In der Berechenbarkeitstheorie ist die Kirch-Turing-These (auch bekannt als die Kirch-Turing-Vermutung, die These der Kirche, die Vermutung der Kirche und die These von Turing) eine vereinigte Hypothese ("These") über die Natur von Funktionen, deren Werte effektiv berechenbar sind; oder, in moderneren Begriffen, Funktionen, deren Werte algorithmisch berechenbar sind. In einfachen Begriffen stellt die Kirch-Turing-These fest, dass "alles algorithmisch Berechenbares durch eine Maschine von Turing berechenbar ist."

Mehrere Versuche wurden in der ersten Hälfte des 20. Jahrhunderts gemacht, den Begriff der Berechenbarkeit zu formalisieren:

• Amerikanische Kirche des Mathematikers Alonzo hat eine Methode geschaffen, um Funktionen zu definieren, hat den λ-calculus, genannt
• Britischer Mathematiker Alan Turing hat ein theoretisches Modell für eine Maschine, jetzt genannt eine universale Maschine von Turing geschaffen, die Berechnungen von Eingängen, ausführen konnte
• Kirche, zusammen mit dem Mathematiker Stephen Kleene und Logiker J.B. Rosser hat eine formelle Definition einer Klasse von Funktionen geschaffen, deren Werte durch recursion berechnet werden konnten.

Wie man

zeigte, waren alle drei rechenbetonten Prozesse (recursion, der λ-calculus und die Maschine von Turing) gleichwertig — alle drei Annäherungen definieren dieselbe Klasse von Funktionen. Das hat Mathematiker und Computerwissenschaftler dazu gebracht zu glauben, dass das Konzept der Berechenbarkeit durch diese drei gleichwertigen Prozesse genau charakterisiert wird. Informell stellt die Kirch-Turing-These dass fest, wenn eine Methode (Algorithmus) besteht, um eine Berechnung auszuführen, dann kann dieselbe Berechnung auch durch eine Maschine von Turing (sowie nach einer rekursiv definierbaren Funktion, und nach einem λ-function) ausgeführt werden.

Die Kirch-Turing-These ist eine Behauptung, die die Natur der Berechnung charakterisiert und nicht formell bewiesen werden kann. Wenn auch die drei Prozesse über dem bewiesenen erwähnt haben, um, die grundsätzliche Proposition hinter der These — der Begriff dessen gleichwertig zu sein, was es für eine Funktion bedeutet", (berechenbar) "effektiv berechenbar zu sein —, ist "ein etwas vager intuitiver ein". So bleibt die "These" eine Hypothese.

Ungeachtet der Tatsache dass es nicht formell bewiesen werden kann, hat die Kirch-Turing-These jetzt nah-universale Annahme.

Formelle Behauptung

Rosser 1939 Adressen der Begriff der "wirksamen Berechenbarkeit" wie folgt: "Klar setzt die Existenz des CC und der FERNSTEUERUNG (die Beweise der Kirche und Rossers) eine genaue Definition von "wirksamen" voraus. "Wirksame Methode" wird hier im ziemlich speziellen Sinn einer Methode verwendet, deren jeder Schritt genau vorher bestimmt wird, und der gewiss die Antwort in einer begrenzten Zahl von Schritten erzeugen wird". So wird das mit dem Adverb adjektivische "wirksame" gewissermaßen "1a verwendet: Das Produzieren einer entschiedenen, entscheidenden oder gewünschten Wirkung", und "fähig dazu, ein Ergebnis zu erzeugen".

Im folgenden werden die Wörter "effektiv berechenbar" "erzeugt durch jeder intuitiv 'wirksam' bedeuten bedeutet beliebig", und "effektiv berechenbar" wird "erzeugt durch eine Turing-Maschine oder gleichwertiges mechanisches Gerät" bedeuten. 1939 von Turing "Definitionen" ist eigentlich dasselbe:

: "+We soll den Ausdruck "berechenbare Funktion" verwenden, um eine Funktion zu bedeuten, die durch eine Maschine berechenbar ist, und wir lassen "effektiv berechenbar" beziehen sich auf die intuitive Idee ohne besondere Identifizierung mit irgendwelchen dieser Definitionen." (vgl der Kommentar + in Turing 1939 (sein Ordnungspapier) in Davis 1965:160).

