Was würde es bedeuten, die These von Church-Turing zu widerlegen?

83

Entschuldigung für den eingängigen Titel. Ich möchte verstehen, was man tun muss, um die These von Church-Turing zu widerlegen. Irgendwo, wo ich lese, ist es mathematisch unmöglich, das zu tun! Warum?

Turing, Rosser usw. verwendeten unterschiedliche Begriffe, um zu unterscheiden zwischen: "was kann berechnet werden" und "was kann von einer Turing-Maschine berechnet werden".

Die diesbezügliche Definition von Turing aus dem Jahr 1939 lautet: "Wir werden den Ausdruck" berechenbare Funktion "verwenden, um eine von einer Maschine berechenbare Funktion zu bezeichnen, und wir lassen" effektiv berechenbar "auf die intuitive Idee verweisen, ohne sich mit einer dieser Definitionen zu identifizieren."

Die Church-Turing-These kann also wie folgt formuliert werden: Jede effektiv berechenbare Funktion ist eine berechenbare Funktion.

Wie wird der Beweis aussehen, wenn man diese Vermutung widerlegt?

András Salamon
quelle
1
Überprüfen Sie den Anhang in diesem großen (aber schwer zu lesen) Papier von L. Levin arxiv.org/PS_cache/cs/pdf/0203/0203029v16.pdf
user2471

Antworten:

5

Die Church-Turing-These wurde für alle praktischen Zwecke bewiesen.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.146.5402

Dershowitz und Gurevich, Bulletin of Symbolic Logic, 2008.

(Diese Literaturstelle diskutiert die Geschichte der Arbeit von Kirche und Turing und spricht sich für eine Trennung zwischen "Church's Thesis" und "Turing's Thesis" als eindeutige logische Behauptungen aus. Dann beweisen sie beide innerhalb einer intuitiven Axiomatisierung der Berechenbarkeit.)

Aaron Sterling
quelle
23
Ich bin ein bisschen besorgt über diese Antwort. Es mag den Menschen den falschen Eindruck vermitteln, dass die These von Church-Turing bewiesen wurde, obwohl dies nicht der Fall ist (und ich würde mir vorstellen, dass die meisten Leute denken, dass dies nicht bewiesen werden kann).
Emil
5
Dies wird mein letzter Kommentar hier sein, aber ich denke, Sie möchten sich vielleicht fragen, warum eine solche Site notwendig ist, wenn wir uns nur die Lehrbücher ansehen müssen. Arora und Barak sind großartige Forscher, aber keine Logiker oder Komplexitätstheoretiker (sie haben sowieso ein Komplexitätsbuch geschrieben, obwohl dies nicht ihr Hauptforschungsgebiet war) oder Experten für Programmiersprachensemantik (was die ursprüngliche Motivation für war) abstrakte Zustandsmaschinen). Konventionelle Weisheit ist nicht unbedingt wahr, und am Ende des Tages müssen wir für uns selbst denken.
Aaron Sterling
8
Wenn Dershowitz und Gurevich die Thesen von Church und Turing bewiesen haben, dann haben sie auch bewiesen, dass wir in Zukunft keinen Computer bauen können, der unendlich viele Rechenschritte in endlicher Zeit ausführt, siehe zum Beispiel arxiv.org/abs/gr-qc/ 0104023, in der solche Möglichkeiten erörtert werden.
Andrej Bauer
50
Normalerweise ist die Church-Turing-These kein formaler Satz, der bewiesen werden kann. Es ist eine wissenschaftliche Hypothese, so dass sie in dem Sinne "widerlegt" werden kann, dass sie fälschbar ist. Jeder "Beweis" muss eine Definition der Berechenbarkeit enthalten, und der Beweis ist nur so gut wie diese Definition. Ich bin sicher, Dershowitz-Gurevich hat einen guten Beweis, aber die eigentliche Frage ist, ob die Definition wirklich alles abdeckt, was berechenbar ist. Antworten auf "Kann es widerlegt werden?" zu sagen "es wurde bewiesen" ist irreführend. Es wurde unter einer vernünftigen (fälschbaren!) Definition der Berechenbarkeit bewiesen.
Ryan Williams
47
Die Arbeit von Dershowitz-Gurevich sagt nichts über probabilistische oder Quantenberechnung aus. Es schreibt eine Reihe von Axiomen über das Rechnen auf und beweist, dass die Church-Turing-These diese Axiome annimmt. Wir müssen diese Axiome jedoch noch rechtfertigen. Weder die Wahrscheinlichkeitsberechnung noch die Quantenberechnung werden von diesen Axiomen abgedeckt (sie geben dies für die Wahrscheinlichkeitsberechnung zu und erwähnen die Quantenberechnung überhaupt nicht), daher ist es mir ziemlich klar, dass diese Axiome in der realen Welt tatsächlich falsch sind, obwohl die Church-Turing These ist wahrscheinlich wahr.
Peter Shor
60

