Y a-t-il un nom pour «des choses physiques à partir desquelles on peut construire une machine de Turing»?

16

L'une des choses étonnantes de l'informatique est que l'implémentation physique est en quelque sorte «hors de propos». Les gens ont réussi à construire des ordinateurs à partir de plusieurs substrats différents - relais, tubes à vide, transistors discrets, etc. Les gens pourraient bientôt réussir à construire des ordinateurs Turing-complets à partir de matériaux optiques non linéaires, de diverses biomolécules et de quelques autres substrats. En principe, il semble possible de construire un ordinateur de billard-ball .

Cependant, le substrat physique n'est pas complètement hors de propos. Les gens ont constaté que certains ensembles de composants - en particulier, la logique de résistance de diode - sont "incomplets": peu importe combien d'entre eux vous connectez à une alimentation et les uns aux autres, il y a certaines choses très simples qu'il ne peut pas faire. (La logique diode-résistance peut implémenter AND, OR, mais échoue à implémenter NOT). De plus, certains modes de connexion des composants - en particulier les perceptrons monocouches - sont "incomplets": il y a certaines choses très simples qu'ils ne peuvent pas faire. (Un perceptron monocouche peut implémenter AND, OR, NOT, mais échoue à implémenter XOR).

Existe-t-il une expression moins gênante pour «des choses physiques à partir desquelles on peut construire une machine de Turing»? Ou au contraire, "des choses physiques qui, peu importe le nombre d'entre elles, ne peuvent pas former une machine de Turing"?

Pendant un certain temps, j'ai utilisé l'expression "ensemble fonctionnellement complet" ou "ensemble universel de portes" - ou, en parlant aux mathématiciens, "des choses physiques qui peuvent implémenter un ensemble fonctionnellement complet" - mais on m'a dit que ce n'est pas ' t tout à fait correct. Certains ensembles de composants peuvent implémenter un ensemble fonctionnellement complet; et pourtant il n'est pas possible de construire une machine complète de Turing entièrement à partir de ces composants. Par exemple, les ampoules et les interrupteurs à commande manuelle à 4 voies peuvent mettre en œuvre un ensemble fonctionnel complet (ET, OU, NON, XOR, etc.); et pourtant il n'est pas possible de construire une machine complète de Turing entièrement à partir d'interrupteurs et d'ampoules, car la sortie (électrique ou optique) de l'une ne peut pas être introduite dans l'entrée (rotative mécaniquement) de l'autre.

en relation: Y a - t-il un nom officiel pour une notion de "réutilisable universel"? et Y a - t-il un nom pour «des puces à partir desquelles on peut construire un CPU»?

David Cary
la source
1
Ce n'est pas une réponse mais je ne peux pas poster de commentaires et j'ai ressenti le besoin de donner le lien vers cette incroyable bande dessinée xkcd: [A Bunch of Rocks] [1] qui est liée à cette question :). [1]: xkcd.com/505
Zenon

Réponses:

3

Je crois qu'un terme approprié est "une implémentation physique de Turing Machine".

PNP, il est donc peu probable qu'un informaticien puisse les résoudre.

Vous pouvez en savoir plus dans l'article de Scott Aaronson NP-complete Problems and Physical Reality , en particulier dans la section informatique analogique et relativité.

Vous pouvez également trouver une implémentation lego (avec bande finie) sur la page suivante: http://legoofdoom.blogspot.com/

chazisop
la source
+1 pour les Legos - whee! J'espérais trouver une phrase un peu plus facile à dérouler que «Une implémentation physique d'une machine de Turing peut être composée de cet ensemble de pièces» - mais c'est encore beaucoup mieux que les alternatives que j'ai vues jusqu'à présent.
David Cary
4

La physique modélise la réalité avec des théories qui définissent un concept d'état dépendant du temps associé à un système et un opérateur d'évolution temporelle qui décrit comment cet état évolue. Dès que vous trouvez un système physique qui (après une discrétisation de l'espace d'état) implémente l'espace d'état de votre machine Turing, et qui comporte des termes d'interaction qui implémentent (peut-être après une certaine discrétisation temporelle) l'évolution du temps en fonction de la table de transition d'état de votre machine Turing sur son espace d'état, vous avez trouvé un modèle physique Turing complet de votre système. Ainsi, vous pouvez dire, votre système "est" Turing-complet.

Lorsque vous regardez l'informatique quantique, vous trouverez des discussions sur les implications des théories physiques sur le modèle de calcul de Turing. Par exemple, les théories physiques doivent être réversibles. Une propriété qui n'est pas partagée par les machines Turing ordinaires. Pourtant, il n'y a pas de perte de généralité, car toute machine de Turing peut être simulée par une machine réversible, avec des frais généraux qui peuvent faire un compromis entre le temps et l'espace, etc.

Martin Schwarz
la source
Ce texte regorge de concepts et d'une terminologie intéressants. Hélas, je ne vois aucune expression ici que je puisse utiliser comme "Ceci est un ensemble de composants <phrase>, alors que ce sont des ensembles de composants <nr-phrase>".
David Cary
3

