Anwendbarkeit der Church-Turing-These auf interaktive Rechenmodelle

Paul Wegner und Dina Goldin veröffentlichen seit über einem Jahrzehnt Artikel und Bücher und argumentieren in erster Linie, dass die These von Church-Turing in der CS-Theory-Community und anderswo häufig falsch dargestellt wird. Das heißt, es wird so dargestellt, dass es alle Berechnungen umfasst, obwohl es tatsächlich nur für die Berechnung von Funktionen gilt, die eine sehr kleine Teilmenge aller Berechnungen darstellt. Stattdessen schlagen sie vor, dass wir versuchen sollten, interaktive Berechnungen zu modellieren, bei denen die Kommunikation mit der Außenwelt während der Berechnung stattfindet.

Die einzige Kritik, die ich an dieser Arbeit gesehen habe, ist das Lambda the Ultimate- Forum, in dem diese Autoren beklagt wurden, dass sie ständig das veröffentlichen, was offensichtlich bekannt ist. Meine Frage ist dann, gibt es noch mehr Kritik an dieser Denkrichtung und insbesondere an ihren Persistent Turing Machines. Und wenn nicht, warum wird es dann anscheinend sehr wenig studiert (ich könnte mich irren). Wie lässt sich der Begriff der Universalität auf eine interaktive Domäne übertragen?

Hier ist meine Lieblingsanalogie. Angenommen, ich habe ein Jahrzehnt damit verbracht, Bücher und Artikel zu veröffentlichen, in denen ich argumentierte, dass die Church-Turing-These entgegen dem Dogma der theoretischen Informatik nicht alle Berechnungen erfasst, weil Turing-Maschinen kein Brot rösten können . Deshalb brauchen Sie mein revolutionäres neues Modell, die Toaster-Enhanced Turing Machine (TETM), die Brot als mögliche Eingabe zulässt und Toasten als primitive Operation beinhaltet.

Man könnte sagen: Klar, ich habe einen "Punkt", aber es ist völlig uninteressant. Niemand hat jemals behauptet, eine Turing-Maschine könne jede mögliche Interaktion mit der Außenwelt bewältigen, ohne sie zuvor an geeignete Peripheriegeräte anzuschließen. Wenn Sie möchten, dass ein TM Brot röstet, müssen Sie ihn an einen Toaster anschließen. Dann kann der TM leicht die interne Logik des Toasters handhaben (es sei denn, dieser spezielle Toaster erfordert die Lösung des Halteproblems oder dergleichen, um zu bestimmen, wie braun das Brot sein soll!). Wenn Sie möchten, dass ein TM mit interaktiver Kommunikation umgehen kann, müssen Sie es auf die gleiche Weise an geeignete Kommunikationsgeräte anschließen, wie Neel in seiner Antwort erläutert hat. In beiden Fällen sagen wir nichts, was Turing selbst nicht aufgefallen wäre.

Ich würde sagen, der Grund, warum Wegner und Goldins Schriften nicht weiterverfolgt wurden, liegt darin, dass TCS seit Anbeginn des Fachgebiets weiß, wie man Interaktivität bei Bedarf modelliert.

Update (8/30): Ein verwandter Punkt ist wie folgt. Gibt es für die Kritiker jemals Anlass zu der Annahme, dass die wichtigsten Forschungsthemen der letzten zwei Jahrzehnte im Inneren des Eliteturings aus Elfenbein (ECTIT) interaktive Beweise, kryptografische Mehrparteienprotokolle, Codes für die interaktive Kommunikation und asynchrone Routing-Protokolle waren? , Konsens, Gerüchteverbreitung, Führerwahl usw. und der Preis der Anarchie in Wirtschaftsnetzwerken? Wenn es so schwierig ist, die Interaktion mit Turings Begriff der Berechnung in den Mittelpunkt zu rücken, wie ist es dann, dass so wenige von uns es bemerkt haben?

