Zeige: Sprache L := { <M> | M hält für mindestens eine Eingabe } ist rekursiv aufzählbar

Question

Aufgabe:

Zeigen Sie, dass die Sprache

          L := { <M> | M hält für mindestens eine Eingabe }

rekursiv aufzählbar ist.

Problem/Ansatz:

1) M gültige Gödelnummer

2) M' simuliert M mit Eingabe w, prüfe ob qaccept / qreject errreicht wird.

   1. Fall: Falls qaccept/qreject erreicht wird, so akzeptiere.

   2. Fall: Falls kein haltender Zustand erreicht wird, so lehne ab.

Könnte man das so zeigen?

Kommentar: 

Das hält bedeutet, ob die Turingmaschine in einen haltenden Zustand kommt. Qaccept oder Qreject. Die eckigen Klammern um M bedeuten das es sich um eine codierte Turingmaschine handelt die einer anderen Turingmaschine übergeben wird.

Comments

L := { <M> | M hält für mindestens eine Eingabe }

Was bedeutet "hält" in diesem Zusammenhang?

Wie sind die eckigen Klammern um M zu lesen?

---

Das hält bedeutet, ob die Turingmaschine in einen haltenden Zustand kommt. Qaccept oder Qreject. Die eckigen Klammern um M bedeuten, dass es sich um eine codierte Turingmaschine handelt, die einer anderen Turingmaschine übergeben wird.

---

Danke für die Ergänzung.

---

Ich vermute, dass sich in der Stacklounge bestimmt jemand damit auskennt.

Als Laie noch eine andere Frage: Warum ist M in 1) plötzlich eine Nummer? Ich könnte mir vorstellen, dass M eine gültige Gödelnummer hat.

2. Fall: Falls kein haltender Zustand erreicht wird, so lehne ab.

Wie lange kannst / willst du hier warten? Ist das praktisch durchführbar?

---

M ist eine codierte Turingmaschine, die einer anderen Turingmaschine M' mit Eingabe w übergeben wird.

Die Eingabe ist immer endlich.

Answer 1

Hi,

das Halten hättet ihr nicht definieren müssen, eigentlich ist das für "Informatiker" klar :)

Also rekursiv Aufzählbar heißt ja dass ich der Reihe nach die Wörter aufzählen kann und halte, falls es passt. Der Ansatz, wie er in der Antwort beschreiben wird, ist meiner Meinung nach so in Ordnung.

@Lu: "Wie lange kannst / willst du hier warten? Ist das praktisch durchführbar?" Praktisch naja :D es geht eher darum einen Widerspruch zu finden. Denn Fakt ist, ich kann nie sagen, ob eine TM auf einer Eingabe w hält. (den Beweis spare ich mir hier mal, der ist aber nicht ganz so schwer)