Die These kann wie folgt festgesetzt werden:

:Every effektiv berechenbare Funktion ist eine berechenbare Funktion.

Turing hat es dieser Weg festgesetzt:

: "Es wurde festgestellt..., dass 'eine Funktion effektiv berechenbar ist, wenn seine Werte durch etwas rein mechanischen Prozess gefunden werden können.' Wir können das wörtlich nehmen, verstehend, dass durch rein mechanischen Prozess-denjenigen, der durch eine Maschine ausgeführt werden konnte. Die Entwicklung führt...... zu einer Identifizierung der Berechenbarkeit + mit der wirksamen Berechenbarkeit" (+ ist der Kommentar oben, ibd.).

Geschichte

Eines der wichtigen Probleme für Logiker war in den 1930er Jahren der Entscheidungsproblem von David Hilbert, der gefragt hat, ob es ein mechanisches Verfahren gab, um mathematische Wahrheiten von mathematischen Lügen zu trennen. Diese Suche hat verlangt, dass der Begriff "des Algorithmus" oder "der wirksamen Berechenbarkeit" unten mindestens ganz gut für die Suche befestigt wird, um zu beginnen. Aber vom wirklichen Anfang haben Kirchversuche von Alonzo mit einer Debatte begonnen, die bis jetzt weitergeht. War der Begriff der "wirksamen Berechenbarkeit" (um i) ein "Axiom oder Axiome" in einem axiomatischen System, oder (ii) bloß eine Definition zu sein, die zwei oder mehr Vorschläge, oder (iii) eine empirische Hypothese "identifiziert" hat, die durch die Beobachtung von natürlichen Ereignissen, oder (iv) oder gerade ein Vorschlag wegen des Arguments (d. h. eine "These") nachzuprüfen ist.

Um 1930-1952

Im Laufe des Studierens des Problems haben Kirche und sein Student Stephen Kleene den Begriff von λ-Definable-Funktionen eingeführt, und sie sind im Stande gewesen zu beweisen, dass mehrere große Klassen von in der Zahlentheorie oft gestoßenen Funktionen λ-definable waren. Die Debatte hat begonnen, als Kirche Kurt Gödel vorgeschlagen hat, dass man die "effektiv berechenbaren" Funktionen definieren sollte, weil der λ-definable fungiert. Gödel war jedoch nicht überzeugt und hat den Vorschlag "völlig unbefriedigend" genannt. Eher in der Ähnlichkeit mit der Kirche (ca 1934-5) hat Gödel axiomatizing der Begriff der "wirksamen Berechenbarkeit" vorgeschlagen; tatsächlich, in einem 1935-Brief an Kleene, hat Kirche dass berichtet:

: "Die einzige Idee seines [Gödel] bestand zurzeit darin, dass es in Bezug auf die wirksame Berechenbarkeit als ein unbestimmter Begriff möglich sein könnte, eine Reihe von Axiomen festzusetzen, die die allgemein akzeptierten Eigenschaften dieses Begriffs aufnehmen würden, und etwas auf dieser Basis zu tun".

Aber Gödel hat keine weitere Leitung angeboten. Schließlich würde er seinen (primitiven) recursion vorschlagen, der durch den Vorschlag von Herbrand modifiziert ist, dass Gödel in seinen 1934 Vorträgen in Princeton über NJ ausführlich berichtet hatte (Kleene und ein anderer Student J. B. Rosser die Zeichen abgeschrieben hat.). Aber "er hat nicht gedacht, dass die zwei Ideen "außer heuristisch" hinreichend identifiziert werden konnten.

Dann war es notwendig, die Gleichwertigkeit von zwei Begriffen der wirksamen Berechenbarkeit zu identifizieren und zu beweisen. Ausgestattet mit dem λ-calculus und "allgemeinem" recursion hat Stephen Kleene mit der Hilfe der Kirche und J. B. Rossers Beweise (1933, 1935) erzeugt, um zu zeigen, dass die zwei Rechnungen gleichwertig sind. Kirche hat nachher seine Methoden modifiziert, Gebrauch von Herbrand-Gödel recursion einzuschließen, und hat sich dann (1936) erwiesen, dass Entscheidungsproblem unlösbar ist: Es gibt keine verallgemeinerte "wirksame Berechnung" (Methode, Algorithmus), der bestimmen kann, ob eine Formel entweder im rekursiven - oder in λ-calculus "gültig" ist (genauer: Keine Methode zu zeigen, dass eine gut gebildete Formel eine "normale Form" hat).