Es gibt einen subtilen Punkt, den ich selten in solchen Diskussionen erwähne und der meiner Meinung nach mehr Aufmerksamkeit verdient.

Angenommen, wie Andrej vorschlägt, jemand baut ein Gerät, das zuverlässig eine Funktion berechnet, die von keiner Turing-Maschine berechnet werden kann. Woher wissen wir, dass die Maschine tatsächlich f berechnet ?ff

Offensichtlich würde keine endliche Anzahl von Eingabe- / Ausgabewerten ausreichen, um zu demonstrieren, dass die Maschine berechnet, im Gegensatz zu irgendeiner anderen Turing-berechenbaren Funktion, die mit f in dieser endlichen Menge übereinstimmt . Deshalb , dass unsere Überzeugung , die Maschine Berechnung f würde auf unseren zu basieren physikalischen Theorien , wie die Maschine arbeitet. Wenn Sie sich einige der konkreten Vorschläge für Hypercomputer ansehen, werden Sie feststellen, dass sie mit Sicherheit eine hochmoderne physikalische Theorie anwenden und diese Theorie auf unendlich hochrechnenfff. Okay, gut, aber jetzt nehmen wir an, wir bauen den Hypercomputer und fragen ihn, ob eine Turing-Maschine, die nach einem Widerspruch in ZFC sucht, jemals anhalten wird. Angenommen, der Hypercomputer antwortet mit "Nein". Was schließen wir? Schliessen wir, dass der Hypercomputer die Konsistenz von ZFC "berechnet" hat? Wie können wir die Möglichkeit ausschließen, dass ZFC tatsächlich inkonsistent ist und wir gerade ein Experiment durchgeführt haben, das unsere physikalische Theorie verfälscht hat?

Ein entscheidendes Merkmal von Turings Definition ist, dass seine philosophischen Annahmen sehr schwach sind. Es setzt natürlich bestimmte einfache Merkmale unserer alltäglichen Erfahrung voraus, wie die grundlegende Stabilität der physischen Welt und die Fähigkeit, endliche Operationen auf zuverlässige, wiederholbare und überprüfbare Weise auszuführen . Diese Dinge akzeptiert jeder (also außerhalb eines Philosophie-Klassenzimmers!). Die Akzeptanz eines Hypercomputers scheint jedoch eine unendliche Extrapolation zu erforderneiner physikalischen Theorie, und all unsere Erfahrungen mit der Physik haben uns gelehrt, nicht dogmatisch über die Gültigkeit einer Theorie in einem Regime zu sein, das weit über das hinausgeht, was wir experimentell verifizieren können. Aus diesem Grund erscheint es mir sehr unwahrscheinlich, dass sich jemals ein überwältigender Konsens darüber entwickeln wird, dass ein bestimmter Hypercomputer einfach nur rechnet und nicht hypercomputert , dh nur dann etwas tut, was man als "rechnen" bezeichnen kann, wenn man ein umstrittenes philosophisches oder philosophisches Konzept akzeptiert physikalische Annahmen über unendliche Extrapolationen.

