Nächste Seite: Wortproblem Aufwärts: Hauptseite Theorie Vorherige Seite: Registermaschine Turingmaschine   Inhalt

Entscheidbarkeit

---

Unterabschnitte

• Wortproblem
• Charakteristische Funktion
  • Totale charakteristische Funktion
  • Partielle charakteristische Funktion
  
  
• Entscheidbarkeit
  • Semientscheidbarkeit
  • Entscheidbarkeit
  • Nicht entscheidbar Unentscheidbar
  • Nicht semientscheidbar
  
  
• Zusammenhang zwischen Entscheidbarkeit und Semientscheidbarkeit
  • entscheidbar, dann auch entscheidbar
  • und semientscheidbar entscheidbar
  
  
• Rekursive Aufzählbarkeit
  • Rekursiv aufzählbar Semientscheidbar
  • Semientscheidbar Rekursiv aufzählbar
  
  
• Halteproblem
  • Die Sprache des Halteproblems und des speziellen Halteproblems
  • Satz: Das Halteproblem ist unentscheidbar
  • Informeller Beweis des Halteproblems mittels Halteproblemtabelle
  • Das Halteproblem ist Semientscheidbar
  • Spezielles Halteproblem
  • Reduktion
  • Reduktionsprinzip
  • Unentscheidbarkeit des Halteproblems
  • Die Nicht-Semientscheidbarkeit des Komplements des Halteproblems: Satz
  • Die Nicht-Semientscheidbarkeit des Komplements des Halteproblems: Informell
  • Die Nicht-Semientscheidbarkeit des Komplements des Halteproblems: Formal
  
  
• Andere unentscheidbare Probleme
  • Satz von Rice
  
  
• Nichtdeterminismus (Ergänzung)
  • Nichtdeterministische Entscheidbarkeit
  • NTM DTM

---