Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!
65
Beweis: H
MPKP
![](/pool/data/tex/de44c582df9d8d29dbbd70aca311c641.gif)
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.
Simuliere dazu eine TM als Dominos.
Simuliere dazu eine TM als Dominos.