Berechenbarkeitstheorie

Die Berechenbarkeitstheorie ist ein Teilgebiet der theoretischen Informatik und der mathematischen Logik, die sich mit dem Begriff der Berechenbarkeit befasst, insbesondere damit, welche Probleme mit Hilfe einer Maschine (genauer: eines mathematischen Modells 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.

Die Berechenbarkeitstheorie wird oft auch als Rekursionstheorie bezeichnet. Manchmal wird letzterer Begriff auch benutzt, wenn man die Berechenbarkeitstheorie als Teilgebiet der mathematischen Logik auffasst oder um zu betonen, dass auch verallgemeinerte Formen von Berechenbarkeit und Definierbarkeit betrachtet werden. Einige Autoren verwenden den Begriff Rekursion, um nur die Funktionen mit explizitem Selbstbezug zu kennzeichnen.

Inhaltsverzeichnis

Hauptfragen

Welche Art Aufgaben kann eine Turingmaschine lösen?

Ein Problem heißt entscheidbar, wenn es durch einen Algorithmus gelöst werden kann. Viele Probleme sind entscheidbar. Man kennt aber auch viele unentscheidbare Probleme.

Zum Beispiel kann das Problem der Gültigkeit prädikatenlogischer Formeln nicht algorithmisch gelöst werden: Gegeben ist eine Aussage der Prädikatenlogik erster Stufe. Aufgabe ist es herauszubekommen, ob die Aussage wahr ist. Dieses Problem ist auch als das Entscheidungsproblem (im engeren Sinn) bekannt. Church und Turing haben unabhängig voneinander nachgewiesen, dass dieses Problem nicht gelöst werden kann.

Ein weiteres Problem ist das Halteproblem. Gegeben seien ein Algorithmus und eine Eingabe. Gefragt wird, ob der Algorithmus für die Eingabe schließlich hält (terminiert). Turing wies die Unentscheidbarkeit dieser Frage nach.

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 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 darin 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

  • Hans Hermes: Aufzählbarkeit - Entscheidbarkeit - Berechenbarkeit. Einführung in die Theorie der rekursiven Funktionen. Berlin - Göttingen - Heidelberg 1961, 2. Aufl. 1971 (als Heidelberger Taschenbuch).
  • Klaus Heidler / Hans Hermes / Friedrich-K. Mahn.: Rekursive Funktionen. Mannheim - Wien - Zürich 1977.
  • Tony Hey: Richard Feynman and Computation. In: Contemporary Physics. Band 40, 1999, Heft 4, S. 257–265, ISSN 0010-7514

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Notation (Berechenbarkeitstheorie) — Eine Notation einer Menge M, im Sinne der Berechenbarkeitstheorie, ist eine möglicherweise partielle surjektive Funktion . Notationen und die verwandten Nummerierungen sind z. B. Werkzeuge beim Beweis der Äquivalenz von Register und… …   Deutsch Wikipedia

  • Registermaschine (Berechenbarkeitstheorie) — Die Registermaschine (auch RAM für engl. random access machine) ist ein Rechnermodell der theoretischen Informatik, das einem realen Rechner (PC) sehr ähnlich ist. Eine Registermaschine kann alles, was auch ein realer Rechner kann. Da man auch… …   Deutsch Wikipedia

  • Theoretische informatik — Mindmap zu einem Teilbereich der Theoretischen Informatik Die Theoretische Informatik beschäftigt sich mit der Abstraktion, Modellbildung und grundlegenden Fragestellungen, die mit der Struktur, Verarbeitung, Übertragung und Wiedergabe von… …   Deutsch Wikipedia

  • Theoretische Informatik — Mind Map zu einem Teilbereich der Theoretischen Informatik Die Theoretische Informatik beschäftigt sich mit der Abstraktion, Modellbildung und grundlegenden Fragestellungen, die mit der Struktur, Verarbeitung, Übertragung und Wiedergabe von… …   Deutsch Wikipedia

  • Berechnungstheorie — Die Berechenbarkeitstheorie ist ein Teilgebiet der theoretischen Informatik und der mathematischen Logik, die sich mit dem Begriff der Berechenbarkeit befasst, insbesondere welche Probleme mit Hilfe einer Maschine (genauer: eines mathematischen… …   Deutsch Wikipedia

  • Rekursionstheorie — Die Berechenbarkeitstheorie ist ein Teilgebiet der theoretischen Informatik und der mathematischen Logik, die sich mit dem Begriff der Berechenbarkeit befasst, insbesondere welche Probleme mit Hilfe einer Maschine (genauer: eines mathematischen… …   Deutsch Wikipedia

  • Theorie der Berechenbarkeit — Die Berechenbarkeitstheorie ist ein Teilgebiet der theoretischen Informatik und der mathematischen Logik, die sich mit dem Begriff der Berechenbarkeit befasst, insbesondere welche Probleme mit Hilfe einer Maschine (genauer: eines mathematischen… …   Deutsch Wikipedia

  • Turing-mächtig — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

  • Turing Vollständigkeit — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

  • Turingmächtig — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”