Noch ein Update: Lassen Sie mich eine sehr einfache Frage an die Leute stellen, die immer wieder darüber diskutieren, dass Formalismen auf höherer Ebene weitaus intuitiver sind als TMs und niemand in Bezug auf TMs als praktische Angelegenheit denkt. Was ist es, das all diese Hochsprachen überhaupt erst existieren lässt, um sicherzustellen, dass sie immer bis zum Maschinencode kompiliert werden können? Könnte es sein ... ähm ... DIE KIRCHENTURIERENDE DIESE , die gleiche, auf der Sie herumgespielt haben? Zur Verdeutlichung ist die kirchliche These nicht die Behauptung, dass "TURING MACHINEZ RULE !!" Vielmehr ist es die Behauptung, dass jede vernünftige Programmiersprache in ihrer Ausdruckskraft Turing-Maschinen gleichwertig ist - und dies zur Folge hat, dass Sie genauso gut in den übergeordneten Sprachen denken könnten, wenn es bequemer ist, dies zu tun. Dies war natürlich vor 60-75 Jahren eine radikale neue Erkenntnis.

Letztes Update: Ich habe einen Blog-Beitrag erstellt, um diese Antwort weiter zu diskutieren.

Ich denke, das Problem ist ziemlich einfach.

1. Alle interaktiven Formalismen können von Turing-Maschinen simuliert werden.

2. TMs sind (in den meisten Fällen) unpraktische Sprachen für die Erforschung interaktiver Berechnungen, da das Rauschen von Codierungen die interessanten Themen überdeckt.

3. Das weiß jeder, der an der Mathematisierung von Interaktionen arbeitet.

Lassen Sie mich das näher erläutern.

Turing-Maschinen können natürlich alle vorhandenen interaktiven Computermodelle in folgendem Sinne modellieren: Wählen Sie eine Codierung der relevanten Syntax als Binärzeichenfolgen, schreiben Sie ein TM, das zwei codierte interaktive Programme P, Q (in einem ausgewählten Modell für interaktive Berechnungen) als Eingabe verwendet. und liefert genau dann true zurück, wenn eine einstufige Reduktion von P auf Q im relevanten Term-Rewriting-System vorliegt (wenn Ihr Kalkül eine ternäre Übergangsrelation aufweist, verfahren Sie entsprechend). Sie haben also ein TM erhalten, das eine schrittweise Simulation der Berechnung im interaktiven Kalkül durchführt. Es ist klar, dass Pi-Kalkül, Umgebungskalkül, CCS, CSP, Petrinetze, zeitgesteuertes Pi-Kalkül und jedes andere interaktive Rechenmodell, das untersucht wurde, in diesem Sinne ausgedrückt werden können. Das ist es, was Menschen meinen, wenn sie sagen, dass Interaktion nicht über TMs hinausgeht.

N. Krishnaswami verweist auf einen zweiten Ansatz zur Modellierung der Interaktivität mithilfe von Orakelbändern. Dieser Ansatz unterscheidet sich von der obigen Interpretation der Reduktions- / Übergangsrelation, da der Begriff TM geändert wird: Wir wechseln von einfachen TMs zu TMs mit Orakelbändern. Dieser Ansatz ist in der Komplexitätstheorie und Kryptographie beliebt, vor allem, weil er Forschern auf diesen Gebieten ermöglicht, ihre Werkzeuge und Ergebnisse von der sequentiellen in die konkurrierende Welt zu übertragen.

Das Problem bei beiden Ansätzen besteht darin, dass die eigentlichen theoretischen Probleme der Nebenläufigkeit verschleiert sind. Die Concurrency-Theorie versucht, Interaktion als Phänomen sui generis zu verstehen. Beide Ansätze über TMs ersetzen einfach einen bequemen Formalismus zum Ausdrücken einer interaktiven Programmiersprache durch einen weniger bequemen Formalismus.

