J'ai une idée générale de la façon dont le processeur gère les instructions, mais je passe mon temps à travailler dans des langues principalement de haut niveau. Peut-être que quelqu'un qui travaille plus près du fer peut fournir des informations précieuses.
En supposant que les langages de programmation sont fondamentalement des abstractions de très haut niveau du jeu d'instructions d'un processeur, quel est le jeu d'instructions le plus basique nécessaire pour créer une machine complète turing?
Remarque: Je ne sais rien de la diversité des architectures matérielles mais - pour des raisons de simplicité - supposons qu'il s'agit d'un processeur typique avec une ALU (si nécessaire) et une pile d'instructions. *
hardware
low-level
turing-completeness
Plie d'Evan
la source
la source
Réponses:
Il s'avère que vous n'avez besoin que d' une seule instruction pour construire une machine capable de calculer Turing. Cette classe de machines qui n'ont qu'une seule instruction et sont complètes de Turing est appelée One Instruction Set Computers ou aussi en plaisantant Ultimate RISC .
la source
Il existe de nombreuses façons d'implémenter quelque chose dans lequel on peut implémenter une machine de turing.
Comme vous regardez les processeurs, celui qui est le plus applicable est probablement le modèle de machine de registre . Le plus simple d'entre eux (en termes de symboles) est le symbole à deux bandes multiples (
marketblank). Si vous optez pour quelque chose de pas tout à fait aussi ésotérique, leinc(r),dec(r)etjz(r,z)(saut si registrerest égal à zéro à l' instructionz) ouclr(r)(clairr),inc,je(i,j,z)(saut si vous inscrire i et j sont égaux à l' instruction z).J'ai vu une machine d'enregistrement qui est:
ce qui est également complet - c'est une machine à registres Minsky bien qu'elle ait d'autres contraintes sur les données dans la bande (ce doit être un nombre Gödel stockant l'état plutôt que des registres individuels)
C'est ça. Rien de plus.
Alors, pourquoi ces processeurs ultra-risc ne sont-ils pas utilisés à la place? C'est vraiment difficile d'écrire un compilateur pour eux et vous abandonnez beaucoup d'autres choses que le processeur peut faire. C'est vraiment bien d'avoir un bit à bit
and, etaddplutôt que d'essayer de tout faire avec des registres d'incrémentation et des boucles. C'est la base d'un langage de programmation préféré intitulé Brainfuck qui a 8 instructions.>incrémenter le pointeur de données<décrémenter le pointeur de données+incrémenter les données au pointeur de données-décrémenter les données au pointeur de données.sortie des données au pointeur de données,lire l'entrée, stocker les données au pointeur de données[si les données au pointeur sont nulles, au lieu de déplacer le pointeur d'instruction vers l'avant, passez-le à la commande après la]commande correspondante]si les données du pointeur ne sont pas nulles, au lieu de déplacer le pointeur d'instruction vers l'avant, faites-le revenir à la commande après la]commande correspondanteOn peut trouver des compilateurs pour Brainfuck, bien que ce ne soit vraiment pas amusant de faire des choses même simples. À moins que vous n'aimiez la frustration, qui est le but de la langue.
Lecture connexe:
la source
Je soupçonne que Post machine est la forme la plus simple d'un appareil complet de Turing. Vous avez besoin d'une alimentation en mémoire adressable par bits, d'un registre d'adresses qui pointe vers l'emplacement actuel des données et de cinq instructions:
Je ne pense pas qu'il soit facile d'inventer quelque chose de beaucoup plus simple sur le plan matériel, bien qu'il existe probablement quelque chose d'encore plus réduit.
la source
Implémentations
Cette réponse se concentrera sur des implémentations intéressantes de processeurs, compilateurs et assembleurs à jeu d'instructions unique.
movfuscator
https://github.com/xoreaxeaxeax/movfuscator
Compile le code C en utilisant uniquement
movdes instructions x86, montrant de manière très concrète qu'une seule instruction suffit.L'intégralité de Turing semble avoir été prouvée dans un document: https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf
subleq
https://esolangs.org/wiki/Subleq :
Voir également
/programming/3711443/minimal-instruction-set-to-solve-any-problem-with-a-computer-program/38523869#38523869
la source
Jörg W Mittag a dit "un", mais qu'en est-il de zéro?
Pourquoi supposez-vous qu'un "processeur" doit avoir des "instructions"?
Une machine de Turing est un processeur complet de Turing, et elle ne fonctionne pas comme telle sur des "instructions". Il a des règles , mais les règles ne sont pas des instructions extraites d'une mémoire à accès aléatoire.
Quand Alan Turing a imaginé sa machine éponyme, il cherchait le modèle de «calcul» le plus simple possible afin de pouvoir utiliser des techniques mathématiques pour répondre à la question «Qu'est-ce qui est calculable?
Il vous serait difficile de concevoir une machine équivalente à Turing plus simple qu'une machine Turing réelle.
FWIW, le type de processeur auquel vous pensez --- celui qui récupère les instructions de la mémoire, les décode et les exécute, et qui fonctionne sur les données stockées dans le même système de mémoire --- est connu comme une architecture Von Neumann
https://en.wikipedia.org/wiki/Von_Neumann_architecture
la source