Entscheidbarkeit einer Turingmaschine |
| 24.06.2018, 20:07 | Auf diesen Beitrag antworten » |
| 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. |
|
|
|
|
|
