This flashcard is just one of a free flashcard set. See all flashcards!
60
Postsches Korrespondenzproblem
korrespondierende Folge: Folge von Dominos aus einer Menge K von Dominos, sodass oben und unten dasselbe Wort steht. (Folge soll aus mind. einem Domino bestehen und Dominos dürfen sich wiederholen)
Instanz des PKP: besteht aus einer Menge
![](/pool/data/tex/931a4a0e530b7b0bac4ba79656b9812e.gif)
wobei
und
nichtleere Wörter über einem endlichen Alphabet
sind.
Es soll entschieden werden, ob es eine korrespondierende Folge von Indizes
gibt, also eine Folge, sodass gilt
.
=>PKP nicht rekursiv, aber rekursiv aufzählbar.
=>
ist nicht rekursiv aufzählbar
(Reduziere dazu MPKP auf PKP und H auf MKPK daraus folgt dass man H auf PKP reduzieren kann)
Instanz des PKP: besteht aus einer Menge
![](/pool/data/tex/931a4a0e530b7b0bac4ba79656b9812e.gif)
wobei
![](/pool/data/tex/1ba8aaab47179b3d3e24b0ccea9f4e30.gif)
![](/pool/data/tex/8d62e469fb30ed435a668eb5c035b1f6.gif)
![](/pool/data/tex/025b3f94d79319f2067156076bf05243.gif)
Es soll entschieden werden, ob es eine korrespondierende Folge von Indizes
![](/pool/data/tex/b4aba7a2c394906d729efedb68c297ea.gif)
![](/pool/data/tex/92c1fa9d21dad8c54563288784c4f009.gif)
=>PKP nicht rekursiv, aber rekursiv aufzählbar.
=>
![](/pool/data/tex/c0049e6f44e2055f5fe0b0177ec95eb7.gif)
(Reduziere dazu MPKP auf PKP und H auf MKPK daraus folgt dass man H auf PKP reduzieren kann)