Berechenbarkeitstheorie
Die Berechenbarkeitstheorie ist derjenige Teil der theoretischen Informatik, der sich damit befasst, welche Probleme mit Hilfe eines Algorithmus lösbar sind.
Die folgenden Hauptfragen werden gestellt:
- Welche Art Aufgaben kann ein endlicher Automat lösen?
- Welche Art Aufgaben kann ein Kellerautomat lösen?
- Welche Art Aufgaben kann eine Turingmaschine lösen?
- Was für andere Systeme gibt es, die gleich leistungsfähig wie Turingmaschinen sind?
- Welche Art Probleme würden leistungsfähigere Maschinen benötigen?
- Welche Art Aufgaben können mit weniger leistungsfähigen Maschinen gelöst werden.
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 und die Aufgabe ist 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 ein Programm und dessen Eingabe und die Aufgabe zu entscheiden ob das Programm mit der gegebenen Eingabe zum Stillstand kommt oder nicht. Turing bewies, dass dies unentscheidbar ist.
Welche andern 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 Chomskyhierarchie 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. Und wenn die Maschine keinen Speicher hat, dann können nur Sprachen, die durch reguläre Ausdrücke definiert sind, erkannt werden.