L'interaction est-elle plus puissante que les algorithmes?

17

J'ai entendu dire que l' interaction avec la devise était plus puissante que les algorithmes de Peter Wegner . L'idée de base est qu'une machine de Turing (classique) ne peut pas gérer l'interaction, c'est-à-dire la communication (entrée / sortie) avec le monde / l'environnement extérieur.

Comment cela peut-il être ainsi? Comment quelque chose peut-il être plus puissant qu'une machine de Turing? Quelle est l'essence de cette histoire? Pourquoi n'est-il pas plus connu?

Dave Clarke
la source
1
Avez-vous une référence à inclure dans votre question? Je connais la définition formelle d'une machine de Turing, mais je ne sais pas exactement ce que vous entendez par «interaction».
Janoma
En outre, il semble que "ne peut pas gérer l'interaction avec l'environnement" est similaire à "ne peut pas gérer le vrai hasard", ce qui pourrait être vrai, mais les deux peuvent être assez bien approchés avec des capteurs et un pseudo-aléatoire. Mais c'est un commentaire non informé, ne connaissant pas une définition de l'interaction.
Janoma
2
Les machines de Turing n'ont pas de capteurs.
Dave Clarke
1
Je suis au courant de ça. Et pourtant, les ordinateurs font capteurs d'utilisation, qui sont d' une manière particulière de passer une entrée à une machine de Turing. Ainsi , les mémoires de traduction font Interagir avec des signaux externes / environnement en quelque sorte.
Janoma
2
La question ne concerne pas les ordinateurs. La seule interaction avec une MT est que l'environnement lui fournit une entrée au début et reçoit au plus une sortie à la fin. Ce n'est guère une interaction générale.
Dave Clarke

Réponses:

11

Les machines de Turing peuvent très bien gérer l'interaction, en utilisant des bandes oracle. Cela fonctionne comme suit: du point de vue d'un ordinateur qui gère l'interaction, l'entrée de l'opérateur est simplement une autre séquence de bits qu'il envoie de temps en temps à l'ordinateur. Nous savons tous qu'un administrateur système paresseux peut écrire un script pour envoyer l'entrée au programme lorsqu'elle est demandée, afin que l'administrateur système puisse continuer de fonctionner plus tôt. La machine d'interaction n'a aucun moyen de savoir s'il y a vraiment un opérateur en direct sur la console, ou si l'entrée est acheminée depuis un autre programme.

Avoir toutes les entrées d'interaction préparées à l'avance équivaut, en termes théoriques, à avoir toutes les entrées sur une bande distincte utilisée par une machine Oracle Turing. Chaque fois que l'ordinateur demande normalement une interaction à l'opérateur, la machine lit à partir de la bande d'entrée. Si la chose lue sur la bande semble invalide d'une manière ou d'une autre, la machine de Turing fait exactement ce que la machine d'interaction ferait en recevant cette entrée.

Je suppose que Wagner est conscient de la possibilité d'utiliser des bandes oracle pour coder l'entrée, vous devez donc prendre ses commentaires avec un grain de sel, ou vous devez demander ce qu'il signifie réellement. Je pense que les gens qui pensent à l'interaction sont généralement préoccupés par deux choses:

  • Les "vrais" ordinateurs ont une interaction, mais pas les algorithmes définis par Turing. Nous pouvons contourner cela en codant l'entrée sur les bandes oracle, mais cela ne correspond toujours pas à la façon dont les vrais ordinateurs fonctionnent. Il pourrait être intéressant d'étudier des modèles de calcul qui sont plus étroitement alignés avec de vrais ordinateurs.

  • Les algorithmes basés sur Oracle ne sont pas souvent pris en compte dans l'informatique au jour le jour car les ordinateurs normaux ne sont pas fournis avec un "oracle" magique pour fournir des données. Mais nous pourrions peut-être simplement utiliser une personne comme oracle. Si la personne comprend les données demandées, elle peut même être en mesure d'aider l'algorithme, améliorant ainsi ses performances. En d'autres termes, un humain peut être en mesure de fournir une bande oracle utile plutôt qu'une simple bande aléatoire, et en principe, cela pourrait conduire à des méthodes de calcul plus rapides ou plus puissantes que celles qui ne sont pas basées sur oracle. Une chose similaire se produit avec le calcul aléatoire, après tout, où la machine reçoit une séquence de bits aléatoires en tant qu'entrée supplémentaire.