Je pensais simplement souligner que l'exhaustivité d'un support physique pour simuler la logique requise pour fabriquer une machine informatique complète Turing peut être établie uniquement par sa capacité à incarner une porte NAND, car toutes les autres portes peuvent être dérivées des portes NAND (une pourrait demander ce qui comprend alors les portes NAND, et c'est une question très intelligente, mais ce sont les portes NAND tout le long!).

Vous devriez regarder le travail de Charles Babbage et les gens qu'il a inspirés. Babbage a fait un ordinateur physique pour tabuler les fonctions polynomiales en tableaux imprimés pour les index mathématiques (à l'époque, vous aviez des piles de livres qui n'avaient que des noms de fonction suivis de feuilles de valeurs f (x)). Ce dernier a commencé à travailler sur ce qui sont devenus un ordinateur complet de Turing utilisant des cames à crémaillère et autres. Son fils, je crois, a continué son travail et la seule manifestation physique de leurs efforts combinés était une ALU mécanique pleinement fonctionnelle qui est la base de ces calculatrices mécaniques que vous connaissez peut-être ou non. Cependant, le financement de ces projets est tombé sous la forme d'un ordinateur mécanique de la taille et de la manière dont ils pouvaient être réalisés à cette époque était très peu pratique. Cependant, depuis lors, et en particulier lors d'événements récents, les gens ont traversé et poursuivent les recherches de Charles Babbage. Cette approche peut faire rire le dernier mot, car il y a ceux qui pensent que la seule façon de rendre les processeurs série plus rapides qu'ils ne le seraient actuellement serait de mettre en œuvre certaines de ces approches mécaniques dans un processeur afin d'éviter les problèmes liés à l'électromagnétisme à une échelle inférieure à celui que nous utilisons maintenant. La mécanique fonctionne à n'importe quelle échelle en apparence.

De même, des travaux ont été consacrés à ce qu'on appelle l'ordinateur quantique, qui cherche à faciliter les grands calculs par le biais de la théorie quantique, je ne sais pas exactement comment tout cela fonctionne. Mais il fait appel physiquement aux expériences de physique des particules qui s'appuient sur la théorie quantique.

Il y a, je suis sûr, beaucoup plus de médiums informatiques différents à explorer, même des roches dans le désert, mais je n'en ai aucune expérience.

acp10bda
la source
Les ampoules et interrupteurs d'éclairage peuvent mettre en œuvre la NAND. Il y a une configuration de 2 interrupteurs d'éclairage ordinaires et une ampoule de sortie (et une deuxième ampoule cachée) où l'ampoule de sortie reste LUMINEUSE sauf lorsqu'un humain met les deux interrupteurs sur ON, puis l'ampoule de sortie devient FONCE. Hélas, il n'est apparemment (?) Pas possible de construire une machine complète de Turing entièrement à partir d'interrupteurs et d'ampoules. Y a-t-il un terme que je peux utiliser qui inclut la NAND 74HC132 mais exclut la NAND des interrupteurs et des ampoules?
David Cary
Eh bien, le problème est que l'entrée est mécanique et la sortie est électrique, donc les commutateurs sont comme une porte nand de conversion entre deux domaines (cinétique en électronique). En supposant qu'il fonctionne comme un nandgate, vous POUVEZ en faire un ordinateur complet Turing, c'est juste que vous devrez faciliter la conversion entre ces deux supports pour que la sortie d'une porte soit entrée à une autre, peut-être un interrupteur motorisé, mais ouais peu pratique. Un terme que vous pourriez utiliser que je vais simplement maquiller maintenant est nandgate du même milieu, qui stipule que l'entrée et la sortie doivent être dans le même milieu.
acp10bda
+1 bonne idée - il suffit de créer un terme et de le définir comme étant exactement le terme que je recherche. L'ensemble {(une boîte avec 2 interrupteurs d'éclairage d'entrée et une ampoule de sortie qui implémente AND), (un interrupteur motorisé activé par la lumière qui implémente NOT)} est un ensemble en cascade universel d. Mais l'ensemble {ampoules, interrupteurs d'éclairage} seul n'est pas un ensemble en cascade d-universel.
David Cary
Est-il possible de construire une machine Turing à partir de choses qui ne sont pas des nandgates de même milieu?
David Cary
Désolé pour le retard de cette réponse, mais oui. Une machine de Turing pourrait être fabriquée à partir de n'importe quel assemblage de composants en utilisant n'importe quelle variété de supports d'entrée et de sortie tant que les composants sont disposés de telle manière que le résultat est un mécanisme complet de Turing. Cependant, étant donné que le support de calcul deviendrait si follement variant et potentiellement très intéressant à regarder, je voudrais faire référence à un tel mécanisme comme un mécanisme complet de Rube-Goldberg-Turing. :)
acp10bda