Das Kefk Network Wiki befindet sich im Testbetrieb.

---

Aus Kefk.

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. Sie ist eng verwandt mit der formalen Semantik, richtet aber die Aufmerksamkeit mehr auf die Terminiertheit von Programmen und Algorithmen. Auch verwendet sie als Ausgangspunkt die verschiedenen Modelle von Maschinen, und nicht die abstrakteren Spezifikationssprachen.

Inhaltsverzeichnis 1 Hauptfragen 2 Welche Art Aufgaben kann eine Turingmaschine lösen? 3 Andere Modelle für Berechenbarkeit mit gleicher Leistungsfähigkeit 4 Welche Aufgaben können durch weniger leistungsfähige Maschinen gelöst werden? 5 Zusammenhang mit der Physik 5.1 Literatur 6 Andere Namen

Hauptfragen

• 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
  • Kellerautomat
  • Linear beschränkte Turingmaschine (LBA)
  • Turingmaschine
  • Registermaschine
• 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 spezielle 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

• Turingmaschine mit mehreren Bändern
• Turingmaschinen mit einem zweidimensionalen "Band"
• Registermaschinen
• Erweiterter Kellerautomat mit zwei Kellerspeichern
• Endlicher Automat mit zwei Zählern
• Typ-0-Grammatiken
• Lambda-Kalkül
• rekursive Funktionen
• Erweiterte Petri-Netze mit Sperrkanten
• Markow-Algorithmen
• die meisten modernen Programmiersprachen

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 setzen 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 nur einen endlichen Speicher hat, dann können nur Sprachen, die durch reguläre Ausdrücke definiert sind, erkannt werden.

Zusammenhang mit der Physik

Dem Physiker Richard Feynman fiel auf, dass Computer ziemlich schlecht sind, Problemstellungen aus der Quantenmechanik zu berechnen. Ein wichtiger Vortrag von ihm hierzu aus dem Jahre 1981 hatte den Titel

Can (quantum) physics be (efficiently) simulated by (classical) computers?

Offenbar kann die Natur den Ausgang eines quantenmechanischen Experimentes schneller ausrechnen, als wir dies mit einem Computer können. Daher schlug er vor, einen besonderen Computer zu bauen, einen Quantenprozessor. Dessen Rechenwerk sollte quantenmechanische Prozesse nutzen, um Ergebnisse für quantenmechanische Probleme effizienter zu berechnen. Dabei wurde dann irgendwann klar, dass die einfachen mathematischen Modelle der theoretischen Informatik eigentlich nur mit einer Teilklasse der realen Computer korrespondieren können, weil man nicht alle physikalischen Möglichkeiten ausgeschöpft hatte. Diese neue Klasse von Computern wird als Quantencomputer bezeichnet. Trotzdem sind Quantencomputer im Sinne der Berechenbarkeitstheorie nicht mächtiger als Turingmaschinen (sie können exakt die gleichen Probleme lösen) jedoch könnte sich eventuell ein erheblicher Geschwindigkeitsvorteil ergeben.

Literatur

Tony Hey: Richard Feynman and Computation, Contemporary Physics, 1999, Volume 40, number 4, p. 257-265, ISSN 0010-7514

Andere Namen

Der früher verwendete Begriff Rekursionstheorie meint heute das gleiche wie Berechenbarkeitstheorie, da die rekursiven Funktionen gerade die berechenbaren Funktionen sind.

Einige Autoren verwenden den Begriff Rekursion, um nur die Funktionen mit explizitem Selbstbezug zu kennzeichnen.

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Berechenbarkeitstheorie, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.