imported>일성김: /* Einführungen */

2024-07-13T07:58:45Z

Einführungen

Neue Seite

Die '''Berechenbarkeitstheorie''' (auch '''Rekursionstheorie''') ist ein Teilgebiet der [[Theoretische Informatik|theoretischen Informatik]] und der [[Mathematische Logik|mathematischen Logik]], die sich mit dem Begriff der [[Berechenbarkeit]] befasst, insbesondere damit, welche Probleme mit Hilfe einer [[Automat (Informatik)|Maschine]] (genauer: eines mathematischen Modells einer Maschine) oder eines anderen mathematischen Modells der Berechenbarkeit lösbar sind. Sie ist eng verwandt mit der [[Formale Semantik|formalen Semantik]], richtet aber die Aufmerksamkeit mehr auf die [[Terminiertheit]] von [[Computerprogramm|Programmen]] und [[Algorithmus|Algorithmen]].

Die zentrale Frage der Rekursionstheorie ist, welche Funktionen (bzw. Mengen) sich mit welchem Berechenbarkeitsmodell berechnen lassen. Es werden dazu Modelle für die Berechenbarkeit und deren Leistungsfähigkeit untersucht. Aus der Art der betrachteten Berechnungsmodelle ergibt sich eine unscharfe Abgrenzung zur [[Komplexitätstheorie]], in der vor allem Berechnungsmodelle mit Ressourcenbeschränkung betrachtet werden. Schwerpunkt vieler Untersuchungen in der Rekursionstheorie ist die relative Berechenbarkeit von Funktionen, d. h., welche Funktionen lassen sich mit einer gegebenen Funktion unter Verwendung eines bestimmten Berechnungsmodells berechnen (siehe zum Beispiel unter [[Turinggrad]]e).

== Hauptfragen ==
Wie kann man den Begriff der intuitiven [[Berechenbarkeit]] formalisieren? Als weitgehend anerkannte Antwort hat sich die [[Turingmaschine]] als mögliches Model durchgesetzt ([[Church-Turing-These]]). Es wurde erkannt, dass die Berechnungsfähigkeit der Turingmaschine gleichmächtig zu vielen anderen Berechnungsmodellen ist.

Welche Art Aufgaben kann welche Klasse von [[Automat (Informatik)|Maschinen]] lösen? Insbesondere werden [[Determinismus (Algorithmus)|deterministische]] und [[Nichtdeterminismus|nichtdeterministische]] Varianten folgender Modelle untersucht:
* [[endlicher Automat]]
* [[Kellerautomat]]
* [[linear beschränkte Turingmaschine]] (LBA)
* [[Turingmaschine]]
* [[Registermaschine]]

Welche Art von Problemen benötigt leistungsfähigere Maschinen?

== Welche Art Aufgaben kann eine Turingmaschine lösen? ==
Ein Problem heißt [[entscheidbar]], wenn es durch einen [[Algorithmus]], der nach endlich vielen Schritten terminiert, gelöst werden kann. Viele Probleme sind entscheidbar, es sind aber auch viele unentscheidbare Probleme bekannt. Beispielsweise sind nach dem [[Satz von Rice]] alle (nichttrivialen) semantischen Eigenschaften von Programmen unentscheidbar.

Zum Beispiel kann das Problem der Gültigkeit [[Prädikatenlogik|prädikatenlogischer]] [[Formel]]n 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.
[[Alonzo Church|Church]] und [[Alan Turing|Turing]] haben unabhängig voneinander nachgewiesen, dass dieses Problem nicht gelöst werden kann.

Ein weiteres Problem ist das [[Halteproblem]]. Es seien ein Algorithmus und eine Eingabe gegeben. Es wird gefragt, 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 ==
* [[Turingmaschine]] mit mehreren Bändern
* Turingmaschine mit einem zweidimensionalen „Band“
* [[Registermaschine]]
* erweiterter [[Kellerautomat]] mit zwei Kellerspeichern
* [[endlicher Automat]] mit zwei Zählern
* [[Chomsky-Hierarchie|Typ-0-Grammatik]]
* [[Lambda-Kalkül]]
* [[Μ-Rekursion|rekursive Funktion]]
* erweitertes [[Petri-Netz]] mit Sperrkanten
* [[Markow-Algorithmus]]
* [[Termersetzungssystem]]
* die meisten modernen [[Programmiersprache]]n