Viele Jahre später in einem Brief an Davis (ca 1965) würde Gödel bekennen, dass "er, zur Zeit dieser [1934] Vorträge war, überhaupt nicht hat überzeugt, dass sein Konzept von recursion den ganzen möglichen recursions umfasst hat". Durch 1963-4 Gödel würde Herbrand-Gödel recursion und den λ-calculus für die Maschine von Turing als die Definition "des Algorithmus" oder "das mechanische Verfahren" oder "das formelle System" verleugnen.

Eine Hypothese, die zu einem natürlichen Gesetz führt?: Gegen Ende 1936 war das Papier von Alan Turing (auch Beweis, dass Entscheidungsproblem unlösbar ist) noch nicht erschienen. Andererseits war das 1936-Papier von Emil Post erschienen und wurde unabhängig der Arbeit von Turing bescheinigt. Post hat stark mit "der Identifizierung" der Kirche der wirksamen Berechenbarkeit mit dem λ-calculus und recursion nicht übereingestimmt, festsetzend:

: "Wirklich trägt die Arbeit, die bereits von der Kirche und anderen getan ist, diese Identifizierung beträchtlich außer der Arbeitshypothese-Bühne. Aber diese Identifizierung laut einer Definition zu maskieren... Rollläden wir zum Bedürfnis nach seiner dauernden Überprüfung."

Eher hat er den Begriff der "wirksamen Berechenbarkeit" als bloß eine "Arbeitshypothese" betrachtet, die durch das induktive Denken zu einem "natürlichen Gesetz" aber nicht durch "eine Definition oder ein Axiom" führen könnte. Diese Idee wurde von der Kirche "scharf" kritisiert.

So rabattierte Posten auch seinen 1936 den Vorschlag von Kurt Gödel zur Kirche in 1934-5, dass die These als ein Axiom oder Satz von Axiomen ausgedrückt werden könnte.

Turing fügt eine andere Definition hinzu, Rosser gleicht alle drei aus: Innerhalb gerade einer kurzen Zeit ist das 1936-37 Papier von Turing "Auf Berechenbaren Zahlen, mit einer Anwendung auf Entscheidungsproblem" erschienen. Darin hat er einen anderen Begriff der "wirksamen Berechenbarkeit" mit der Einführung von seinem Maschinen (jetzt bekannt als der Maschinenauszug von Turing rechenbetontes Modell) behauptet. Und in einer Probeskizze zusätzlich als ein "Anhang" zu seinem 1936-37 Papier hat Turing gezeigt, dass die Klassen von Funktionen, die durch λ-calculus und Maschinen von Turing definiert sind, zusammengefallen sind.

In ein paar Jahren (1939) würde Turing, wie Kirche und Kleene vor ihm vorschlagen, dass seine formelle Definition von mechanischem Rechenreagenz die richtige war. So, vor 1939, hatten sowohl Kirche (1934) als auch Turing (1939), keiner, Kenntnisse der Anstrengungen eines anderen habend, individuell vorgeschlagen, dass ihre "formellen Systeme" Definitionen der "wirksamen Berechenbarkeit" sein sollten; keiner hat ihre Behauptungen als Thesen eingerahmt.

Rosser (1939) hat formell die drei Begriffe als die Definitionen identifiziert:

: "Alle drei Definitionen sind gleichwertig, so ist es nicht von Bedeutung, welcher verwendet wird."

Kleene schlägt die These der Kirche vor: Das hat den offenen Ausdruck einer "These" Kleene verlassen. In seiner 1943-Zeitung haben Rekursive Prädikate und Quantifiers Kleene seine "THESE I" vorgeschlagen:

: "Diese heuristische Tatsache [allgemeine rekursive Funktionen ist]... geführte Kirche effektiv berechenbar, um die folgende These festzusetzen. Dieselbe These ist in der Beschreibung von Turing von Rechenmaschinen implizit.

:: "THESE I. Jede effektiv berechenbare Funktion (effektiv entscheidbares Prädikat) ist rekursiv [die Kursive von Kleene] allgemein

