Automatentheorie: Frage zu Entscheidbarkeit und rek. Aufz.

[Nikolas]

Hallo Delphianer

Ich hoffe mal, dass es hier ein paar Studenten gibt, die schon in den Genuss einer Vorlesung über Automatentheorie gekommen sind. (Oder andere, die sich in ihrer Freizeit mit theoretischer Informatik beschäftigen).

Es geht um die Sprache L = { <M> | M akzeptiert mindestens zwei Eingaben}.
Wobei <M> eine Kodierung einer TuringMaschine ist.

Zu untersuchen ist die entscheidbarkeit und die rekursive Aufzählbarkeit.
Ich habe eine Idee und wollte euch mal fragen, was ihr davon haltet:

a) Entscheidbarkeit: Turingmaschinen sind unter Vereinigung abgeschlossen, da ich in einer TM zwei andere parallel simulieren kann.
Jetzt nehme ich eine beliebige Sprache A, die nur ein Wort akzeptiert. (ein Übergang vom Start in den akzeptierenden Übergang, der ein bestimmtes Zeichen von der Eingabe liest) und vereinige diese Sprache mit einer anderen (B).
Jetzt frage ich, ob diese Vereinigung mehr als ein Wort akzeptiert, was mit meine Entscheider-TM für L sagen kann. Wenn das der Fall ist, akzeptiert B mindestens ein Wort, sonst nicht.
Diese Entscheider-TM kann also genutzt werden, um das unentscheidbare Leerheitsproblem der TM zu entscheiden, damit gibt es sie nicht und L ist nicht entscheidbar .

b) rekursiv aufzählbar: Ich brauche also eine TM, die hält, wenn M mehr als eine Eingabe akzeptiert und sonst weiterlaufen darf.
Ich nehme mir eine Liste aller möglichen Eingaben. (erst alle mit einem Zeichen, dann die mit zwei Zeichen usw. (lexikalisch geordnet)). So eine Liste kann ich mir anlegen, weil die Menge der Eingabe abzählbar ist. Jetzt simuliere ich einen Schritt von M für die erste Eingabe. Dann simuliere ich noch einen schritt von M für die erste Eingabe und schreibe mir die Konfiguration irgendwo hin. Dann simuliere ich einen Schritt von M für die zweite Eingabe und merke mir diese Konfiguration. Dann wieder einen für die erste Eingabe, für die zweite Eingabe und dann für die dritte. usw usw usw.

Ich simuliere also im Endeffekt sämtliche Eingaben auf einmal. Jede Eingabe wird simuliert und bekommt eine unendliche Rechenzeit. (spätere Eingaben müssen zwar seeehr lange auf ihre Berechnung warten, werden aber irgendwann betrachtet).

Ich muss mich also nur neben diese TM setzen und die akzeptierten Eingaben zählen. Gibt es mehr als eine, werde ich irgendwann aufhören können, wenn nicht, läuft diese TM ewig, aber das darf mir bei der rekursiven Aufzählbarkeit egal
sein.

Was meint ihr dazu? Klingt das plausibel?

Nikolas

[Nikolas]

Gibt's hier niemanden, der TuringMaschinen toll findet?