Ist Interaktion leistungsfähiger als Algorithmen?

17

Ich habe gehört, das Motto Interaktion ist mächtiger als Algorithmen von Peter Wegner . Die Grundlage der Idee ist, dass eine (klassische) Turing-Maschine keine Interaktion, dh keine Kommunikation (Eingabe / Ausgabe) mit der Außenwelt / Umgebung, bewältigen kann.

Wie kann das so sein? Wie kann etwas leistungsfähiger sein als eine Turingmaschine? Was ist das Wesentliche dieser Geschichte? Warum ist es nicht bekannter?

Dave Clarke
quelle
1
Haben Sie eine Referenz, die Sie in Ihre Frage aufnehmen möchten? Ich kenne die formale Definition einer Turing-Maschine, aber ich weiß nicht genau, was Sie unter "Interaktion" verstehen.
Janoma
Außerdem scheint es so, als ob "ich kann nicht mit der Interaktion mit der Umgebung umgehen" ähnlich ist wie "ich kann nicht mit wahrer Zufälligkeit umgehen", was wahr sein könnte, aber beide können mit Sensoren und Pseudozufälligkeit ziemlich gut angenähert werden. Aber das ist ein nicht informierter Kommentar, der keine Definition von Interaktion kennt.
Janoma
2
Turingmaschinen haben keine Sensoren.
Dave Clarke
1
Ich bin mir dessen bewusst. Und doch, Computer tut Verwendung Sensoren, die sind eine besondere Art und Weise einen Eingang zu einer Turing - Maschine zu übergeben. So TMs tut irgendwie mit externen Signalen / Umgebung in Wechselwirkung treten.
Janoma
2
Die Frage bezieht sich nicht auf Computer. Die einzige Interaktion mit einem TM besteht darin, dass die Umgebung ihm zu Beginn eine Eingabe bereitstellt und am Ende höchstens eine Ausgabe empfängt. Dies ist kaum eine allgemeine Interaktion.
Dave Clarke

Antworten:

11

Turingmaschinen können mit Orakelbändern problemlos mit Interaktionen umgehen. Es funktioniert folgendermaßen: Aus der Sicht eines Computers, der die Interaktion handhabt, ist die Eingabe des Operators einfach eine andere Folge von Bits, die er von Zeit zu Zeit an den Computer sendet. Wir alle wissen, dass ein fauler Sysadmin ein Skript schreiben kann, um die Eingabe an das Programm zu senden, wenn es angefordert wird, sodass der Sysadmin früher in die Pause gehen kann. Die Interaktionsmaschine kann nicht wissen, ob sich tatsächlich ein Live-Operator an der Konsole befindet oder ob die Eingabe von einem anderen Programm weitergeleitet wird.

Wenn alle Interaktionseingaben im Voraus vorbereitet werden, entspricht dies theoretisch den Eingaben auf einem separaten Band, das von einer Oracle Turing-Maschine verwendet wird. Wann immer der Computer normalerweise eine Interaktion vom Bediener anfordert, liest das Gerät stattdessen vom Eingabeband. Wenn das vom Band gelesene Ding in irgendeiner Weise ungültig erscheint, tut die Turing-Maschine genau das, was die Interaktionsmaschine beim Empfang dieser Eingabe tun würde.

Ich würde vermuten, dass Wagner sich der Fähigkeit bewusst ist, Orakelbänder für die Codeeingabe zu verwenden. Sie müssen also seine Kommentare mit einem Körnchen Salz auffassen oder sich fragen, was er eigentlich meint. Ich glaube, dass Menschen, die über Interaktion nachdenken, im Allgemeinen zwei Dinge befürchten:

  • "Echte" Computer haben eine Interaktion, Algorithmen, wie sie von Turing definiert wurden, jedoch nicht. Wir können dies umgehen, indem wir die Eingabe auf Oracle-Bändern codieren, aber dies entspricht immer noch nicht der Art und Weise, wie echte Computer funktionieren. Es könnte hilfreich sein, Rechenmodelle zu studieren, die näher an realen Computern ausgerichtet sind.

  • Oracle-basierte Algorithmen werden in der täglichen Arbeit kaum berücksichtigt, da normale Computer kein magisches "Orakel" für die Datenbereitstellung besitzen. Aber vielleicht können wir tatsächlich nur eine Person als Orakel benutzen. Wenn die Person die angeforderten Daten versteht, kann sie dem Algorithmus möglicherweise sogar weiterhelfen und so seine Leistung verbessern. Mit anderen Worten, ein Mensch ist möglicherweise in der Lage, ein nützliches Orakelband anstelle eines zufälligen zur Verfügung zu stellen, und dies kann prinzipiell zu schnelleren oder leistungsstärkeren Rechenmethoden führen als bei nicht auf Orakel basierenden. Ähnliches passiert schließlich beim randomisierten Rechnen, bei dem die Maschine eine Folge von Zufallsbits als zusätzliche Eingabe erhält.