: "Seitdem eine genaue mathematische Definition des Begriffes effektiv berechenbar (effektiv entscheidbar) gewollt hat, können wir diese These... als eine Definition davon..." nehmen

:: " Bezugskirche 1936

:: " Verweisungen Turing 1936-7

Kleene setzt fort, dass zu bemerken:

: "... die These hat den Charakter einer Hypothese — ein Punkt, der durch den Posten und durch die Kirche betont ist. Wenn wir die These und sein gegenteiliges als Definition denken, dann ist die Hypothese eine Hypothese über die Anwendung der mathematischen aus der Definition entwickelten Theorie. Für die Annahme der Hypothese gibt es, wie wir, ziemlich zwingender Boden vorgeschlagen haben."

::: "(24) Bezugsposten 1936 des Postens und der Formellen Definitionen der Kirche in der Theorie von Ordinalzahlen, Fonds. Mathematik. vol 28 (1936) pp.11-21 (sieh bezüglich. #2, Davis 1965:286).

Die Kirch-Turing-These von Kleene: Ein paar Jahre später (1952) würde Kleene offen nennen, verteidigen, und die zwei "Thesen" ausdrücken und sie dann "identifizieren" (zeigen Sie Gleichwertigkeit) durch den Gebrauch seines Lehrsatzes XXX:

: "Heuristische Beweise und andere Rücksichten haben Kirche 1936 dazu gebracht, die folgende These vorzuschlagen.

:: These I. Jede effektiv berechenbare Funktion (effektiv entscheidbares Prädikat) ist rekursiv allgemein.

:Theorem XXX: "Die folgenden Klassen von teilweisen Funktionen sind koextensiv, d. h. haben dieselben Mitglieder: (a) die teilweisen rekursiven Funktionen, (b) die berechenbaren Funktionen...".

:Turing'S-These: "Die These von Turing, dass jede Funktion, die als berechenbar natürlich betrachtet würde, laut seiner Definition, d. h. durch eine seiner Maschinen berechenbar ist, ist zur These der Kirche durch den Lehrsatz XXX." gleichwertig

Spätere Entwicklungen

Ein Versuch, den Begriff der "wirksamen Berechenbarkeit" zu verstehen, hat besser Robin Gandy (der Student und Freund von Turing) 1980 dazu gebracht, Maschinenberechnung (im Vergleich mit der menschlichen Berechnung zu analysieren, die durch eine Maschine von Turing vorgespielt ist). Die Wissbegierde von Gandy über, und Analyse, "Zellautomaten" "muss das Spiel von Conway des Lebens" haben "Parallelismus" und "kristallene Automaten" ihn dazu gebracht, vier "Grundsätze (oder Einschränkungen) vorzuschlagen..., der es, jede Maschine diskutiert wird, befriedigen." Sein die meisten - wichtiges Viertel, "basiert der Grundsatz der Kausalität" auf der "begrenzten Geschwindigkeit der Fortpflanzung von Effekten und Signalen; zeitgenössische Physik weist die Möglichkeit der sofortigen Handlung in einer Entfernung zurück." Von diesen Grundsätzen und einigen zusätzlichen Einschränkungen — (1a) hat ein niedrigerer zu den geradlinigen Dimensionen von einigen der Teile, (1b) gebunden ein oberer hat zu Geschwindigkeit der Fortpflanzung (die Geschwindigkeit des Lichtes), (2) getrennter Fortschritt der Maschine, und (3) deterministisches Verhalten gebunden — er erzeugt einen Lehrsatz, dass, "Was durch ein Gerät berechnet werden kann, das Grundsätze befriedigt, ist I-IV berechenbar.".

Gegen Ende der 1990er Jahre hat Wilfried Sieg die Begriffe von Turing und Gandys der "wirksamen Berechenbarkeit" mit der Absicht analysiert, "den informellen Begriff zu schärfen, seine allgemeinen Eigenschaften axiomatisch formulierend, und das axiomatische Fachwerk untersuchend". In seinen 1997 und 2002 Geschenken von Sieg eine Reihe von Einschränkungen auf das Verhalten eines computor — "ein menschlicher Rechenagent, der mechanisch weitergeht"; diese Einschränkungen nehmen ab zu:

