Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!
66
Simulation einer TM durch Dominos
Gegeben sei die Eingabe (<M>,w) für H. Konstruiere berechnbare Funktion f als Menge M von Dominos M=f(<M>,w). Bilde ungültige Eingaben für H auf ungültige Eingaben für MPKP ab.
1.) Startdomino: Startkonfiguration
2.) Kopierdominos:
für alle 
3.) Überführungssteine:
falls 
falls 
falls 
1.) Startdomino: Startkonfiguration
2.) Kopierdominos:
für alle 3.) Überführungssteine:
falls falls falls 