Anders ausgedrückt: Um die These von Church-Turing zu widerlegen, müsste nicht nur das von Andrej beschriebene Gerät gebaut werden, sondern es muss auch zu jedermanns Zufriedenheit bewiesen werden, dass das Gerät die beworbene Leistung erbringt. Obwohl nicht unvorstellbar, ist dies eine große Herausforderung. Für heutige Computer bedeutet die Endlichkeit der Berechnung, dass ich, wenn ich das Ergebnis der "Berechnung" eines bestimmten Computers nicht glaube, im Prinzip eine endliche Folge von Schritten auf eine völlig andere Weise ausführen kann, um das Ergebnis zu überprüfen. Diese Art des "Rückgriffs" auf gesunden Menschenverstand und endliche Verifikation ist nicht verfügbar, wenn wir Zweifel an einem Hypercomputer haben.

Timothy Chow
quelle
1
Tim, klar, die Church-Turing-These kann durch die erfolgreiche Demonstration eines Modells effektiver Berechnung widerlegt werden, das den gemeinsamen Geltungsbereich der identifizierten äquivalenten Modelle Church und Turing überschreitet. Man kann argumentieren, wie unvorstellbar das sein könnte, aber ich glaube, das ist immer noch das, was es brauchen würde. (Beachten Sie, dass ich in diesem Zusammenhang "beweisen" und "widerlegen" vermeide.)
orcmid
2
22250
6
@Neel: Im Gegenteil, ich meine genau, dass es durchaus vernünftig ist, die ausgefallene Physik eines Computers anzuzweifeln, der entweder heute existiert oder ein Hypercomputer der Zukunft. Ein Hauptgrund, warum wir die heutigen Computer tolerieren, ist, dass sie mit endlichen Berechnungen beauftragt sind, die wir im Prinzip ohne ausgefallene Physik nachahmen können. Aber bauen Sie einen Hypercomputer, dessen Korrektheit inhärent von der Extrapolation physikalischer Theorien abhängt, die unendlich weit über experimentell zugängliche Regime hinausgehen, und wir können nicht sagen, ob die Berechnung korrekt ist oder ob unsere Theorien schief gelaufen sind.
Timothy Chow
6
@orcmid: Die Physik muss das Bild irgendwo eingeben; was soll uns sonst davon abhalten zu erklären, dass alle funktionen berechenbar sind? Um den Namen zu verdienen, muss eine "Berechnung" etwas sein, das wir uns vorstellen können, tatsächlich durchzuführen. Aus diesem Grund bemühen sich Vorschläge für Hypercomputer zu erklären, wie sie physikalisch konstruiert werden können. Mein Punkt ist, dass wir das Gedankenexperiment noch einen Schritt weiter führen sollten: Woher wissen wir angesichts eines mutmaßlichen Hypercomputers, dass es wirklich wie angekündigt funktioniert? Wenn wir es nicht wissen könnten, wäre es dann wirklich legitim, seine Ergebnisse als "Berechnungen" zu bezeichnen?
Timothy Chow
1
Das ist interessant, vielleicht können wir nicht wirklich wissen, dass die Maschine f berechnet, weil wir gerade fertig sind. Vielleicht würde es einen hypercomputating Beobachter nehmen zu prüfen, ob ein Objekt in der Tat hypercomputing oO hypercomputing ist
guillefix
58

Obwohl es aufgrund des informellen Charakters der "effektiv berechenbaren Funktion" ziemlich schwierig erscheint, die These von Church-Turing zu beweisen, können wir uns vorstellen, was es bedeuten würde, sie zu widerlegen. Wenn nämlich jemand ein Gerät baut, das (zuverlässig) eine Funktion berechnet, die von keiner Turing-Maschine berechnet werden kann, würde dies die Church-Turing-These widerlegen, da es das Vorhandensein einer effektiv berechenbaren Funktion feststellt, die von einer Turing-Maschine nicht berechnet werden kann.