• "(B.1) (Boundedness) gibt Es einen festen hat zur Zahl von symbolischen Konfigurationen gebunden, die ein computor sofort anerkennen kann.
• "(B.2) (Boundedness) gibt Es einen festen hat zur Zahl von inneren Staaten gebunden, in denen ein computor sein kann.
• "(L.1) (Gegend) Ein computor kann nur Elemente einer beobachteten symbolischen Konfiguration ändern.
• "(L.2) (Gegend) Ein computor kann Aufmerksamkeit von einer symbolischer Konfiguration bis einen anderen auswechseln, aber die neuen beobachteten Konfigurationen müssen innerhalb einer begrenzten Entfernung der sofort vorher beobachteten Konfiguration sein.
• "(D) (Determinacy) sofort erkennbar (sub-) bestimmt Konfiguration einzigartig den folgenden Berechnungsschritt (und id [sofortige Beschreibung])"; festgesetzt ein anderer Weg: "Ein innerer Staat eines computor zusammen mit der beobachteten Konfiguration befestigt einzigartig den folgenden Berechnungsschritt und den folgenden inneren Staat."

Die Sache bleibt in der aktiven Diskussion innerhalb der akademischen Gemeinschaft.

Erfolg der These

Andere Formalismen (außer recursion, dem λ-calculus und der Maschine von Turing) sind vorgeschlagen worden, um wirksame Berechenbarkeit/Berechenbarkeit zu beschreiben. Stephen Kleene (1952) fügt zur Liste die Funktionen "reckonable im System S" Kurt Gödels 1936 hinzu, und Emil Post (1943, 1946) "kanonisch [hat auch normal] Systeme genannt". In den 1950er Jahren haben Hao Wang und Martin Davis außerordentlich das Ein-Band-Turing-Maschinenmodell vereinfacht (sieh Post-Turing Maschine). Marvin Minsky hat das Modell zu zwei oder mehr Bändern ausgebreitet und hat außerordentlich die Bänder in "unten Schalter" vereinfacht, die Melzak und Lambek weiter darin entwickelt haben, was jetzt als das Gegenmaschinenmodell bekannt ist. Gegen Ende der 1960er Jahre und Anfang Forscher der 1970er Jahre hat das Gegenmaschinenmodell in die Register-Maschine, einen nahen Vetter zum modernen Begriff des Computers ausgebreitet. Andere Modelle schließen combinatory Logik und Algorithmen von Markov ein. Gurevich fügt das Zeigestock-Maschinenmodell von Kolmogorov und Uspensky (1953, 1958) hinzu:" ... sie haben sich... gerade überzeugen wollen, dass es keine Weise gibt, den Begriff der berechenbaren Funktion zu erweitern."

Alle diese Beiträge sind mit Beweisen verbunden, dass die Modelle zur Maschine von Turing rechenbetont gleichwertig sind; wie man sagt, sind solche Modelle abgeschlossener Turing. Weil alle diese verschiedenen Versuche des Formalisierens des Konzepts der "wirksamen Berechenbarkeit/Berechenbarkeit" gleichwertige Ergebnisse nachgegeben haben, wird es jetzt allgemein angenommen, dass die Kirch-Turing-These richtig ist. Tatsächlich hat Gödel (1936) etwas Stärkeres vorgeschlagen als das; er hat bemerkt, dass es etwas "Absolutes" über das Konzept "reckonable in S" gab:

: "Es kann auch gezeigt werden, dass eine Funktion, die ['reckonable'] in einem der Systeme S, oder sogar in einem System des transfiniten Typs berechenbar ist, bereits [reckonable] in S berechenbar ist. So ist das Konzept 'berechenbar' ['reckonable'] in einem bestimmten bestimmten 'absoluten' Sinn, während praktisch alle anderen vertrauten metamathematical Konzepte (z.B nachweisbar, definierbar, usw.) ganz im Wesentlichen vom System abhängen, zu dem sie" definiert werden

Informeller Gebrauch in Beweisen

Beweise in der Berechenbarkeitstheorie rufen häufig die Kirch-Turing-These auf eine informelle Weise an, die Berechenbarkeit von Funktionen zu gründen, während sie (häufig sehr lange) Details vermeiden, die an einem strengen, formellen Beweis beteiligt würden. Um festzustellen, dass eine Funktion durch die Maschine von Turing berechenbar ist, wird es gewöhnlich genügend betrachtet, eine informelle englische Beschreibung dessen zu geben, wie die Funktion effektiv geschätzt werden, und dann "Durch die Kirch-Turing-These" aufhören kann, dass die Funktion Turing berechenbar (gleichwertig teilweise rekursiv) ist.

