Nächste Seite: Registermaschinen (kurz: RM) Aufwärts: Hauptseite Theorie Vorherige Seite: Formale Sprachen   Inhalt

Berechenbarkeit

---

Unterabschnitte

• Registermaschinen (kurz: RM)
  • Aufbau und Befehle
  • Kostenmaße
  • Effiziente Algorithmen
  
  
• Turingmaschinen (kurz: DTM oder NTM)
  • Einbandige ,,normale'' Turingmaschinen (deterministisch)
  • Mehrbandige Turingmaschinen
  • Nichtdeterministische Turingmaschinen
  • Kosten von Turingmaschinen
  • Simulation von mehrbandigen Turingmaschinen durch einbandige Turingmaschinen
  • Programmierung von DTMs
  
  
• Registermaschine Turingmaschine
  • Simulation von Registermaschinen durch Turingmaschinen
  • Simulation von Turingmaschinen durch Registermaschinen
  • Simulation von Turingmaschinen mit Turingmaschinen - Universelle Turingmaschinen

---