Berechenbarkeitstheorie
Die Berechenbarkeitstheorie ist ein Teilgebiet der theoretischen Informatik, der sich mit dem Begriff der Berechenbarkeit befasst, insbesondere welche Probleme mit Hilfe einer Maschine (genauer: eines mathematischen Modelles einer Maschine) lösbar sind.
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.
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?
Andere Modelle für Berechenbarkeit mit gleicher Leistungsfähigkeit
Welche Aufgaben können durch weniger leistungsfähige Maschinen gelöst werden?