www.wikidata.de-de.nina.az

Berechenbarkeitstheorie Die auch Rekursionstheorie ist ein Teilgebiet der theoretischen Informatik und der mathematische

Berechenbarkeitstheorie

Die Berechenbarkeitstheorie (auch Rekursionstheorie) 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) oder eines anderen mathematischen Modells der Berechenbarkeit lösbar sind. Sie ist eng verwandt mit der formalen Semantik, richtet aber die Aufmerksamkeit mehr auf die Terminiertheit von Programmen und 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 Turinggrade).

Hauptfragen Bearbeiten

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 Maschinen lösen? Insbesondere werden deterministische und nichtdeterministische Varianten folgender Modelle untersucht:

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

Welche Art Aufgaben kann eine Turingmaschine lösen? Bearbeiten

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ä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. 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 Bearbeiten

Welche Aufgaben können durch weniger leistungsfähige Maschinen gelöst werden? Bearbeiten

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äre Ausdrücke definiert sind, erkannt werden.

Zusammenhang mit der Physik Bearbeiten

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

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 Bearbeiten

Einführungen Bearbeiten

  • 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-ID 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 Bearbeiten

  • 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.
  • Hartley Rogers, Jr.: Theory of recursive functions and effective computability. McGraw-Hill, New York NY u. a. 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 Bearbeiten

  1. 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.
  2. Tony Hey: Richard Feynman and Computation. In: Contemporary Physics. Bd. 40, Nr. 4, 1999, ISSN 0010-7514, S. 257–265, doi:10.1080/001075199181459.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Berechenbarkeitstheorie auch Rekursionstheorie 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 oder eines anderen mathematischen Modells der Berechenbarkeit losbar sind Sie ist eng verwandt mit der formalen Semantik richtet aber die Aufmerksamkeit mehr auf die Terminiertheit von Programmen und Algorithmen Die zentrale Frage der Rekursionstheorie ist welche Funktionen bzw Mengen sich mit welchem Berechenbarkeitsmodell berechnen lassen Es werden dazu Modelle fur die Berechenbarkeit und deren Leistungsfahigkeit untersucht Aus der Art der betrachteten Berechnungsmodelle ergibt sich eine unscharfe Abgrenzung zur Komplexitatstheorie in der vor allem Berechnungsmodelle mit Ressourcenbeschrankung 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 Turinggrade Inhaltsverzeichnis 1 Hauptfragen 2 Welche Art Aufgaben kann eine Turingmaschine losen 3 Andere Modelle fur Berechenbarkeit mit gleicher Leistungsfahigkeit 4 Welche Aufgaben konnen durch weniger leistungsfahige Maschinen gelost werden 5 Zusammenhang mit der Physik 6 Literatur 6 1 Einfuhrungen 6 2 Spezialwerke 7 EinzelnachweiseHauptfragen BearbeitenWie kann man den Begriff der intuitiven Berechenbarkeit formalisieren Als weitgehend anerkannte Antwort hat sich die Turingmaschine als mogliches Model durchgesetzt Church Turing These Es wurde erkannt dass die Berechnungsfahigkeit der Turingmaschine gleichmachtig zu vielen anderen Berechnungsmodellen ist Welche Art Aufgaben kann welche Klasse von Maschinen losen Insbesondere werden deterministische und nichtdeterministische Varianten folgender Modelle untersucht endlicher Automat Kellerautomat linear beschrankte Turingmaschine LBA Turingmaschine RegistermaschineWelche Art von Problemen benotigt leistungsfahigere Maschinen Welche Art Aufgaben kann eine Turingmaschine losen BearbeitenEin Problem heisst entscheidbar wenn es durch einen Algorithmus der nach endlich vielen Schritten terminiert gelost 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 Gultigkeit pradikatenlogischer Formeln nicht algorithmisch gelost werden Gegeben ist eine Aussage der Pradikatenlogik 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 unabhangig voneinander nachgewiesen dass dieses Problem nicht gelost werden kann Ein weiteres Problem ist das Halteproblem Es seien ein Algorithmus und eine Eingabe gegeben Es wird gefragt ob der Algorithmus fur die Eingabe schliesslich halt terminiert Turing wies die Unentscheidbarkeit dieser Frage nach Andere Modelle fur Berechenbarkeit mit gleicher Leistungsfahigkeit BearbeitenTuringmaschine mit mehreren Bandern Turingmaschine mit einem zweidimensionalen Band Registermaschine erweiterter Kellerautomat mit zwei Kellerspeichern endlicher Automat mit zwei Zahlern Typ 0 Grammatik Lambda Kalkul rekursive Funktion erweitertes Petri Netz mit Sperrkanten Markow Algorithmus Termersetzungssystem die meisten modernen ProgrammiersprachenWelche Aufgaben konnen durch weniger leistungsfahige Maschinen gelost werden BearbeitenDie Chomsky Hierarchie beschreibt diejenigen formalen Sprachen die durch vier Klassen von Algorithmen erkannt werden konnen Sie alle setzen einen nichtdeterministischen endlichen Automaten voraus mit einem Speicher Wenn der Speicher unendlich gross ist dann entspricht die Situation der Turingmaschine Wenn der Speicher proportional zur Grosse der Eingabezeichenkette ist dann konnen kontextabhangige Sprachen erkannt werden Wenn der Speicher nur einen Stapel umfasst dann konnen kontextfreie Sprachen erkannt werden Wenn die Maschine nur einen endlichen Speicher hat dann konnen nur Sprachen die durch regulare Ausdrucke definiert sind erkannt werden Zusammenhang mit der Physik BearbeitenDem Physiker Richard Feynman fiel auf dass Computer ziemlich schlecht darin sind Problemstellungen aus der Quantenmechanik zu berechnen 1 2 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 konnen Daher schlug er vor einen besonderen Computer zu bauen einen Quantenprozessor Dessen Rechenwerk sollte quantenmechanische Prozesse nutzen um Ergebnisse fur 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 konnen weil man nicht alle physikalischen Moglichkeiten ausgeschopft hatte Diese neue Klasse von Computern wird als Quantencomputer bezeichnet Trotzdem sind Quantencomputer im Sinne der Berechenbarkeitstheorie nicht machtiger als Turingmaschinen sie konnen exakt die gleichen Probleme losen jedoch konnte sich eventuell ein erheblicher Geschwindigkeitsvorteil ergeben Literatur BearbeitenEinfuhrungen Bearbeiten S Barry Cooper Computability Theory Chapman amp 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 Aufzahlbarkeit Entscheidbarkeit Berechenbarkeit Einfuhrung 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 ID 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 Bearbeiten Piergiorgio Odifreddi Classical Recursion Theory The Theory of Functions and Sets of Natural Numbers 2 Bande 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 Hartley Rogers Jr Theory of recursive functions and effective computability McGraw Hill New York NY u a 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 Bearbeiten 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 Tony Hey Richard Feynman and Computation In Contemporary Physics Bd 40 Nr 4 1999 ISSN 0010 7514 S 257 265 doi 10 1080 001075199181459 Abgerufen von https de wikipedia org w index php title Berechenbarkeitstheorie amp oldid 218546464