Welche Art Aufgaben kann eine Turingmaschine lösen?

Ein unentscheidbares Problem ist eines, das nicht durch einen Algorithmus gelöst werden kann, auch wenn unbeschränkt Zeit und Geld zur Verfügung steht.Nicht alle Aufgaben können gelöst werden. Man kennt viele unentscheidbare Aufgaben.

Aufgabe ist es zu entscheiden, ob die Aussage allgemein gültig ist. kann das spezielle Entscheidungsproblem nicht gelöst werden: Gegeben ist eine Aussage der Prädikatenlogik erster Ordnung.Z. B.

Church und Turing haben unabhängig nachgewiesen, dass diese Aufgabe nicht gelöst werden kann.

Ein weiteres Problem ist das Halteproblem, siehe dort.

Hauptfragen

• Wie kann man den Begriff der Berechenbarkeit formalisieren?
• Welche Art Aufgaben kann welche Klasse von Maschinen lösen? Insbesondere werden deterministische und nichtdeterministische Varianten folgender Modelle untersucht:
  • endlicher Automat
  • Kellerautomat
  • Linear beschränkte Turingmaschine (LBA)
  • Turingmaschine
  • registermaschine
• Welche Art Probleme würden leistungsfähigere Maschinen benötigen?

Literatur

257-265, ISSN 0010-7514.Tony Hey: Richard Feynman and Computation, Contemporary Physics, 1999, Volume 40, number 4, p.

Andere Modelle für Berechenbarkeit mit gleicher Leistungsfähigkeit

• Turingmaschine mit mehreren Bändern
• Turingmaschinen mit einem zweidimensionalen "Band"
• registermaschinen
• Erweitereter Kellerautomat mit zwei Kellerspeichern
• Endlicher Automat mit zwei Zählern
• Typ-0-Grammatiken
• Lambda-Kalkül
• rekursive Funktionen
• Erweiterte Petri-Netze mit Sperrkanten
• Markow-Algorithmen
• die meisten modernen Programmiersprachen