These von Church

These von Church

Die Church-Turing-These (benannt nach Alonzo Church und Alan Turing, auch Churchsche These genannt) trifft Aussagen über die Fähigkeiten einer Rechenmaschine. Sie lautet:

Die Klasse der Turing-berechenbaren Funktionen ist genau die Klasse der intuitiv berechenbaren Funktionen.

Diese These ist nicht beweisbar, da der Begriff intuitiv berechenbare Funktion nicht exakt formalisiert werden kann. Man versteht darunter alle Funktionen, die prinzipiell auch von einem Menschen ausgerechnet werden könnten. Damit setzt man insbesondere keine Vorstellung voraus, welche Funktionen auf den natürlichen Zahlen berechenbar sind. Es wird in der Informatik üblicherweise angenommen, dass die These stimmt. Dadurch kann es ermöglicht werden, von einer Funktion nachzuweisen, dass sie nicht berechenbar ist.

Inhaltsverzeichnis

Entstehung

Turing empfand die Gedankenprozesse eines Menschen beim Zahlenrechnen durch die von ihm entwickelte Turingmaschine nach (in der Funktionsweise ähnlich den heutigen Computern) und analysierte deren Fähigkeiten. Er stellte fest, dass viele Funktionen, die von einem Menschen ausgedacht werden können, erst gar nicht durch die Turingmaschine berechenbar sind, wie z. B. die Funktion des Halteproblems.

Zum anderen zeigte sich, dass auch andere Herangehensweisen, die menschliche Denkweise beim Rechnen zu formalisieren, nicht erfolgreicher waren: So wurde von Turing historisch zuerst die Äquivalenz von Churchs Lambdakalkül zur Turingmaschine bewiesen. Es folgten darauf viele weitere vorgeschlagene Algorithmenbegriffe (Rechenmodelle), die alle in ihrer Berechnungsfähigkeit nicht mehr leisteten als die Turingmaschine. Man bezeichnet diese Algorithmenbegriffe demzufolge als Turing-vollständig.

Dies ließ vermuten, dass es keinen mächtigeren Formalismus als den der Turingmaschine hinsichtlich der Berechenbarkeit gebe und der Mensch – ebenfalls algorithmisch arbeitend – auch nicht mehr Funktionen ausrechnen könne. Damit entstand die Church-Turing-These.

Implikationen

Falls die These wahr ist, kann es kein Rechnermodell geben, das mehr als die bisherigen Modelle berechnen kann. Insbesondere ist ein Computer ein solches Rechnermodell, somit kann auf ihm theoretisch jeder Algorithmus ausgeführt werden, vorausgesetzt genügend Speicherplatz ist vorhanden. Es ist dann nicht möglich eine Rechenmaschine zu bauen, die mehr berechnen kann als ein Computer bereits kann. Da viele Programmiersprachen ebenfalls turing-vollständig sind, kann man jeglichen Algorithmus mittels eines Quelltexts dieser Sprachen ausdrücken. Insbesondere können sich verschiedene Rechenmodelle gegenseitig simulieren.

Falls die These falsch ist, gelten die genannten Implikationen nicht. Eine Widerlegung der These wäre mit der Konstruktion eines Hypercomputers möglich, der Berechnungen ausführen kann, die auf einer Turingmaschine nicht möglich sind.

Erweiterte Churchsche These

Die erweiterte Churchsche These geht noch einen Schritt weiter. Sie lautet:

Für je zwei Rechnermodelle R1 und R2 gibt es ein Polynom p, so dass t Rechenschritte auf Modell R1 bei Eingabe der Länge n durch p(t,n) Rechenschritte auf Modell R2 simuliert werden können.

Weitere Algorithmenbegriffe

Siehe auch

Literatur


Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

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

  • Church History —     Ecclesiastical History     † Catholic Encyclopedia ► Ecclesiastical History     I. NATURE AND OFFICE     Ecclesiastical history is the scientific investigation and the methodical description of the temporal development of the Church… …   Catholic encyclopedia

  • Church of Christ, Scientist — Classification Christian Geographical areas United States Founder Mary Baker Eddy Origin 1879 Boston, Massachusetts, USA Congregations …   Wikipedia

  • Church–Turing thesis — Church s thesis redirects here. For the constructive mathematics assertion, see Church s thesis (constructive mathematics). In computability theory, the Church–Turing thesis (also known as the Church–Turing conjecture, Church s thesis, Church s… …   Wikipedia

  • Von Ormy, Texas — Von Ormy (pronEng|ˌvahn AHR mi) is a city located in southwest Bexar County, Texas, United States. It has been known as Von Ormy since the late 1880s. Prior to 1880, the community was known as Mann s Crossing, Garza s Crossing [cite… …   Wikipedia

  • Church of Antioch —     The Church of Antioch     † Catholic Encyclopedia ► The Church of Antioch     (Antiocheia, Antiochia)     I. ORIGIN AND HISTORY OF THE CITY     Of the vast empire conquered by Alexander the Great many states were formed, one of which… …   Catholic encyclopedia

  • Church of the Immaculate Conception (Saint Mary-of-the-Woods, Indiana) — Church of the Immaculate Conception …   Wikipedia

  • Church of the Teutonic Order, Vienna — Church of Saint Elisabeth of Hungary entrance of the mother church of the Teutonic Order Basic information Location Vienna, Austria Geographic coordinates …   Wikipedia

  • Von Worndle Family —     Von Wörndle Family     † Catholic Encyclopedia ► Von Wörndle Family     Philip von Wörndle     Of Adelsfried and Weierburg, major of a Tyrolese rifle corps, commandant in the militia reserve, b. at Hotting Innsbruck, 9 July, 1755; d. at Linz …   Catholic encyclopedia

  • Von G. Keetch — (born March 17th, 1960) is a Utah based lawyer. He is a sharehold in the lawfirm of Kirton and McConkie and a member of the Constitutional, Religious and Appellate Practice section for that law firm.Keetch is a member of The Church of Jesus… …   Wikipedia

  • Church of Saint Maurice (Ebersmunster) — Abbatiale Saint Maurice d Ebersmunster Église Saint Maurice d Ebersmunster Country France Denomination Roman Catholic Ch …   Wikipedia

Share the article and excerpts

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