| Info567 |
Entscheidbarkeit einer Turingmaschine
Meine Frage:
Hallo Leute,
ich habe eine Turingmaschine M für ein Problem gegeben und soll entscheiden und beweisen, ob dieses entscheidbar, semi-entscheidbar oder unentscheidbar ist.
Die Frage die die Turingmaschine prüfen soll ist:
Erzeugt die Turingmaschine bei keiner Eingabe die Ausgabe 0?
Beide Alphabete sind dabei durch die Zeichen 0 und 1 codiert.
Meine Ideen:
Ich hätte gesagt, dass dieses Problem unentscheidbar ist, da die Turingmaschine zwar alle möglichen Eingaben durchgehen kann und sobald sie ein Wort findet, wo 0 ausgegeben wird sagen kann dass die Frage mit nein beantwortet werden kann. Aber es können ja beliebig viele Wörter als Eingabe erfolgen die geprüft werden müssen. |
