CoboCards App FAQ & Wünsche Feedback
Sprache: Deutsch Sprache
Kostenlos registrieren  Login

Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!

Alle Oberthemen / Mathematik / Berechenbarkeit / Berechenbarkeit I
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)

Neuer Kommentar
Karteninfo:
Autor: hemag
Oberthema: Mathematik
Thema: Berechenbarkeit
Veröffentlicht: 16.03.2010

Abbrechen
E-Mail

Passwort

Login    

Passwort vergessen?
Deutsch  English