Est une interaction plus puissante que les algorithmes?

cs.stackexchange https://cs.stackexchange.com/questions/438

  •  16-10-2019
  •  | 
  •  

Question

Je l'ai entendu la devise interaction est plus puissante que les algorithmes de Peter Wegner . La base de l'idée est qu'un (classique) Machine de Turing ne peut pas gérer l'interaction, qui est, la communication (entrée / sortie) avec le monde extérieur / environnement.

  

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

Était-ce utile?

La solution

machines de Turing peuvent gérer l'interaction très bien, en utilisant des bandes d'oracle. Il fonctionne sont suit: à partir du point de vue d'un ordinateur sur lequel l'interaction entre les poignées, l'entrée de l'opérateur est tout simplement une autre séquence de bits qu'elle a envoyé à l'ordinateur de temps en temps. Nous savons tous qu'un sysadmin paresseux pourrait écrire un script pour envoyer l'entrée au programme quand il est demandé, de sorte que le sysadmin pourrait aller en pause plus tôt. La machine d'interaction n'a aucun moyen de savoir s'il y a vraiment un opérateur en direct à la console, ou si l'entrée est canalisée d'un autre programme.

vu toutes les entrées d'interaction préparé à l'avance est le même, en termes théoriques, comme ayant toutes les entrées sur une bande séparée qui est utilisée par une machine de Turing oracle. Chaque fois que l'ordinateur demanderait normalement l'interaction de l'opérateur, la machine se lit à la place de la bande d'entrée. Si la chose lu sur la bande semble invalide d'une certaine façon, la machine de Turing fait exactement ce que la machine d'interaction ferait sur la réception de cette entrée.

Je suppose que Wagner est au courant de la possibilité d'utiliser des bandes d'oracle à l'entrée de code, vous devez donc prendre ses commentaires avec un grain de sel, ou vous devez demander ce qu'il en fait des moyens. Je crois que les gens qui pensent à l'interaction sont généralement inquiets de deux choses:

  • ordinateurs « réels » ont une interaction, mais des algorithmes tels que définis par Turing ne sont pas. Nous pouvons contourner ce problème en codage de l'entrée sur les bandes d'oracle, mais cela ne correspond toujours pas la façon dont fonctionnent les ordinateurs réels. Il pourrait être agréable de modèles d'étude de calcul qui sont plus étroitement alignés avec les ordinateurs réels.

  • algorithmes basés sur Oracle ne sont pas souvent pris en compte dans jour le jour de calcul parce que les ordinateurs normaux ne viennent pas avec une magie « oracle » pour fournir des données. Mais nous pourrions être en mesure d'utiliser en fait juste une personne comme l'oracle. Si la personne comprend les données qui sont demandés, ils peuvent même être en mesure d'aider l'algorithme le long, améliorant ainsi ses performances. En d'autres termes, un homme peut être en mesure de fournir une bande d'oracle utile plutôt que de simplement un hasard, et en principe cela pourrait conduire à des méthodes de calcul plus rapide ou plus puissant par rapport à celles non basées sur Oracle. La même chose se produit avec l'informatique randomisée, après tout, où la machine est donnée à une séquence de bits aléatoires en tant qu'entrée supplémentaire.

Autres conseils

En ce calcul du modèle des machines, et ne dispose pas d'un concept d'interaction. En ce sens, une machine que l'interaction soutenue avec un système extérieur peut faire les choses d'une machine tournant ne peut pas. Mais le calcul fait entre bit d'entrée à partir d'une source extérieure ne peut évidemment toujours être modélisé par une machine de Turing, de sorte que même une « IO Machine » ne peut rien faire avec à l'extérieur entrée qu'une machine de Turing ne pouvait pas faire.

