Turing terminé

Turing Complete fait référence à une machine qui, avec suffisamment de temps et de mémoire ainsi que les instructions nécessaires, peut résoudre n'importe quel problème de calcul, quelle que soit sa complexité. Le terme est normalement utilisé pour décrire les langages de programmation modernes car la plupart d'entre eux sont Turing Complete (C++, Python, JavaScript, etc.).

Qu'est-ce qu'une machine de Turing ?

Avant les ordinateurs modernes, Alan Turing avait émis l'hypothèse qu'il y aurait un jour une machine capable de résoudre n'importe quel problème. Cette machine est devenue connue sous le nom de machine de Turing.

Alan a imaginé sa machine comme un long morceau de bande avec des informations écrites dessus sous forme de code binaire (1 et 0). La machine aurait également une tête de lecture/écriture qui se déplace le long de la bande en lisant chaque carré, un par un. Le code poserait à la machine un problème de calcul, et la bande serait aussi longue que nécessaire pour parvenir à une solution.

Lorsque la tête se déplace le long de la bande, la machine suit des instructions simples qui régissent sa réaction. Il lit la bande, suit les instructions et effectue une certaine action pour écrire un nouveau code au fur et à mesure qu'il avance. Ce nouveau modèle de code est la réponse au problème. La machine hypothétique de Turing pourrait répondre à n'importe quel problème de calcul qui pourrait être exprimé en code (et qui avait une réponse calculable).

Un appareil ou un langage de programmation est considéré comme Turing complet lorsqu'il peut répliquer une machine de Turing en exécutant n'importe quel programme ou en résolvant tout problème que la machine de Turing pourrait exécuter ou résoudre. D'un autre côté, si un appareil ou un langage de programmation n'est pas capable de le faire, on dit qu'il est incomplet de Turing.

Une calculatrice simple est un exemple de système qui est incomplet de Turing car il ne peut effectuer que quelques types de calculs. En revanche, une calculatrice scientifique programmable (capable d'effectuer toutes sortes de calculs) peut être considérée comme une machine de Turing.

Blockchain et complétude de Turing

Alors que certaines applications de la technologie blockchain sont Turing Complete, d'autres sont Turing Incomplete. Cela varie selon la technologie de script mise en œuvre. Par exemple, le langage de script utilisé dans Bitcoin est intentionnellement conçu comme Turing Incomplete car il sert son objectif et une complexité accrue pourrait potentiellement introduire des problèmes. En restant simple, les développeurs peuvent prédire avec une grande précision comment il va réagir dans le nombre fini de situations dans lesquelles il est utilisé.

Ethereum, en revanche, est construit comme une blockchain Turing Complete. Ceci est important car il doit comprendre les accords qui composent les contrats intelligents. En étant Turing Complete, Ethereum a la capacité de comprendre et de mettre en œuvre tout accord futur, même ceux qui n'ont pas encore été pensés. En d'autres termes, l'exhaustivité de Turing d'Ethereum signifie qu'il est capable d'utiliser sa base de code pour effectuer pratiquement n'importe quelle tâche, tant qu'il dispose des instructions correctes, de suffisamment de temps et de puissance de traitement.