In keinem der beiden Ansätze sind wirklich nebenläufige theoretische Probleme, dh die Kommunikation und ihre unterstützende Infrastruktur, direkt vertreten. Sie sind dort, sichtbar für das geübte Auge, aber verschlüsselt, verborgen im undurchdringlichen Nebel der Verschlüsselungskomplexität. Beide Ansätze sind also schlecht in der Mathematisierung der Schlüsselaspekte des interaktiven Rechnens. Nehmen wir zum Beispiel die beste Idee in der Theorie der Programmiersprachen des letzten halben Jahrhunderts, Milner et al. Axiomatisierung der Scope-Extrusion (was ein Schlüsselschritt in einer allgemeinen Theorie der Kompositionalität ist):

Wie schön einfach diese Idee ist, wenn man sie in einer maßgeschneiderten Sprache wie dem Pi-Kalkül ausdrückt. Dies mit der Kodierung von pi-calculus in TMs zu tun, würde wahrscheinlich 20 Seiten füllen.

Mit anderen Worten, die Erfindung expliziter Formalismen für die Interaktion hat folgenden Beitrag zur Informatik geleistet: Die direkte Axiomatisierung der Schlüsselprimitive für die Kommunikation (z. B. Eingabe- und Ausgabeoperatoren) und die unterstützenden Mechanismen (z. B. Generierung neuer Namen, parallele Komposition usw.). . Diese Axiomatisierung hat sich zu einer regelrechten Forschungstradition mit eigenen Konferenzen, Schulen und Terminologie entwickelt.

Eine ähnliche Situation ergibt sich in der Mathematik: Die meisten Konzepte könnten in der Sprache der Mengenlehre (oder der Topos-Theorie) niedergeschrieben werden, aber wir bevorzugen meist Konzepte höherer Ebenen wie Gruppen, Ringe, topologische Räume und so weiter.

$\mathbb{N} \to \mathbb{N}$

Es ist jedoch immer noch wahr, dass Turing-Maschinen für die Modellierung von Eigenschaften wie Interaktivität ziemlich schmerzhaft sind. Der Grund ist ein wenig subtil und hat mit den Arten von Fragen zu tun, die wir über interaktive Berechnungen stellen möchten.

Der übliche erste Durchgang bei der Modellierung der Interaktion mit TMs ist mit Orakelbändern. Intuitiv kann man sich die auf dem Orakelband aufgedruckte Zeichenfolge als "Vorhersage" der I / O-Interaktion der Turing-Maschine mit der Umgebung vorstellen. Bedenken Sie jedoch die Art von Fragen, die wir zu interaktiven Programmen stellen möchten: Beispielsweise möchten wir möglicherweise wissen, dass ein Computerprogramm Ihre Finanzdaten nur ausgibt, wenn Sie Ihren Benutzernamen und Ihr Kennwort als Eingabe erhalten, und dass Programme nicht auslaufen Informationen zu Passwörtern. Das Sprechen über diese Art von Einschränkung ist bei Orakelketten sehr schmerzhaft, da sie eine zeitliche, epistemische Einschränkung der Interaktionsspur widerspiegeln und Sie bei der Definition von Orakelbändern aufgefordert werden, die gesamte Kette im Voraus anzugeben.

Ich vermute, dass es machbar ist, dieses Ziel zu erreichen, und im Wesentlichen bedeutet (1), Orakelstrings nicht als eine Menge zu betrachten, sondern als einen topologischen Raum, dessen offene Mengen die modale Logik von Zeit und Wissen kodieren, die Sie modellieren möchten, und (2) sicherzustellen dass die Theoreme, die Sie beweisen, in Bezug auf diese Topologie alle stetig sind und Prädikate als stetige Funktionen von Orakelketten bis zu Wahrheitswerten betrachten, die als Sierpinski-Raum angesehen werden. Ich möchte betonen, dass dies eine Vermutung ist , die auf der Analogie zur Domänentheorie basiert. Sie müssten die Details ausarbeiten (und sie wahrscheinlich an LICS oder etwas anderes senden), um sicherzugehen.

