---

Geschrieben von Info567 am 24.06.2018 um 20:07:

  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.