Thuring Maschine und Automaten

Question

Aufgabe:

Sei

Zeigen Sie, dass L ={M | M ist eine TM und {b}*∩L(M) ungelich ∅}.

Zeigen Sie, dass

1. L aufzählbar ist, aber

2. L nicht entscheidbar ist.

Problem/Ansatz:

Kann mir jemand bei Lösung helfen, ich weiß nicht wie ich es lösen muss.

Comments

Was ist X? Und was ist L?

---

Ich habe falsch geschrieben. L hätte statt x geschrieben werden sollen.

---

Ich habe das geändert.

Was ist L?

---

L ist eine Sprache

---

Welche Sprache ist L?

---

Was meinen Sie?

---

Welche Wörter gehören zu der Sprache L ?

---

Die Wörter, die Turing maschine M akzeptiert und und {b}*∩L(M) ungelich ∅

---

Ich verstehe die Aufgabe nicht und ich brauche die Lösung, um ich die Aufgabe verstehen kann.

---

Wie sieht die Turingmaschine M aus?

---

Keine Ahnung

---

Kannst du mir helfen?

Answer 1

Zeigen Sie, dass L ={M | M ist eine TM und {b}*∩L(M) ungelich ∅}.

Das kann ohne Kenntnis davon, wie L definiert ist, nicht gezeigt werden.

Ich gehe deshalb im Folgenden davon aus, dass

        L = {M | M ist eine TM und {b}*∩L(M) ≠ ∅}

ist.

1. L aufzählbar ist, aber

L kann wie folgt aufgezählt werden.

1. Alle TM mit einem Zustand die in einem Schritt ε oder b akzeptieren
   
2. Alle TM mit höchstens zwei Zuständen die in höchstens zwei Schritten ε oder b oder bb akzeptieren.
3. Alle TM mit höchstens drei Zuständen die in höchstens drei Schritten ε oder b oder bb oder bbb akzeptieren.
   
4. ...

2. L nicht entscheidbar ist.

Sei für jede Turingmaschine M die Turingmaschine B(M) gegeben durch: Für jedes n ∈ ℕ₀ akzeptiert B(M) das Wort bⁿ genau dann, wenn M ein Wort der Länge n akzeptiert.

Dann ist B(M) ∈ L ⇔ {b}* ∩ L(B(M)) ≠ ∅ ⇔ L(M) ≠ ∅.

Das Leerheitsproblem ist aber nicht entscheidbar.

Comments

Danke für deine Antwort. Uch habe aber nicht sicher gut verstanden warum L aufzählbar ist, kannst du vielleicht mehr erklären?

---

Was genau hast du an der Argumentation nicht verstanden?

---

"Eine Sprache L ist aufzählbar, wenn es eine Turingmaschine M gibt, die L akzeptiert, also eine mit L(M) = L"

Wie hast du aber diese Aussage bewiesen? Oder wie hast du bewiesen, dass L aufzählbar ist?

---

Du hast geschrieben,, Das Leerheitsproblem ist aber nicht entscheidbar" aber hier ist L(M) ≠ ∅.

Also L(M) ist nicht gleich ∅. Ich habe hier auch nicht verstanden

---

Kannst du mir helfen?

---

Wenn es eine surjektive, berechenbare Funktion

        \(\varphi:\ \mathbb{N}\to L\subseteq \Sigma^*\)

gibt, dann ist \(L\) aufzählbar.

Beweis. Sei \(w\in \Sigma^*\). Dann terminiert folgender Algorithmus genau dann, wenn \(w\in L\) ist.

Sei n = 1.
Solange φ(n) ≠ w ist
    erhöhe n um 1.

Ich habe den Eindruck, dass der Name aufzählbar genau von diesem Zusammenhang kommt. Man kann dann nämlich alle Wörter von L aufzählen:

        φ(1), φ(2), φ(3), ...

wie hast du bewiesen, dass L aufzählbar ist?

Indem ich aufgezeigt habe, wie man ein geeignetes φ bekommt.

aber hier ist L(M) ≠ ∅.

Das wäre relevant, wenn es um Aufzählbarkeit gehen würde. Hier geht es aber um Entscheidbarkeit.

Eine Sprache \(L\) ist genau dann entscheidbar, wenn \(\overline{L}\) entscheidbar ist.

Ersetzt man in obigem Satz entscheidbar durch aufzählbar, dann gilt der Satz nicht mehr.

---

Kannst du vielleicht der weite Teil(nicht entscheidbar) mit dem Satz von Rice beweisen?

---

Ja, den zweiten Teil kannst du auch mit dem Satz von Rice beweisen.

---

Einer hat mir gesagt, dass zweite Teil mit dem Satz von Rice einfacher ist, aber uch weiß nicht wie ich es machen soll. Es wäre sehr nett von dir, wenn du einmal den zweiten Teil mit dem Satz von Rice beweisen.

Vielen Dank