Infolgedessen modellieren die Benutzer die Interaktion lieber mit Dingen wie dem Dolev-Yao- Modell, bei dem Sie die Interaktion zwischen Computern und der Umgebung explizit modellieren, sodass Sie explizit charakterisieren können, was der Angreifer weiß. Dies erleichtert die Formulierung geeigneter Modallogiken für Sicherheitsüberlegungen erheblich, da der Systemstatus und der Umgebungsstatus explizit dargestellt werden.

Beim Lesen des Blogs von Lance Fortnows stieß ich auf diesen kürzlich erschienenen / schönen / langen Umfrageartikel zum Thema mit vielen Perspektiven und Referenzen [1] (der bisher noch nicht zitiert wurde), unter anderem auf die Perspektive von Wegner / Goldin. Ich zitiere nur Fortnows ausgezeichnete / nachdrückliche Zusammenfassung / Erklärung / Behauptung der fast amtlichen / einheitlichen / einstimmigen TCS-Parteilinie:

"Einige wenige Informatiker versuchen dennoch zu argumentieren, dass die These von [Church-Turing] einige Aspekte der Berechnung nicht erfasst. Einige von ihnen wurden an renommierten Orten wie Science, Communications of the ACM und jetzt in einer ganzen Reihe von Publikationen veröffentlicht Artikel in ACM Ubiquity. Einige Leute außerhalb der Informatik glauben möglicherweise, dass es eine ernsthafte Debatte über die Art der Berechnung gibt.

[1] Turings Titanic Machine von Barry S. Cooper CACM Vol. 55

Ich stimme den Kommentaren von Aaron sehr zu.

Ich verstehe Milners Arbeit nicht. (zB Pi-Kalkül, den Milner erfunden hat, um Kommunikationsprozesse zu beschreiben). Es ist für mich ziemlich unlesbar, ebenso wie fast alle Artikel über Mathematik und Logik, wie etwa Lambeks Theorien. Ich habe keinen Zweifel, dass Lambeks Ideen sehr gut sind, aber ich würde sie gerne in eine Art Pidgin-Englisch übersetzt sehen, das ich lesen kann.

Milners Bemerkung, dass Lambda-Kalkül für "sequentielle Prozesse" in Ordnung ist, aber dass etwas mehr für die Kommunikation von Prozessen benötigt wird, stört mich.

Mein (vielleicht naiver) Standpunkt war, dass das nicht so sein kann, da pi-Kalkül Turing vollständig ist und daher mechanisch in eine andere Turing-vollständige Notation, dh Lambda-Kalkül, konvertiert werden kann. Daher kann Milners pi-Kalkülnotation automatisch in Lambda-Kalkül konvertiert werden.

Es scheint, dass ich ein Projekt identifiziert habe: Intuitiv sollte es möglich sein, mechanisch von einer Turing-vollständigen Sprache in eine andere zu konvertieren. Gibt es einen Algorithmus, um dies zu tun? Ich muss auf Google schauen. Vielleicht ist das unglaublich schwierig und genauso schwierig wie das Problem des Stillstands.

Ich habe gestern im Netz nachgesehen und Papiere über Modelle der Lambda-Rechnung gefunden. Ich war überrascht, dass dies ein sehr tiefes Kaninchenloch zu sein scheint.

Richard Mullins

Hier ist die Sache, sobald Sie (reine) Interaktivität hinzufügen, geht die Formalität aus dem Fenster. Es ist kein "geschlossenes" System mehr. Die Frage ist dann, was ist der Begriff der Berechnung, sobald Interaktivität eintritt? Diese Antwort: Nun, entweder ersetzt der andere Benutzer / die andere Maschine einen Teil Ihrer Berechnung (die durch eine andere, größere Zustandsmaschine beschrieben werden kann), oder Sie befinden sich nicht mehr in einem formal definierbaren System und spielen jetzt ein Spiel , in dem es keine Anwendung der Church-Turing-These gibt.

