| |
|
Nicht alle Aufgaben können gelöst werden. 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. Man kennt viele unentscheidbare Aufgaben.
Z. B. kann das Entscheidungsproblem nicht gelöst werden: Gegeben ist eine Aussage der Prädikatenlogik erster Ordnung. Aufgabe ist es zu entscheiden, ob die Aussage allgemein gültig ist.
Church und Turing haben unabhängig nachgewiesen, dass diese Aufgabe nicht gelöst werden kann.
Ein weiteres Problem ist das Halteproblem, siehe dort.
Maschinen, die gleich leistungsfähig wie Turingmaschinen sind:
Die Chomsky-Hierarchie beschreibt diejenigen formalen Sprachen die durch vier Klassen von Algorithmen erkannt werden können.
Sie alle setzten einen nichtdeterministischen endlichen Automaten voraus mit einem Speicher.
Wenn der Speicher unendlich groß ist, dann entspricht die Situation der Turingmaschine.
Wenn der Speicher proportional zur Größe der Eingabezeichenkette ist, dann können kontext-abhängige Sprachen erkannt werden.
Wenn der Speicher nur einen Stapel umfasst, dann können kontextfreie Sprachen erkannt werden.
Wenn die Maschine keinen Speicher hat, dann können nur Sprachen, die durch reguläre Ausdrücke definiert sind, erkannt werden.
Hauptfragen
Welche Art Aufgaben kann eine Turingmaschine lösen?
Welche anderen Maschinen sind gleich leistungsfähig wie Turingmaschinen?
Welche Aufgaben können durch weniger leistungsfähige Maschinen gelöst werden?