== 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 kontextabhä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ärer Ausdruck|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.<ref>[[Richard P. Feynman]]: ''Simulating Physics with computers.'' In: ''International Journal of Theoretical Physics.'' Bd. 21, Nr. 6/7, 1982, {{ISSN|0020-7748}}, S. 467–468, {{DOI|10.1007/BF02650179}}.</ref><ref>Tony Hey: ''Richard Feynman and Computation.'' In: ''Contemporary Physics.'' Bd. 40, Nr. 4, 1999, {{ISSN|0010-7514}}, S. 257–265, {{DOI|10.1080/001075199181459}}.</ref> 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 ==
=== Einführungen ===
* [[George Boolos|George S. Boolos]], John P. Burgess, Richard C. Jeffrey: ''Computability and Logic.'' Cambridge University Press, 2007 (5. Auflage).
* S. Barry Cooper: ''Computability Theory.'' Chapman & Hall/CRC, Boca Raton FL u. a. 2004, ISBN 1-58488-237-9.
* Nigel Cutland: ''Computability. An introduction to recursive function theory.'' Cambridge University Press, Cambridge u. a. 1980, ISBN 0-521-29465-7.
* Klaus Heidler, [[Hans Hermes]], Friedrich-K. Mahn: ''Rekursive Funktionen.'' Bibliographisches Institut, Mannheim u. a. 1977, ISBN 3-411-01535-7.
* Hans Hermes: ''Aufzählbarkeit – Entscheidbarkeit – Berechenbarkeit. Einführung in die Theorie der rekursiven Funktionen'' (= ''Die Grundlehren der mathematischen Wissenschaften.'' 109, {{ISSN|0072-7830}}). Springer, Berlin u. a. 1961 (2. Auflage. ebenda 1971, ISBN 3-540-05334-4, als ''Heidelberger Taschenbuch.'' 87).
* [[Stephen Cole Kleene]]: ''Introduction to Metamathematics'' (= ''Bibliotheca Mathematica.'' 1, {{ZDB|419838-4}}). Amsterdam u. a., North-Holland u. a. 1952.
* [[Michael Sipser]]: ''Introduction to the Theory of Computation.'' PWS Publishing, Boston MA u. a. 1997, ISBN 0-534-94728-X, Part Two: ''Computability Theory.'' Chapters 3–6, S. 123–222.

=== Spezialwerke ===
* [[Piergiorgio Odifreddi]]: ''Classical Recursion Theory. The Theory of Functions and Sets of Natural Numbers.'' 2 Bände. Elsevier, Amsterdam u. a. 1989–1999;
** Band 1. (= ''Studies in Logic and the Foundations of Mathematics.'' 125). 1989, ISBN 0-444-87295-7;
** Band 2. (= ''Studies in Logic and the Foundations of Mathematics.'' 143). 1999, ISBN 0-444-50205-X.
* {{Literatur | Autor= [[Hartley Rogers|Hartley Rogers, Jr.]]| Titel= Theory of recursive functions and effective computability| Verlag= McGraw-Hill| Ort=New York NY u. a. | Jahr=1967 }}
* [[Gerald E. Sacks]]: ''Higher Recursion Theory.'' Springer, Berlin u. a. 1990, ISBN 3-540-19305-7.
* Robert I. Soare: ''Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets'' (= ''Perspectives in Mathematical Logic.''). Springer, Berlin u. a. 1987, ISBN 0-387-15299-7.

== Einzelnachweise ==
<references />

[[Kategorie:Berechenbarkeitstheorie| ]]
[[Kategorie:Mathematische Logik]]

Berechenbarkeitstheorie - Versionsgeschichte

imported>일성김: /* Einführungen */