Carl Mummert
quelle
Oracle-Bänder modellieren die Interaktion nicht korrekt. Versuchen Sie zu beweisen, dass in einem Computersystem keine privaten Informationen verloren gehen. Dies kann nicht in Form eines TM mit einem festen Orakelband formalisiert werden, da die Eigenschaft davon abhängt, wie die Berechnung von der Umgebung ausgeführt werden kann - genau das, was wir mit einem Orakelband abstrahieren.
Neel Krishnaswami
Es kommt darauf an, was Sie mit "richtig modellieren" meinen. Einige Artikel (z. B. aus der Hypercomputer-Community) scheinen darauf hinzudeuten, dass Interaktion den Satz berechenbarer Funktionen irgendwie erweitert. Genau wie bei der Orakelberechnung. Natürlich können Sie keine TMs verwenden, um die Eigenschaften der tatsächlichen Berechnungsumgebung zu untersuchen. Wenn Sie wissen möchten, ob der Prozessor in Ihrem Computer fehlerhaft ist, hilft es nicht, ihn vollständig zu ignorieren und sich nur Turing-Maschinen anzusehen. Für Fragen, die nur die berechnete Funktion betreffen, sind Interaktion und Orakel gleichwertig.
Carl Mummert
nn
Für eine wirklich gründliche Ausarbeitung dieser Analogie siehe Peter Hancock, Pierre Hyvernat: Programmierschnittstellen und grundlegende Topologie. citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.919
Neel Krishnaswami
1
n
8

Turning Machines Modellberechnung, und haben kein Konzept der Interaktion. In diesem Sinne kann eine Maschine, die die Interaktion mit einem externen System unterstützt, Dinge tun, die eine Drehmaschine nicht kann. Aber die Berechnung zwischen Eingaben von einer externen Quelle kann natürlich immer von einer Turing-Maschine modelliert werden, so dass selbst eine "IO-Maschine" mit Eingaben von außen nichts anfangen kann, was eine Turing-Maschine nicht kann.

In gewissem Sinne ist eine solche Maschine möglicherweise in der Lage, Probleme zu "entscheiden", die von Turing Machines nicht entschieden werden können, aber nur, wenn Sie sich vorstellen, dass das System, mit dem sie interagiert, über Super-Turing-Machine-Kräfte verfügt und zuverlässig ist (in gewisser Weise wahrscheinlichkeitstheoretische Zuverlässigkeit) wäre genug).

Stellen Sie sich ein Programm für eine IO-Maschine vor wie: "Drucken Sie für eine anfängliche Bandeingabe den Bandinhalt aus und lesen Sie dann ein Symbol von einer externen Eingabe. Akzeptieren Sie, wenn das Symbol 1 ist, und lehnen Sie dies ab." Dieses Programm kann jedes Problem entscheiden . Aber nur wenn das externe System, mit dem es interagieren kann, in der Lage ist, das Problem zu entscheiden; Für mich ist das keine sehr interessante Art zu sagen, dass die IO-Maschine von in der Lage ist, Probleme zu entscheiden, die von Turing Machines nicht entschieden werden können.

Ich denke, es wäre immer möglich, eine interaktive Berechnung darzustellen, indem man sich eine Maschine vorstellt, die auf ihrem Band eine Codierung einer früheren Konfiguration zusammen mit einer externen Eingabe als Eingabe verwendet und die Maschine anhält, während ihr Band eine Codierung einer Konfiguration zusammen enthält mit Ausgabe. Der Vorgang "Ausführen eines Programms" führt diese Turing-Maschine dann wiederholt auf mechanische Weise aus, wobei der einzige "nicht-mechanische" Teil jedoch die Eingabe von außen ist. Ich bin mir sicher, dass Sie das beweisen könnten, wenn ein solches System seine Eingabe erhalten würde, indem Sie seine Ausgabe an eine andere Turing-Maschine weitergebenWenn das kombinierte System auf ähnliche Weise eingerichtet ist, verfügt es über identische Rechenfähigkeiten wie eine einzelne Turing-Maschine. Ich finde, dass ein überzeugendes Argument, dass interaktive Berechnung nicht leistungsfähiger ist als nicht interaktive Berechnung, es sei denn, das System, mit dem die Berechnung interagiert, ist leistungsfähiger als eine Turing-Maschine .


Es gibt jedoch einen nicht-theoretischen Sinn, in dem Interaktivität dazu beitragen kann, dass ein Computer Probleme lösen kann. Es gibt viele Dinge, die Menschen sehr genau tun, und wir wissen nicht, wie wir Computer dazu bringen können, sehr gut zu funktionieren. Aber es gibt auch viele Dinge, bei denen Menschen Unsinn sind und bei denen wir Computer dazu bringen können, dies zu tun. Die Kombination dieser beiden Faktoren kann zu Projekten wie reCaptcha führen , bei dem Bücher automatisch digitalisiert werden, indem die Probleme der Erkennung von Wörtern für Menschen in schwierigen Fällen vermieden werden. Das sich ergebende System von Computer + menschlicher Arbeit erzielt ein Ergebnis, das gegenwärtig entweder mit der Berechnung alleine oder mit der menschlichen Arbeit alleine nicht zu erreichen ist.

