Berechenbare Funktionen und die Church-Turing-These

Berechenbare Funktionen sind solche, die ein mechanisches Verfahren auswerten kann, und die Church-Turing-These identifiziert diesen informellen Begriff mit mehreren präzisen mathematischen Modellen, die alle dieselbe Klasse definieren.

Definition

Eine Funktion ist berechenbar, wenn eine Turingmaschine, oder äquivalent eine partiell rekursive Definition, ihre Ausgabe für jede Eingabe erzeugt, für die sie definiert ist; die Church-Turing-These besagt, dass diese mathematisch präzise Klasse mit der intuitiven Klasse der effektiv berechenbaren Funktionen übereinstimmt.

Scope

Dieses Thema behandelt Turingmaschinen, die partiell rekursiven Funktionen, die aus Basisfunktionen durch Komposition, primitive Rekursion und Minimierung aufgebaut sind, den Lambda-Kalkül und Registermaschinen, die Beweise, dass diese Modelle äquivalent sind, universelle Maschinen und die Church-Turing-These, dass sie alle effektiven Berechnungen erfassen.

Core questions

• Was ist eine Turingmaschine und wie definiert sie eine Berechnung?
• Wie werden die partiell rekursiven Funktionen aus grundlegenden Operationen erzeugt?
• Warum definieren alle vernünftigen Berechnungsmodelle dieselben Funktionen?
• Welchen Status und welche Bedeutung hat die Church-Turing-These?

Key theories

Turingmaschinenmodell

Eine Turingmaschine ist ein endlicher Automat, der auf einem unbegrenzten Band arbeitet, und die Funktionen, die sie berechnet, formalisieren den Begriff eines Algorithmus in Bezug auf elementare Symbolmanipulation.

Äquivalenz der Modelle

Turingmaschinen, die partiell rekursiven Funktionen, der Lambda-Kalkül und Registermaschinen berechnen alle genau dieselbe Klasse von Funktionen, was die Robustheit des Begriffs der Berechenbarkeit demonstriert.

Universelle Maschine und Aufzählung

Es gibt eine universelle Turingmaschine, die jede Maschine simuliert, wenn ihr Code gegeben ist, sodass berechenbare Funktionen effektiv aufgezählt und als Daten behandelt werden können, die Grundlage für Selbstreferenz-Ergebnisse.

Clinical relevance

Der Begriff einer berechenbaren Funktion ist die Grundlage der theoretischen Informatik: Die universelle Maschine nimmt den speicherprogrammierbaren Computer vorweg, die Äquivalenz der Modelle rechtfertigt eine einzige robuste Definition des Algorithmus, und der Rahmen liefert die präzise Umgebung, in der Unentscheidbarkeit und Komplexität untersucht werden.

History

1936 definierte Church die effektive Berechenbarkeit über den Lambda-Kalkül und Turing über seine Maschinen, und die beiden Begriffe wurden bald als äquivalent zu Kleenes rekursiven Funktionen erwiesen. Die daraus resultierende Church-Turing-These wurde zur akzeptierten Definition des Algorithmus, und Turings universelle Maschine wurde zu einem konzeptionellen Vorläufer des Allzweckcomputers.

Key figures

• Alan Turing
• Alonzo Church
• Stephen Cole Kleene
• Emil Post

Seminal works

• cutland1980
• turing1936
• sipser2013

Frequently asked questions

Sind einige Funktionen nicht berechenbar?

Ja. Da Programme aufgezählt werden können, Funktionen aber nicht, zeigt ein Zählargument, dass die meisten Funktionen nicht berechenbar sind, und spezifische Beispiele wie die Haltefunktion sind nachweislich unberechenbar. Berechenbarkeit ist eine echte Einschränkung dafür, welche Funktionen Algorithmen auswerten können.

Begrenzt die Church-Turing-These, was Computer tun können?

Sie besagt, dass kein Modell effektiver Berechnung die Klasse der berechenbaren Funktionen über Turingmaschinen hinaus erweitert. Schnellere Hardware oder andere Architekturen ändern die Effizienz, nicht aber die Grenze dessen, was prinzipiell berechenbar ist, sodass die These eine absolute Grenze für die algorithmische Lösbarkeit setzt.