Andrej Bauer
quelle
1
In welchem ​​Sinne muss jemand die Maschine "bauen"? Wir leben in einer endlichen Welt, die möglicherweise nur Computer enthält, die strikt schwächer sind als Turing-Maschinen. Vielleicht muss er stattdessen eine neue intuitiv ansprechende logische Charakterisierung erfinden? Wie kann es sein?
Vag
2
Und unser Universum immer mehr eingeschränkt als theoretische Finite State Mashines wegen Beschränktheit von Masse / Energie , die durch Beton konstant und Bremmermann Grenze pespmc1.vub.ac.be/ASC/Bremer_limit.html so gibt es Berechnungen , die größer imaginäre FSMs tun können , aber physischen Computer kann nicht (transcomputational Probleme).
Vag
2
Natürlich müsste ein Mensch in der Lage sein, die Maschine zu simulieren, um die ursprüngliche These von Turing zu widerlegen, in der effektive Berechenbarkeit mit menschlicher Berechenbarkeit identifiziert wird.
Carl Mummert
35

Das Widerlegen der These von Church-Turing erscheint in der Tat äußerst unwahrscheinlich und konzeptionell sehr schwer vorstellbar. Es gibt verschiedene "hypothetische physikalische Welten", die im Spannungsfeld zur kirchentürkischen These stehen (aber ob sie sich widersprechen, ist für sich genommen eine interessante philosophische Frage). Ein Aufsatz von Pitowsky " The Physical Church's Thesis and Physical Computational Complexity", Iyun 39, 81-99 (1990), befasst sich mit solchen hypothetischen physikalischen Welten. Siehe auch das Papier von Itamar Pitowsky und Oron Shagrir: " The Church-Turing Thesis and Hyper Computation ", Minds and Machines 13, 87-101 (2003). Oron Shagrir hat mehrere philosophische Artikel über die These von Church-Turing geschrieben ( siehe seine Webseite) . (Siehe auch diesen Blogbeitrag .)

Die effektive oder effiziente Church-Turing-These ist eine unendlich stärkere Behauptung als die ursprüngliche Church-Turing-Behauptung, die besagt, dass jede mögliche Berechnung von einer Turing-Maschine effizient simuliert werden kann. Quantencomputer werden in der Tat zeigen, dass die effiziente These von Church-Turing ungültig ist (modulo einige rechnerisch komplexe mathematische Vermutungen und modulo die "asymptotische Interpretation"). Ich denke, die effiziente Church-Turing-Vermutung wurde erstmals 1985 von Wolfram formuliert. Der Artikel ist in Pitowskys oben verlinktem Artikel zitiert. Tatsächlich braucht man nicht einmal universelle Quantencomputer, um die effiziente CT-These zu widerlegen, und es ist interessant, Forschungszweig (den Aaronson ua studiert), um die rechnerische Überlegenheit von Quantensystemen möglichst einfach nachzuweisen.

Es ist auch ein interessantes Problem, wenn es einfachere Möglichkeiten gibt, die Rechenüberlegenheit von Quantencomputern bei Vorhandensein von Rauschen zu demonstrieren, als eine vollständige Quantenfehlertoleranz (die eine universelle Quantenberechnung ermöglicht). (Scott A. interessiert sich in der Tat auch für dieses Problem.)

