Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!
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
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
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)
