WikiDer > Church-Turing-Hypothese

Das Church-Turing-Hypothese (Englisch: Church-Turing-These) ist ein Satz im Berechenbarkeitstheorie, formuliert von Alonzo-Kirche und Alan Turing. Diese Aussage ist eigentlich a Hypothese, da dies nie bewährt werden können. Einige abgeleitete Hypothesen wurden sogar widerlegt.

Der Vorschlag

Die Aussage lautet: Jede mögliche Berechnung kann durch a Algorithmus auf einen Turing Maschine durchgeführt werden, sofern genug vorhanden Erinnerung und Zeit ist verfügbar.

Im Allgemeinen werden folgende Bedingungen an den Algorithmus gestellt:

• Der Algorithmus besteht aus einer endlichen Anzahl von klar definierten Anweisungen.
• Der Algorithmus gibt eine Antwort innerhalb einer endlichen Anzahl von Schritten.
• Der Algorithmus kann mit Stift und Papier durchgeführt werden. (in der Theorie)
• Es sind keine Kenntnisse erforderlich, außer wie die Anweisungen ausgeführt werden.

Das alles scheint offensichtlich, ist es aber nicht formell genug. Was sind zum Beispiel jede mögliche Berechnung, ein klar definierte Anweisung und der Kenntnisse über die Durchführung der Anweisungen?

Aufgrund dieser Mehrdeutigkeiten ist diese Behauptung schwer zu beweisen oder zu widerlegen.

Ableitungssätze

Physische Kirche-Turing-These (PCTT): Jede physikalisch berechenbare Funktion kann von einer Turingmaschine berechnet werden.

Diese Behauptung wurde möglicherweise entlarvt, als Willem Fouché entdeckte im Jahr 2002, dass a Turing Maschine kann sich den Werten für eine eindimensionale wahrscheinlich nicht nähern braunes Uhrwerk auf rational Punkte in der Zeit.

Strong Church-Turing-These (SCTT): Jedes „vernünftige“ Berechnungsmodell kann durch eine probabilistische Turingmaschine effizient simuliert werden.

Es scheint jedoch Hinweise darauf zu geben, dass dies nicht stimmt: a Nummer kann effizient sein faktorisiert auf einen Quantencomputer, aber es wurde noch kein Algorithmus gefunden, der dies mit einer Turing-Maschine tun kann. Es ist jedoch noch nicht bewiesen, dass dieser Algorithmus nicht existiert.

Siehe die Kategorie Turing-Maschinen von Wikimedia Commons für Mediendateien zu diesem Thema.