Gil Kalai
quelle
Ich dachte, Turing-Maschinen könnten Quantencomputer simulieren? (Natürlich mit großem Effizienzverlust.) (Edit: ah, ich stelle fest, dass Sie die "Effektive CT-These" gesagt haben - ist dies die These, dass TMs jedes Rechengerät effizient simulieren können?)
Emil
5
Ich denke, Gil spricht von der "erweiterten" Church-Turing-These (die er "effektive" Church-Turing-These nennt), dass alles, was in der Natur effizient berechenbar ist, auch auf einer polytime Turing-Maschine berechenbar ist.
Ryan Williams
2
Ich habe einen Satz hinzugefügt, um es zu verdeutlichen.
Gil Kalai
Gil, danke für diesen schönen Beitrag! Um ein Quantensystem Engineering Point-of-View auszudrücken, existieren wir Menschen in einer lauten Welt , in der (fehlende Fehlerkorrektur) die ECT empirisch wahr ist , ---, dass quantendynamischen Prozesse können effizient simuliert wird --- über Formalismen , in denen (effektiv) Quantenüberlagerung ist eine lokale Annäherung, in etwa dem gleichen Sinne wie die euklidische Geometrie eine lokale Annäherung an die Riemannsche Geometrie ist. Umfasst die Natur ähnliche Quantenflüsse, um sich selbst effizient zu berechnen? Das ist eine offene Frage ... und meiner Meinung nach eine sehr interessante.
John Sidles
Inspiriert von Gil's Post und Timothy Chows Post (unten), habe ich den obigen Kommentar zu einer formalen TCS-Frage befördert: "Welche Rolle spielt die Validierung bei der Quantensampling-, Simulations- und Extended-Church-Turing-Prüfung (ECT)? " Danke Gil und Timothy.
John Sidles
24

Nach meinem Verständnis besteht die "Unmöglichkeit", die These zu beweisen oder zu widerlegen, darin, dass es keine formale Definition von "effektiv berechenbar" gibt. Wir gehen heute davon aus, dass es genau "von einer Turing-Maschine berechenbar" ist, aber das wirft die Frage auf.

Berechnungsmodelle, die strikt leistungsfähiger als eine Turing-Maschine sind, wurden untersucht. Einige Beispiele finden Sie unter http://en.wikipedia.org/wiki/Hypercomputation . Oder nimm einfach eine Turingmaschine mit einem Orakel für das Halteproblem für Turingmaschinen. Solch eine Maschine hat ein eigenes Halteproblem, kann aber das ursprüngliche Halteproblem problemlos lösen. Natürlich haben wir kein solches Orakel, aber es gibt nichts mathematisch Unmögliches an der Idee.

Evgenij Thorstensen
quelle
Danke für die Antwort. Eine Funktion zu entwickeln, die mathematisch (aber nicht physikalisch) durch ein Modell, aber nicht durch eine Turing-Maschine realisierbar ist, widerlegt die These also nicht?
1
Dershowitz und Gurevich 2008 axiomatisieren "effektiv berechenbar" mit abstrakten Zustandsautomaten.
Aaron Sterling
4
Sie definieren also ein anderes Berechnungsmodell und beweisen, dass es den vorhandenen Modellen entspricht, nicht wahr? Warum ist dieses Rechenmodell vertrauenswürdiger als das vorhandene?
Blaisorblade
Wir könnten die menschliche Kraft als solches Orakel nutzen und einen formellen Beweis für die (Nicht-) Beendigung erarbeiten. Schlechte Laufzeit, obwohl ...
Raphael
10

Beweise für Hypercomputing setzen im Allgemeinen die Gültigkeit der Bekenstein'schen Schranke voraus, die eine bestimmte Grenze für die Informationsmenge festlegt, die eine endliche Menge an Speicherplatz enthalten kann. Es gibt Kontroversen über diese Grenze, aber ich denke, die meisten Physiker akzeptieren sie.

Wenn die Bindung von Bekenstein schwer verletzt wird und die Menge der in einer bestimmten Region enthaltenen Informationen (z. B. ein Schwarzes Loch oder eine unendlich feine und robuste Gravur) unbegrenzt ist, gibt es willkürlich verfeinerbare Mechanismen, um deren Inhalt zu untersuchen Man kann annehmen, dass gerade ein Artefakt existiert, das ein stoppendes Orakel codiert, indem man die Strahlung, die von einem sorgfältig konstruierten Objekt emittiert wird, sorgfältig untersucht, das in das Schwarze Loch fällt, oder indem man einen Stift über die Rillen der Gravur fährt .

