| Infos Home | Impressum | Original Artikel & Autoren Liste |
Hauptfragen
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, siehe dort.
Andere Modelle für Berechenbarkeit mit gleicher Leistungsfähigkeit
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.
|
Der Ursprungsartikel stammt von der deutschsprachigen Wiki pedia (siehe oben: "Original Artikel & Autoren Liste"). Der Text steht unter der GNU Freie Dokumentation Lizenz. |