Wegners Papier überfliegen, es ist klar, dass er ein bisschen melodramatisch und konträr ist, aber er hat einen Punkt. Die Zukunft des Rechnens konzentriert sich wohl wesentlich mehr auf Robotik , KI oder Datenverarbeitung (von riesigen "Big Data" der realen Welt), die er scheinbar nicht namentlich erwähnt, auf die er jedoch mit seinem Modell klar anspielt. und diese Bereiche konzentrieren sich größtenteils auf das Universum außerhalb der Ein- und Ausgänge eines TM.

Historisch wurde es auch als Kybernetik bezeichnet, wie es von Weiner erfunden / formuliert wurde. Der Punkt der Robotik ist, dass Ein- und Ausgänge nicht nur digital und ohne Bedeutung sind, woraus man einen TM schließen könnte. Sie sind es, aber sie haben reale Auswirkungen / Auswirkungen / Ursachen usw., und die Maschine bildet eine Rückkopplungsschleife mit der Umgebung.

Ich würde also argumentieren, dass TMs und Robotik sozusagen eine sehr natürliche Synergie oder Symbiose eingehen. Aber dies ist keine radikale Behauptung und das, was Wegner mit großer Fanfare ankündigt, ist anders formuliert, nicht sehr kontrovers oder neuartig. Mit anderen Worten, Wegner scheint sich absichtlich als intellektueller oder akademischer Bilderstürmer in seinem Stil zu etablieren. Und wer ist die TCS-Community, die ihm diese melodramatische Einrahmung verweigert? dennoch siehe [2] für eine ernsthafte Widerlegung.

Wegners Beispiel des Autofahrens ist sehr relevant und andere wichtige neue Durchbrüche in TCS können angeführt werden:

• die DARPA Road Race Challenge und auch Googles Annäherung an die Technologie eines fahrenden Autos. [3]
• der Fall des Big Blue AI-Schachsiegs über Kasparov
• der jüngste Sieg bei der Deep Blue Jeopardy Challenge
• der zunehmend autonome Marsrover
• ein kürzlich angekündigter Durchbruch bei der unbeaufsichtigten Objekterkennung durch Google. [4]
• kommerzialisierte Spracherkennung

Aber es ist wahr, was vor Jahrzehnten als bloße Theorie mit TMs begann, ist heute ein sehr reales Phänomen, und Teile der TCS-Community im Elfenbeinturm könnten in einem gewissen Widerstand stehen oder diese Tatsache und die damit verbundenen fundamentalen [in der Nähe von Kuhnian] sogar verneinen ] Transformation und Verschiebung "derzeit im Spiel". Dies ist etwas ironisch, weil Turing in vielen seiner Perspektiven und Studien sehr angewendet wurde, wie z. B. in Bezug auf sein Interesse an einem operationellen AI-Test (dem Turing-Test), der chemischen Dynamik, der Berechnung von Schachlösungen usw. [5].

Sie können dies sogar in einem Mikrokosmos auf dieser Seite in Konflikten über die Definition des Geltungsbereichs und in heftigen Auseinandersetzungen darüber sehen, ob eine bestimmte scheinbar harmlose Marke, die als Anwendung der Theorie bezeichnet wird, legitim ist. [7]

und nehmen wir zur Kenntnis, dass TCS in der Tat viele interaktive Rechenmodelle untersucht und in diesem Bereich viel Schlüsselforschung betrieben wird ... insbesondere interaktive Beweissysteme, für die alle wichtigen Rechenklassen definiert werden können. [6]

[1] Die Church-Turing-These - Brechen des Mythos von Goldin & Wegner

[2] Gibt es neue Rechenmodelle? eine Antwort auf Goldin & Wegner von Cockshott & Michaelson

[3] Googles selbstfahrende Autos - 300.000 Kilometer geloggt, kein einziger Unfall unter Computersteuerung, der Atlantik

[4] Google unbeaufsichtigt Objekterkennung von Youtube-Bildern

[5] Alan Turings Beiträge zu CS

[6] Landschaft interaktiver Beweissysteme

[7] Zur Änderung unseres Geltungsbereichs - ein Vorschlag