Church-Turing-These - LinkFang.de





Church-Turing-These


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 stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.“[1]

Diese These ist nicht beweisbar, da der Begriff „intuitiv berechenbare Funktion“ nicht exakt formalisiert werden kann. Man versteht darunter alle Funktionen, die prinzipiell auf irgendeine Weise berechnet 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.

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 gäbe 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 (z. B. Registermaschinen, Turingmaschinen, GOTO-Programme, WHILE-Programme, µ-rekursive Funktionen) 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 [math]R_1[/math] und [math]R_2[/math] gibt es ein Polynom [math]p[/math], sodass [math]t[/math] Rechenschritte auf Modell [math]R_1[/math] bei Eingabe der Länge [math]n[/math] durch [math]p(t,n)[/math] Rechenschritte auf Modell [math]R_2[/math] simuliert werden können.

Weitere Algorithmenbegriffe

Siehe auch

Literatur

Society. Series 2, Bd. 42, 1936, ISSN 0024-6115 , S. 230–265.

Einzelnachweise

  1. Dirk W. Hoffmann: Theoretische Informatik. 2., aktualisierte Auflage. Carl Hanser Fachbuchverlag, München 2011, ISBN 978-3-446-42639-9, S. 308.
lt:Tiuringo mašina#Tiuringo tezė

Kategorien: Alan Turing | Berechenbarkeitstheorie | Komplexitätstheorie | Automatentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Church-Turing-These (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.