Carl Mummert
la source
Les bandes Oracle ne modélisent pas correctement l'interaction. Pensez à essayer de prouver qu'un système informatique ne divulgue pas d'informations privées. Cela ne peut pas être formalisé en termes de MT avec une bande Oracle fixe, car la propriété dépend de la caractérisation du calcul que l'environnement peut faire - exactement ce que nous abstenons avec une bande Oracle.
Neel Krishnaswami
Cela dépend de ce que vous entendez par «correctement modéliser». Certains articles (par exemple de la communauté de l'hypercalcul) semblent suggérer que l'interaction élargit en quelque sorte l'ensemble des fonctions calculables. Ce qu'il fait, exactement de la même manière que le calcul Oracle. Bien sûr, vous ne pouvez pas utiliser de MT pour étudier les propriétés de l'environnement de calcul réel; si vous voulez savoir si le processeur de votre ordinateur est bogué, il ne sera pas utile de l'ignorer complètement et de regarder les machines Turing. Mais pour les questions qui ne concernent que la fonction en cours de calcul, l'interaction et les oracles sont équivalents.
Carl Mummert
Non, ce n'est pas le cas: il existe des restrictions de continuité sur les interactions possibles que les bandes oracle ne modélisent pas. Si l'environnement ne peut pas voir à l'intérieur du programme, alors l'entrée qu'il fournit à l'instant ne peut dépendre que de la sortie à des moments antérieurs n . (Autrement dit, la visualisation de l'entrée en fonction de la sortie, la fonction d'entrée doit être non expansive par rapport à la métrique Cantor.) Tout comme la calculabilité "ressemble à" la topologie pour un mathématicien classique, l'interactivité "ressemble à" la topologie à la construction mathématiciens. nn
Neel Krishnaswami
Pour une analyse vraiment approfondie de cette analogie, voir Peter Hancock, Pierre Hyvernat: Programmation des interfaces et de la topologie de base. citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.919
Neel Krishnaswami
1
n
8

Turning Machines modélise le calcul, et n'a pas de concept d'interaction. En ce sens, une machine qui prend en charge l'interaction avec un système extérieur peut faire des choses qu'une machine à tourner ne peut pas faire. Mais le calcul effectué entre un bit d'entrée provenant d'une source externe peut évidemment toujours être modélisé par une machine de Turing, donc même une "machine IO" ne peut rien faire avec une entrée externe qu'une machine de Turing ne pourrait pas faire.

Dans un certain sens, une telle machine peut être en mesure de «décider» des problèmes indécidables par Turing Machines, mais seulement si vous imaginez que le système avec lequel elle interagit a des pouvoirs super-Turing-Machine et est fiable (en quelque sorte; fiabilité probabiliste serait suffisant).

Imaginez un programme pour une machine IO comme: "pour toute entrée de bande initiale, imprimez le contenu de la bande, puis lisez un symbole à partir de l'entrée extérieure; acceptez si le symbole est 1 et rejetez sinon". Ce programme peut résoudre n'importe quel problème. Mais seulement si le système extérieur avec lequel il peut interagir est capable de décider du problème; pour moi, ce n'est pas une façon très intéressante de dire que la machine IO est capable de résoudre des problèmes indécidables par Turing Machines.

Je pense qu'il serait toujours possible de représenter un calcul interactif en imaginant une machine qui prend en entrée sur sa bande un encodage d'une configuration antérieure avec une entrée extérieure, et que la machine s'arrête avec sa bande contenant un encodage d'une configuration ensemble avec sortie. Ensuite, le processus d '«exécution d'un programme» exécute à plusieurs reprises cette machine de Turing de manière mécanique, la seule partie «non mécanique» étant toutefois l'entrée extérieure qui provient. Je suis certain que vous pourriez prouver que si un tel système obtenait son entrée en donnant sa sortie à une autre machine de Turingconfiguré pour fonctionner de manière similaire, le système combiné a des puissances de calcul identiques à une seule machine de Turing. Je trouve qu'un argument convaincant selon lequel le calcul interactif n'est pas plus puissant que le calcul non interactif, à moins que le système avec lequel le calcul interagit soit plus puissant qu'une machine de Turing .


Il existe cependant un sens non théorique dans lequel l'interactivité peut accroître la capacité d'un ordinateur à résoudre des problèmes. Il y a beaucoup de choses que les humains font très précisément que nous ne savons pas comment faire pour que les ordinateurs fonctionnent très bien. Mais il y a aussi beaucoup de choses pour lesquelles les humains sont des ordures que nous pouvons faire faire aux ordinateurs. La combinaison de ces deux peut conduire à des projets tels que reCaptcha , qui numérise efficacement automatiquement les livres en éliminant les problèmes de reconnaissance des mots aux humains dans les cas difficiles. Le système informatique + travail humain qui en résulte aboutit à un résultat qui n'est actuellement pas réalisable avec le calcul seul ou le travail humain seul.

Ben
la source
8

L'ACM a organisé récemment le symposium Ubiquity « Qu'est-ce que le calcul? »dans lequel Peter Wegner a publié un article qui reflète son point de vue sur l'informatique interactive.

Voici deux extraits de l'article de Peter Wegner:

Un nouveau concept, absent des premières machines de Turing, est le «calcul interactif», qui permet l'interaction avec l'environnement pendant le calcul.

Les machines d'interaction peuvent effectuer des formes informatiques plus puissantes que les machines de Turing et peuvent effectuer le type de réflexion proposé par Turing car l'interaction améliore leurs performances par rapport à celles des machines de Turing.

Cependant, Fortnow, qui a un article dans le même symposium, semble être en désaccord avec les vues de Wegner et pense que l'informatique interactive n'offre aucune puissance supplémentaire sur les machines de Turing.

Pour ajouter au mélange, il semble que nous débattions et définissions encore le calcul. Moshe Vardi a un article, Qu'est-ce qu'un algorithme?, Communications of the ACM, Vol. 55, n ° 3, mars 2012.

Vardi présente deux nouvelles définitions d'algorithmes. Le premier est proposé par Gurevich et le second par Moschovakis.

Gurevich a soutenu que chaque algorithme peut être défini en termes de machine à états abstraite.

Moschovakis, en revanche, a soutenu qu'un algorithme est défini en termes de récurseur, qui est une description récursive construite sur des opérations arbitraires prises comme des primitives.

Mohammad Al-Turkistany
la source
6

Je ne pense pas que les modèles avec IO soient "plus puissants" que les machines Turing, ils modélisent simplement des choses différentes.

En théorie, vous pourriez voir les E / S comme un oracle (bruyant?). Avec un oracle parfait, vous pouvez utiliser des fonctions non calculables de Turing; mais d'où vient l'oracle? Les humains sont le seul choix "super-Turing" (s'il y en a) et nous sommes connus pour être très peu fiables.

Une classe de programmes qui correspondent à ce modèle sont les assistants de preuve interactifs (par exemple Isabelle / HOL , Coq ). Ils traitent des espaces de preuve indécidables mais (sans doute) chaque preuve peut être trouvée (et vérifiée) avec une entrée utilisateur appropriée.

Raphael
la source
Les machines de Turing avec oracles sont donc plus puissantes que les machines de Turing sans elles et les machines de Turing avec oracles peuvent modéliser l'interaction. La réponse semble donc être oui.
Dave Clarke
1
@DaveClarke Si vous considérez des oracles parfaits, oui.
Raphael
2
Je pense qu'une machine (ou un programme) sans aide (par n'importe quelle forme d'oracle ou d'entrée) pourrait en principe trouver toutes les preuves. Il y a deux problèmes: (1, théorique): il ne sera jamais en mesure de vérifier qu'une déclaration n'a pas de preuve, et (2, pratique): générer aveuglément des preuves dans l'espoir de tomber sur une déclaration donnée est si terriblement inefficace que personne veut essayer, et donc les assistants de preuve préfèrent une recherche guidée, abandonnant le succès "assuré" au cas où une preuve existe.
Marc van Leeuwen
2
Comme le souligne Ben dans sa réponse, la bonne façon de voir les choses n'est pas "les machines de Turing avec des oracles sont plus puissantes"; les machines elles-mêmes font juste des choses calculables. La bonne façon de voir les choses est "certains oracles ne sont pas calculables, et donc à partir de ces oracles nous pouvons calculer des choses que nous ne pouvons pas calculer sans oracle". La force de calcul vient de l'oracle, plutôt que de la machine.
Carl Mummert
Il semble que les machines de Turing avec oracles soient la chose la plus puissante. Pourquoi même s'embêter avec de nouvelles définitions?
saadtaame