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

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»?

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

$P \neq NP$, 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/

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.

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.