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.
Die folgenden Hauptfragen werden gestellt:
- 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
- Kellerautomaten
- LBAs (linear platzbeschränkte Turingmaschinen)
- Turingmaschinen
- Registermaschinen
- Welche Art Probleme würden leistungsfähigere Maschinen benötigen?
Welche Art Aufgaben kann eine Turingmaschine lösen?
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: Gegeben ist ein Programm und dessen Eingabe. Die Aufgabe ist es zu entscheiden, ob das Programm mit der gegebenen Eingabe zum Stillstand kommt oder nicht. Turing bewies, dass dies unentscheidbar ist.
Welche anderen Maschinen sind gleich leistungsfähig wie Turingmaschinen?
....
Maschinen, die gleich leistungsfähig wie Turingmaschinen sind:
- Turingmaschine mit mehreren Bändern
- Turingmaschinen mit einem zweidimensionalen "Band"
- Endlicher Automat mit zwei Stapelspeichern
- Endlicher Automat mit zwei Zählern
- Eine formale Sprache
- Lambdakalkül
- Fast jede moderne Programmiersprache
Welche Aufgaben können durch weniger leistungsfähige Maschinen gelöst werden?
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.