Zeigen Sie: L_{5} ist nicht entscheidbar.

Question

Frage:

Sei \( L_{5}:=\left\{w \mid M_{w}\right. \) hält auf genau 10 Eingaben oder auf genau 20 Eingaben \( \} \).

Zeigen Sie: \( L_{5} \) ist nicht entscheidbar.

Wie würde hier die totale Funktion aussehen?

Comments

Was ist \(M_w\)?

---

irgendeine turing maschine

---

\(M_w\) ist mit Sicherheit nicht irgendeine Turingmaschine.

---

ich bin mir sehr sicher. wir sollen hier ja von dem Halteproblem reduizieren auf unsere Sprache und dort ist die Turingmaschine ja auch nicht definiert

---

Die Frage ergibt überhaupt keinen Sinn, wenn es keinen Zusammenhang zwischen \(w\) und \(M_w\) gibt.

Es gibt eine sogenannte universelle Turingmaschine. Diese Turingmaschine bekommt als Eingabe ein Wort \(w\) und ein Wort \(w'\). Sie fasst \(w\) als Codierung einer Turingmaschine \(M\) auf und liefert als Ausgabe das Wort, das die Turingmaschine \(M\) mit \(w'\) als Eingabe liefern würde.

Ich vermute, \(M_w\) soll die durch das Wort \(w\) codierte Turingmaschine sein.

---

ich denke genauso ist es gemeint.

Answer 1

Die totale Funktion, die L5 entscheidet, würde wie folgt aussehen:

def decide_L5(w):

  for i in range(1, 21):

      result = run_input_on_machine(w, i)

      if result:

          for j in range(i+1, 21):

              if run_input_on_machine(w, j):

                  return False

          return True

  return False

Hier wird die Funktion run_input_on_machine(w, n) verwendet, die die Eingabe w auf der Turingmaschine mit der ID w mit einer maximalen Laufzeit von n Schritten ausführt und True zurückgibt, falls die Turingmaschine anhält, andernfalls False.

Um zu zeigen, dass diese Funktion nicht entscheidbar ist, können wir einen Widerspruchsbeweis durchführen. Angenommen, decide_L5 entscheidet L_5. Wir konstruieren dann eine neue Funktion decide_L5_prime, die das Komplement von L_5 entscheidet, d.h. die Eingaben akzeptiert, die nicht in L_5 liegen, und die Eingaben ablehnt, die in L_5 liegen. Dazu verwenden wir decide_L5 wie folgt:

def decide_L5_prime(w):

  if decide_L5(w):

      return False

  else:

      return True

Nun betrachten wir die Eingabe w' mit der ID decide_L5_prime. Diese Eingabe muss von decide_L5_prime entschieden werden. Wenn decide_L5_prime(w') True zurückgibt, dann muss decide_L5(w') True zurückgeben, da w' nicht in L_5 liegt. Aber das bedeutet, dass w' auf genau 10 oder auf genau 20 Eingaben halten muss, was ein Widerspruch ist. Wenn decide_L5_prime(w') False zurückgibt, dann muss decide_L5(w') False zurückgeben, da w' in L_5 liegt. Aber das bedeutet, dass w' auf keiner der ersten 20 Eingaben hält, was ebenfalls ein Widerspruch ist. Daher kann decide_L5 nicht existieren, und somit ist L_5 nicht entscheidbar.

PS: Entschuldigung, falls ich einen Fehler gemacht haben sollte. Ich habe es einfach so geschrieben, wie ich es für richtig halte.

Ich hoffe ich konnte Ihnen helfen.