Ben
quelle
8

Kürzlich veranstaltete ACM ein Ubiquity-Symposium zum Thema " Was ist Berechnung?". ', in dem Peter Wegner einen Artikel veröffentlichte, der seine Ansichten zu Interactive Computing widerspiegelt.

Hier zwei Auszüge aus dem Artikel von Peter Wegner:

Ein neues Konzept, das in frühen Turing-Maschinen fehlt, ist "Interactive Computing", das die Interaktion mit der Umgebung während der Berechnung berücksichtigt.

Interaktionsmaschinen können leistungsstärkere Formen der Datenverarbeitung ausführen als Turing-Maschinen und können die von Turing vorgeschlagene Art des Denkens ausführen, da die Interaktion ihre Leistung gegenüber der von Turing-Maschinen verbessert.

Fortnow, der einen Artikel im selben Symposium verfasst hat, scheint jedoch mit den Ansichten von Wegner nicht einverstanden zu sein und ist der Ansicht, dass interaktives Computing keine zusätzliche Macht über Turing Machines bietet.

Um die Mischung zu ergänzen, scheint es, dass wir immer noch über Berechnungen diskutieren und sie definieren. Moshe Vardi hat einen Artikel, Was ist ein Algorithmus? Nr. 3, März 2012.

Vardi berichtet über zwei neue Definitionen von Algorithmen. Das erste wird von Gurevich und das zweite von Moschovakis vorgeschlagen.

Gurevich argumentierte, dass jeder Algorithmus als abstrakte Zustandsmaschine definiert werden kann.

Im Gegensatz dazu argumentierte Moschovakis, dass ein Algorithmus in Form eines Rekursors definiert ist, der eine rekursive Beschreibung ist, die auf willkürlichen Operationen aufbaut, die als Grundelemente betrachtet werden.

Mohammad Al-Turkistany
quelle
6

Ich denke nicht, dass Modelle mit IO "leistungsstärker" sind als Turing-Maschinen, sie modellieren nur verschiedene Dinge.

Theoretisch könnten Sie IO als (lautes?) Orakel ansehen. Mit einem perfekten Orakel können Sie Turing-unberechenbare Funktionen rechnen; aber woher kommt das Orakel? Menschen sind die einzige "Super-Turing" Wahl (wenn es welche gibt) und wir sind dafür bekannt, sehr unzuverlässig zu sein.

Eine Klasse von Programmen, die zu diesem Modell passen, sind interaktive Proofassistenten (z. B. Isabelle / HOL , Coq ). Sie befassen sich mit unentscheidbaren Beweisräumen, aber (wohl) jeder Beweis kann durch geeignete Benutzereingaben gefunden (und überprüft) werden.

Raphael
quelle
So Turingmaschinen mit Oracles sind leistungsstärker , dass Turing - Maschinen , ohne sie und Turing - Maschinen mit Oracles Interaktion modellieren können. Die Antwort scheint also ja zu sein.
Dave Clarke
1
@ DaveClarke Wenn Sie perfekte Orakel betrachten, ja.
Raphael
2
Ich denke, eine Maschine (oder ein Programm) ohne Hilfe (durch jede Form von Orakel oder Eingabe) könnte im Prinzip jeden Beweis finden. Es gibt zwei Probleme: (1, theoretisch): Es kann niemals festgestellt werden, dass eine Aussage keinen Beweis hat, und (2, praktisch): Die blinde Erzeugung von Beweisen in der Hoffnung, auf eine bestimmte Aussage zu stoßen, ist so schrecklich ineffizient, dass niemand darauf stößt will es versuchen, und so bevorzugen Proof-Assistenten eine geführte Suche und geben "gesicherten" Erfolg auf, falls es einen Proof gibt.
Marc van Leeuwen
2
Wie Ben in seiner Antwort betont, ist die richtige Sichtweise nicht "Turingmaschinen mit Orakeln sind mächtiger". Die Maschinen selbst machen nur berechenbare Dinge. Die richtige Sichtweise lautet: "Einige Orakel sind nicht berechenbar. Aus diesen Orakeln können wir Dinge berechnen, die wir ohne Orakel nicht berechnen können." Die Rechenleistung kommt eher vom Orakel als von der Maschine.
Carl Mummert
Turingmaschinen mit Orakeln scheinen das Mächtigste zu sein. Warum sollte man sich überhaupt mit neuen Definitionen beschäftigen?
Saadtaame