Dans un certain sens, une telle machine peut être en mesure de « décider » des problèmes qui sont indécidable par machines de Turing, mais seulement si vous imaginez que le système, il interagit avec a des pouvoirs super-Turing-Machine et est fiable . (d'une certaine manière, la fiabilité probabiliste serait suffisant)

Imaginez un programme pour une machine IO comme: « pour toute entrée de bande initiale, imprimer le contenu de la bande, puis lire un symbole de l'entrée à l'extérieur, accepter si le symbole est 1 et rejeter autrement ». Ce programme peut décider tout problème . Mais que si le système extérieur peut interagir avec est capable de décider le problème; pour moi, c'est pas une façon très intéressante de dire que l'IO machine est en mesure de décider des problèmes qui sont indécidable par machines de Turing.

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 codage d'une certaine configuration avant avec une entrée à l'extérieur, et ont l'arrêt de la machine avec sa bande contenant un codage de une configuration en même temps que la production. Ensuite, le processus de « l'exécution d'un programme » est en cours d'exécution à plusieurs reprises cette machine de Turing de façon mécanique, avec la seule partie « non-mécanique » étant cependant l'entrée de l'extérieur provient. Je suis certain que vous pourriez prouver que si un tel système a obtenu son entrée en donnant sa sortie à une autre machine de Turing mis en place pour fonctionner de manière similaire, le système combiné a des pouvoirs de calcul identiques à un unique machine de Turing. Je trouve qu'un argument convaincant que le calcul interactif est plus puissant que le calcul non interactif, à moins que le système de calcul interagit avec est plus puissant qu'une machine de Turing .

Il y a un sens non théorique où l'interactivité peut ajouter à la capacité d'un ordinateur pour résoudre les problèmes, cependant. Il y a beaucoup de choses que les humains font de façon très précise que nous ne savons pas comment les ordinateurs à faire très bien. Mais il y a aussi beaucoup de choses que les humains sont des ordures à ce que nous pouvons obtenir des ordinateurs à faire. La combinaison de ces deux peut conduire à des projets tels que reCaptcha , qui est effectivement numérisation automatique des livres par l'agriculture les problèmes de reconnaissance de mots à l'homme dans les cas difficiles. Le système résultant de l'ordinateur + le travail humain aboutit à un résultat qui est actuellement impossible de réaliser avec soit le seul calcul ou le travail de l'homme seul.

Récemment ACM a tenu colloque Ubiquity ' Qu'est-ce calcul? ' dans laquelle 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, manque de premières machines de Turing, est « Interactive Computing », qui accueille l'interaction avec l'environnement pendant le calcul.

     

machines d'interaction peut effectuer des formes plus puissantes de calcul que les machines de Turing, et peut effectuer le genre de pensée proposée par interaction, car Turing améliore leurs performances par rapport à celle des machines de Turing.

Cependant, Fortnow, qui a un article dans le même colloque, semble être en désaccord avec les vues Wegner et estime que l'informatique interactive ne propose pas de puissance supplémentaire par rapport aux machines de Turing.

Pour ajouter au mélange, il semble que nous sommes en train de débattre encore et la définition de calcul. Moshe Vardi a un article, Qu'est-ce qu'un algorithme ?, Communications de l'ACM, Vol. 55, n ° 3, Mars de 2012.

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

  

Gourevitch a fait valoir que chaque algorithme peut être défini en termes d'une machine d'état abstrait.

     

Moschovakis, en revanche, a soutenu que l'algorithme est défini en termes d'un recursor, qui est une description récursive construit au-dessus des opérations arbitraires prises comme primitives.

Je ne pense pas que les modèles avec IO sont « plus puissants » que les machines de Turing, ils modélisent juste des choses différentes.

En théorie, vous pouvez voir IO (noisy?) Oracle. Avec un oracle parfait, vous pouvez ordinateur fonctions de Turing non calculable; mais où trouver l'oracle de? Les humains sont la seule « super-Turing » choix (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 assisstants de preuve interactive (par exemple Isabelle / HOL , Coq ). Ils traitent avec des espaces de preuve indécidables, mais (sans doute) toutes les preuves sont disponibles (et vérifié) avec l'entrée d'utilisateur approprié.

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top