Alles sehr unwahrscheinlich, aber es zeigt, dass die Behauptung, dass Hyperberechnung unmöglich ist, keine mathematische Wahrheit ist, sondern auf der Physik basiert. Das heißt, Andrej hat recht, wenn er sagt, wir können uns vorstellen, was es bedeuten würde, [die These von Church-Turing] zu widerlegen. Nämlich, wenn jemand ein Gerät gebaut hat, das (zuverlässig) eine Funktion berechnet hat, die von keiner Turing-Maschine berechnet werden kann .

Charles Stewart
quelle
Bekensteins Schranke mag stimmen, dennoch könnte eine Überberechnung möglich sein.
András Salamon
@ András: Im Prinzip ja: Wir brauchen viel mehr physikalische Theorie, um ein negatives Argument zum Funktionieren zu bringen. Aber die Versuche, Hypercomputer zu "beschreiben", die ich gesehen habe, verstoßen alle dagegen.
Charles Stewart
Verletzen diejenigen, die geschlossene Schleifen in der Nähe von Schwarzen Löchern beinhalten, die Grenze?
András Salamon
@ András: Ich weiß nicht welche du meinst. Die Stringtheorie ist im Allgemeinen mit der Bindung von Bekenstein kompatibel.
Charles Stewart
Ich meine Dinge wie arxiv.org/abs/gr-qc/0209061, die, anstatt sich auf die Stringtheorie zu stützen, "nur" davon ausgehen, dass man Berechnungen in die Vergangenheit schicken kann.
András Salamon
9

In Bezug auf die Extended Church-Turing-These (gemeint als "Eine probabilistische Turing-Maschine kann jede physikalisch berechenbare Funktion effizient simulieren."):

Eine Möglichkeit ist der Unterschied zwischen klassischen und Quantencomputern. Insbesondere die Frage: "Gibt es eine Aufgabe, die Quantencomputer nicht erfüllen können wie klassische Computer?" Ein kürzlich veröffentlichter ECCC-Bericht von Scott Aaronson (siehe Vermutung 9 auf Seite 5) hebt eine Vermutung hervor, die, falls bewiesen, starke Beweise gegen die Extended Church-Turing Thesis liefern würde.

Wenn man die Extended Church-Turing Thesis widerlegen würde, könnte es so aussehen - nämlich indem man eine effizient berechenbare Aufgabe demonstriert, die eine (klassische) Turing-Maschine nicht effizient berechnen kann.

Daniel Apon
quelle
2
Zur Verdeutlichung stellt die Quantenberechnung nur die Efficient / Extended / Strong Church-Turing-These in Frage, die besagt, dass alle realisierbaren Rechenmodelle in polynomieller Zeit auf einer Turing-Maschine simuliert werden können. Die normale Church-Turing-These schränkt die Effizienz nicht ein. Quantencomputer haben keine Hoffnung, diese Version zu stürzen, da eine Turing-Maschine einfach alle exponentiell vielen Zweige einer Quantenberechnung in endlicher Zeit simulieren kann.
Ian
Ja, danke dafür - ich habe meine nachlässige Verwendung der beiden Begriffe korrigiert.
Daniel Apon
Hmmm ... aber nach Standarddefinitionen, hat nicht die ECT bereits schlüssig widerlegt worden? Alice: "Hier ist ein Beispiel von wirklich zufälligen Binärziffern, die von meinem (Ein-Modus-) optischen Quantennetzwerk berechnet wurden." Bob: "Hier ist eine Stichprobe von Pseudo-Zufallszahlen, die von einer klassischen Turing-Maschine berechnet wurden." Alice: Tut mir leid, Bob ... Ihre Stichprobe ist algorithmisch komprimierbar und meine nicht. Daher zeigen meine Daten, dass die ECT falsch ist! Formal ist Alices Argumentation einwandfrei. Sollten wir zufrieden sein, wenn Alice keine Validierungsprüfung ihrer Behauptungen durchführt?
John Sidles
4

