J'ai construit un ordinateur mécanique alimenté par des billes. Quelles sont ses limites théoriques?

8

Au cours des deux dernières années, j'ai construit un ordinateur mécanique alimenté par des billes et en ai fait un jeu. Il est similaire à l'ancien Digi-Comp II, à l'exception de deux différences clés:

  1. Les pièces sont repositionnables sur la carte.
  2. Vous pouvez connecter plusieurs «bits» ensemble à l'aide d'engrenages. Lorsqu'un de ces bits est retourné, il retourne les autres bits qui lui sont connectés.

Le lien ci-dessus décrit comment cela fonctionne. Ma question est, quelles sont ses limites théoriques? Mes connaissances théoriques en informatique sont faibles, veuillez donc ELI5.

edit: je ne suis pas intéressé par les limites évidentes: la vitesse (ne va gagner aucune course là-bas ...), la taille du plateau ou le nombre de billes. Je suis plus intéressé par ses limites théoriques. Il serait peut-être utile de le diviser en deux questions:

  1. Comment peut-on prouver (ou réfuter) que Turing est complet?
  2. Si plus de 3 embouts d'engrenage sont connectés ensemble, le frottement devient trop important pour qu'une bille puisse les tourner tous en même temps. Cela crée-t-il des limitations supplémentaires?

Merci - je suis vraiment ravi de lire vos réponses! J'y pense depuis longtemps.

complexity-theory turing-machines computer-architecture computation-models Paul Boswell
la source
3
Voulez-vous envisager un modèle idéalisé (taille de grille infinie, infiniment de billes) ou la machine spécifique à portée de main? En regardant la mélagne des étiquettes que vous avez choisies, pouvez-vous préciser quelles questions vous souhaitez répondre? Que peut-on calculer? À quelle vitesse les choses peuvent-elles être calculées? Quelles questions sur l'architecture avez-vous en tête?
Raphael
1
La façon la plus simple d'affiner les capacités de votre modèle est de répondre à ces questions. 1) Que sont les entrées et sorties? 2) Quelles portes logiques pouvez-vous modéliser? Je demande 2) parce qu'il est clair que vous n'avez pas d'ordinateur universel là-bas; chaque configuration de carte est un programme fixe, et cela correspond étroitement aux circuits. Donc, si vous pouvez simuler n'importe quel ensemble complet de portes (par exemple les portes NAND), vous avez un modèle complet de Turing (en supposant tout ce qui est infini). Comme vous n'avez pas de composant statique avec deux entrées et une seule sortie, je ne vois pas immédiatement ce qui se passe.
Raphael
2
Cela dit, projet intéressant! Veuillez nous en informer dans Computer Science Chat lors de son lancement.
Raphael
3
Dans la vidéo, vous dites: si vous faites une carte assez grande, elle peut faire ce que n'importe quel ordinateur peut faire. Eh bien, oui et non: avec un ordinateur, vous pouvez (théoriquement) construire une carte assez grande, mais avec une carte, vous pouvez construire un ordinateur qui a besoin d'une carte plus grande - et cela signifie que vos cartes ne sont pas complètes. Pour être complet, il faut opérer sur une mémoire arbitrairement grande , ce que vos cartes ne peuvent pas faire. Chaque machine de Turing est la limite d'une série infinie de machines de Turing à bande finie, mais cela ne rend pas les machines de Turing à bande finie Turing complètes.
reinierpost
2
Si vous intégrez l'agrandissement d'une planche au fonctionnement de la machine, elles deviennent Turing complètes.
reinierpost

Réponses:

3

Ce que vous avez en ce moment est un ordinateur concret. Nous ne pouvons pas le comparer à un modèle informatique tant qu'il n'est pas formalisé correctement.

Mon intuition est que la carte pourrait être modélisée comme une architecture de flux de données . Les modèles de calcul conçus selon ce paradigme peuvent être complets à Turing, mais (comme cela a été dit dans les commentaires) aucun ordinateur concret ne sera jamais équivalent à Turing, et je ne pense pas que vous devriez vous en inquiéter. Tous les vrais ordinateurs ne sont que des métaphores de travail (imparfaites) de modèles informatiques formels.

Si vous venez à l'idée d'imiter de plus près une machine de flux de données équivalente à Turing, il y a quelques problèmes qui pourraient être résolus afin de "renforcer la métaphore", pour ainsi dire. L'introduction des cycles et de la composition des machines serait à mon avis les deux choses les plus importantes, mais je pense que votre machine est déjà assez étonnante. Il remplit très bien sa fonction et ces "améliorations" pourraient sacrifier sa facilité d'utilisation.

André Souza Lemos
la source
Merci! Et très utile! Je ne connaissais pas la distinction entre l'architecture de flux de données et, disons, l'architecture Von Neumann auparavant. J'ai juste imaginé que, si la planche était plus grosse, une architecture Von Neumann pourrait être construite. Avez-vous une chance de proposer une définition ou un lien vers ce que vous entendez par «cycles» et «composition»?
Paul Boswell
Pour les cycles, imaginez qu'il existe un moyen de renvoyer les billes, au début ou à une mémoire intermédiaire au milieu. Cela vous permettrait de calculer certains types de fonctions récursives primitives. La composition des machines est similaire à la composition des fonctions, imaginez que vous pouvez brancher la sortie d'une carte à l'entrée des autres.
André Souza Lemos
Un ordinateur von Neumann est un grand cycle.
André Souza Lemos