Dirk van Dalen (in Gabbay 2001:284) führt das folgende Beispiel wegen der Veranschaulichung dieses informellen Gebrauches der Kirch-Turing-These an:

:EXAMPLE: Jeder unendliche RE-Satz enthält einen unendlichen rekursiven Satz.

:Proof: Lassen Sie A unendlicher RE sein. Wir verzeichnen die Elemente effektiv, n, n, n, n...

:From diese Liste ziehen wir eine zunehmende Subliste heraus: Gestellte m=n, danach begrenzt viele Schritte wir finden einen n solch, dass n> M, stellen m=n. Wir wiederholen dieses Verfahren, um m> M zu finden, usw. gibt das eine wirksame Auflistung der Teilmenge B = {M, M, M nach...} A, mit dem Eigentum M.

:Claim. B ist entscheidbar. Da, um k in B zu prüfen, den wir wenn k=m für einige ich überprüfen müssen. Da die Folge der M zunimmt, müssen wir an den meisten k+1 Elementen der Liste erzeugen und sie mit k vergleichen. Wenn keiner von ihnen k, dann k nicht in B gleich ist. Da dieser Test wirksam ist, ist B entscheidbar und durch die These der Kirche, rekursiv.

(Betonung hinzugefügt). Um das obengenannte Beispiel völlig streng zu machen, würde man eine Turing Maschine oder λ-function sorgfältig bauen, oder sorgfältig recursion Axiome anrufen, oder bestenfalls, klug verschiedene Lehrsätze der Berechenbarkeitstheorie anrufen müssen. Aber weil der Berechenbarkeitstheoretiker glaubt, dass Berechenbarkeit von Turing richtig gewinnt, was effektiv geschätzt werden kann, und weil ein wirksames Verfahren in Englisch dargelegt wird, den Satz B zu entscheiden, akzeptiert der Berechenbarkeitstheoretiker das als Beweis, dass der Satz tatsächlich rekursiv ist.

Als Faustregel sollte die Kirch-Turing-These nur angerufen werden, um Beweise in Fällen zu vereinfachen, wo der Schriftsteller dazu fähig sein würde und annimmt, dass die Leser auch zu, leicht (aber nicht notwendigerweise ohne Langweiligkeit) das Produzieren eines strengen Beweises fähig sind, wenn man gefordert würde.

Schwankungen

Der Erfolg der Kirch-Turing-These hat Schwankungen der These aufgefordert, vorgeschlagen zu werden. Zum Beispiel, die Staaten der Physischen Kirch-Turing-These (PCTT):

:: "Gemäß Physischem CTT sind alle physisch berechenbaren Funktionen" Turing-berechenbar

Die Kirch-Turing-These sagt nichts über die Leistungsfähigkeit, mit der das-Modell der Berechnung einen anderen vortäuschen kann. Es ist zum Beispiel bewiesen worden, dass (Mehrband) universale Maschine von Turing nur einen logarithmischen Verlangsamungsfaktor im Simulieren jeder Maschine von Turing erträgt. Kein solches Ergebnis ist im Allgemeinen für ein willkürliches, aber angemessenes Modell der Berechnung bewiesen worden. Eine Schwankung der Kirch-Turing-These, die dieses Problem richtet, ist die Durchführbarkeitsthese oder (Klassische) mit der Kompliziertheit theoretische Kirch-Turing-These (SCTT), der nicht wegen der Kirche oder Turing ist, aber eher allmählich in der Entwicklung der Kompliziertheitstheorie begriffen wurde. Es setzt fest:

: "Eine probabilistic Maschine von Turing kann jedes realistische Modell der Berechnung effizient vortäuschen."