Die folgenden Artikel von Selim Akl könnten für die Diskussion von Interesse und relevant sein:

Akl, SG, "Drei Gegenbeispiele, um den Mythos des Universalcomputers zu zerstreuen", Parallel Processing Letters, Vol. 3, September 2006, S. 381 - 403.

Akl, SG, "Auch Beschleunigungsmaschinen sind nicht universell", International Journal of Unconventional Computing, Vol. 3, No. 2, 2007, S. 105 - 121.

Nagy, M. und Akl, SG, "Parallelität in der Quanteninformationsverarbeitung besiegt den Universalcomputer", Parallel Processing Letters, Special Issue on Unconventional Computational Problems, Vol. 3, September 2007, S. 233 - 262.

Hier ist die Zusammenfassung der ersten:

Es wird gezeigt, dass das Konzept eines Universalcomputers nicht verwirklicht werden kann. Insbesondere werden Instanzen einer berechenbaren Funktion F gezeigt, die auf keiner Maschine U berechnet werden können, die nur eine endliche und feste Anzahl von Operationen pro Schritt ausführen kann. Dies gilt auch dann, wenn die Maschine U über einen unendlichen Speicher und die Fähigkeit verfügt, mit der Außenwelt zu kommunizieren, während sie versucht, F zu berechnen. Dies gilt auch dann, wenn U eine unbestimmte Zeit für die Berechnung zur Verfügung steht F. Dieses Ergebnis gilt nicht nur für idealisierte Rechenmodelle, wie die Turing-Maschine und dergleichen, sondern auch für alle bekannten Universalcomputer, einschließlich bestehender herkömmlicher Computer (sowohl sequentiell als auch parallel) sowie für in Betracht gezogene unkonventionelle, wie z als biologische und Quantencomputer.

Massimo Cafaro
quelle
Können Sie einen Link zu der ersten Zeitung angeben, die sich nicht hinter einer Paywall befindet? Was ist ihre Definition von "berechenbarer Funktion"? Nach der Standarddefinition (es gibt eine Turing-Maschine, die die Funktion berechnet) ist ihre Behauptung per Definition falsch ...
Christopher Monsanto
Ich habe Ihnen das Papier gerade per E-Mail geschickt.
Massimo Cafaro
Hier ist einer dieser Artikel: research.cs.queensu.ca/home/akl/techreports/even.pdf . Mehr hier: research.cs.queensu.ca/Parallel/projects.html . Es gibt keine wirkliche Definition eines "Computers" in der Zeitung, nur eine handgewellte Beschreibung. Vermutlich kann diese handgewellte Beschreibung mit ein wenig Arbeit unter Verwendung des Turing-Maschinenmodells oder dergleichen als Grundlage formalisiert werden.
Sasho Nikolov
W(t)tcW(t)>ct
Sasho Nikolov
-6

Wie kann es wahr sein? Ein klassischer Computer kann einen Quantencomputer nicht effizient simulieren. Es gibt Quantenalgorithmen, die eine exponentielle Beschleunigung gegenüber klassischen Computern mit klassischen Algorithmen ermöglichen: Shors Algorithmus ist einer.

Robert McGwier
quelle
3
1) Möglicherweise gibt es einen klassischen Polytime Factoring-Algorithmus. Wir kennen keine, aber ihre Existenz steht völlig im Einklang mit dem Stand der Komplexitätstheorie. 2) In der ursprünglichen Church-Turing-These geht es um Berechenbarkeit, nicht um effiziente Berechenbarkeit.
Sasho Nikolov