Also ich denke, mit der Frage in der Prüfung war gemeint,
ob das Halteproblem aufzählbar ist und wie man das begründet.
Und beim Halteproblem sollte man wahrscheinlich immer
erwähnen, dass es unentscheidbar ist (aber das ist ja im
Skript bewiesen).
Und wenn man etwas begründen muss, macht man eines zuerst:
die Definition und äquivalente Charakterisierungen anschauen.
Zur Aufzählbarkeit gibt es da ja verschiedene. Und dann
guckt man, von welcher man am einfachsten Begründen kann,
dass sie zutrifft. In diesem Fall gehts am leichtesten mit
folgender Beschreibung:
"Eine Sprache ist genau dann aufzählbar, wenn sie von einer
TM akzeptiert wird."
Man muss also überlegen, ob es eine TM gibt, die das
Halteproblem akzeptiert, die also die Beschreibung einer
DTM als Eingabe entgegennimmt und genau dann akzeptiert,
wenn diese DTM irgendwann anhält.
Die gibt es: man nimmt die universelle TM und baut sie so zu
einer TM A um, dass A akzeptiert, sobald die simulierte DTM
keine Folgekonfiguration mehr besitzt. Und ansonsten simuliert
A einfach weiter. Damit akzeptiert A genau dann, wenn die TM,
die sie als Eingabe bekommen hat, irgendwann anhält.
Ist das jetzt klar geworden? [img]
http://www.fb18.de/gfx/17.gif[/img]