Das Wort 'effizient' hier bedeutet bis zu den polynomisch-maligen Verminderungen. Diese These wurde Rechenbetonte mit der Kompliziertheit theoretische Kirch-Turing-These von Ethan Bernstein und Umesh Vazirani (1997) ursprünglich genannt. Die mit der Kompliziertheit theoretische Kirch-Turing-These postuliert dann das alle 'angemessenen' Modelle der Berechnung geben dieselbe Klasse von Problemen nach, die in der polynomischen Zeit geschätzt werden können. Die Vermutung annehmend, dass probabilistic polynomische Zeit (BPP) deterministischer polynomischer Zeit (P) gleichkommt, ist das Wort 'probabilistic' in der mit der Kompliziertheit theoretischen Kirch-Turing-These fakultativ. Eine ähnliche These, genannt die Invariant These, wurde von Cees F. Slot und Peter van Emde Boas eingeführt. Es setzt fest:" Angemessene" Maschinen können einander innerhalb polynomisch begrenzt oberirdisch rechtzeitig und ein unveränderlicher Faktor oben im Raum vortäuschen. Die These ist ursprünglich in einer Zeitung an STOC '84 erschienen, der das erste Papier war, um zu zeigen, dass polynomisch-malig oberirdisch und Unveränderlich-Raum-oberirdisch gleichzeitig für eine Simulation einer Zufälligen Zugriffsmaschine auf einer Maschine von Turing erreicht werden konnte.

Wenn Produktionsskala-Quant-Computer gebaut werden können, konnten sie die mit der Kompliziertheit theoretische Kirch-Turing-These ungültig machen, da sie auch vermutet wird, dass Quant-Polynom-Zeit (BQP) größer ist als BPP. Mit anderen Worten gibt es effiziente Quant-Algorithmen, die Aufgaben durchführen, die, wie man bekannt, effiziente probabilistic Algorithmen nicht haben; zum Beispiel, ganze Factoring-Zahlen. Sie würden die ursprüngliche Kirch-Turing-These nicht jedoch ungültig machen, da ein Quant-Computer immer durch eine Maschine von Turing vorgetäuscht werden kann, aber sie würden die klassische mit der Kompliziertheit theoretische Kirch-Turing-These aus Leistungsfähigkeitsgründen ungültig machen. Folglich, das Quant mit der Kompliziertheit theoretische Kirch-Turing-Thesenstaaten:

: "Ein Quant Maschine von Turing kann jedes realistische Modell der Berechnung effizient vortäuschen."

Eugene Eberbach und Peter Wegner behaupten, dass die Kirch-Turing-These manchmal zu weit gehend, interpretiert wird

das Angeben "der breiteren Behauptung, dass Algorithmen genau gewinnen

was geschätzt werden kann, ist ungültig". Sie behaupten, dass Formen der durch die These nicht gewonnenen Berechnung heute, wichtig

sind

Begriffe, die sie super-Turing Berechnung nennen.

Philosophische Implikationen

Die Kirch-Turing-These hat einige tiefe Implikationen für die Philosophie der Meinung; jedoch schließen viele der philosophischen Interpretationen der These grundlegende Missverständnisse der Thesenbehauptung ein. B. Jack Copeland stellt fest, dass es eine offene empirische Frage ist, ob es wirkliche deterministische physische Prozesse gibt, die sich im langen Lauf, Simulation durch eine Maschine von Turing entziehen; außerdem stellt er fest, dass es eine offene empirische Frage ist, ob irgendwelche solche Prozesse am Arbeiten des menschlichen Gehirns beteiligt werden. Es gibt auch einige wichtige geöffnete Fragen, die die Beziehung zwischen der Kirch-Turing-These und Physik und der Möglichkeit der Hyperberechnung bedecken. Wenn angewandt, auf die Physik hat die These mehrere mögliche Bedeutungen:

1. Das Weltall ist zu einer Maschine von Turing gleichwertig; so ist Computerwissenschaft nichtrekursiver Funktionen physisch unmöglich. Das ist die Starke Kirch-Turing-These genannt worden und ist ein Fundament der Digitalphysik.
2. Das Weltall ist zu einer Maschine von Turing nicht gleichwertig (d. h. die Gesetze der Physik sind nicht Turing-berechenbar), aber incomputable physische Ereignisse sind nicht "harnessable" für den Aufbau eines Hypercomputers. Zum Beispiel könnte ein Weltall, in das Physik mit reellen Zahlen im Vergleich mit berechenbarem reals verbunden ist, in diese Kategorie fallen.
3. Das Weltall ist ein Hypercomputer, und es ist möglich, reale Geräte zu bauen, um dieses Eigentum anzuspannen und nichtrekursive Funktionen zu berechnen. Zum Beispiel ist es eine geöffnete Frage, ob das ganze Quant mechanische Ereignisse sind Turing-berechenbar, obwohl es bekannt ist, dass strenge Modelle wie Quant Maschinen von Turing zu deterministischen Maschinen von Turing gleichwertig sind. (Sie sind nicht notwendigerweise effizient gleichwertig; sieh oben.) hat John Lucas und, berühmter, Roger Penrose vorgeschlagen, dass der Menschenverstand das Ergebnis einer Art Quants mechanisch erhöhte, "nichtalgorithmische" Berechnung sein könnte, obwohl es keine wissenschaftlichen Beweise für diesen Vorschlag gibt.

Es gibt viele andere technische Möglichkeiten, die draußen oder zwischen diesen drei Kategorien fallen, aber diese dienen, um die Reihe des Konzepts zu illustrieren.

Nichtberechenbare Funktionen

Man kann Funktionen formell definieren, die nicht berechenbar sind. Ein weithin bekanntes Beispiel solch einer Funktion ist die Beschäftigte Biber-Funktion. Diese Funktion nimmt einen Eingang n und gibt die größte Zahl von Symbolen zurück, die eine Maschine von Turing mit N-Staaten vor dem Halt, wenn geführt, ohne Eingang drucken kann. Entdeckung eines oberen hat zur beschäftigten Biber-Funktion gebunden ist zum Beheben des stockenden Problems, ein Problem gleichwertig, das bekannt ist, durch Maschinen von Turing unlösbar zu sein. Da die beschäftigte Biber-Funktion durch Maschinen von Turing nicht geschätzt werden kann, behauptet die Kirch-Turing-These, dass diese Funktion durch keine Methode effektiv geschätzt werden kann. Weil mehr Information den Artikel beschäftigter Biber sieht.

Mehrere rechenbetonte Modelle berücksichtigen die Berechnung (des Kirch-Turing) nichtberechenbare Funktionen. Diese sind als bekannt

Hypercomputer.

Mark Burgin

behauptet, dass superrekursive Algorithmen wie induktive Maschinen von Turing die Kirch-Turing-These widerlegen. Sein Argument verlässt sich auf eine Definition des Algorithmus, der breiter ist als der gewöhnliche, so dass nichtberechenbare bei einigen induktiven Maschinen von Turing erhaltene Funktionen berechenbar genannt werden. Diese Interpretation der Kirch-Turing-These unterscheidet sich von der Interpretation, die allgemein in der Berechenbarkeitstheorie akzeptiert ist, die oben besprochen ist. Das Argument, dass superrekursive Algorithmen tatsächlich Algorithmen im Sinne der Kirch-Turing-These sind, hat breite Annahme innerhalb der Berechenbarkeitsforschungsgemeinschaft nicht gefunden.

Siehe auch

• Die These der Kirche in der konstruktiven Mathematik
• Berechenbarkeitslogik
• Berechenbarkeitstheorie
• Entscheidbarkeit
• Geschichte der Kirch-Turing-These
• Hypercomputer
• Superrekursiver Algorithmus
• Church-Turing-Deutsch-Grundsatz, der feststellt, dass jeder physische Prozess durch ein universales Rechengerät vorgetäuscht werden kann

Kommentare

• Schließt ursprüngliche Vorträge von Gödel, Kirche, Turing, Rosser, Kleene und in dieser Abteilung erwähntem Posten ein.
• Zitiert von Kleene (1952) als "sterben Über Lāange von Beweisen", in der Mathematik von Ergebnisse eines. Koll, usw.
• Nachgedruckt im Unentscheidbaren, p. 255ff. Kleene hat seine Definition "allgemeinen recursion" raffiniert und ist in seinem Kapitel "12 weitergegangen. Algorithmische Theorien", um "These I" (p zu postulieren. 274); er würde später diese These (in Kleene 1952:300) wiederholen und es "die These der Kirche" (Kleene 1952:317) (d. h., die Kirchthese) nennen.

• (und)

Links

.

• Berechnung in Physischen Systemen Eine umfassende philosophische Behandlung von relevanten Problemen.