La Turing completeness (complétude de Turing) est une propriété fondamentale d’un système computationnel qui signifie qu’il peut exécuter n’importe quel algorithme calculable, étant donné suffisamment de temps et de mémoire. En crypto, ce concept est crucial car il distingue les blockchains capables d’exécuter des smart contracts complexes de celles qui ne le peuvent pas.
Ethereum est la première blockchain Turing-complete majeure. Sa machine virtuelle (EVM) peut exécuter n’importe quel programme : des simples transferts de tokens aux protocoles DeFi complexes, en passant par les jeux on-chain et les systèmes de gouvernance. Le langage Solidity permet aux développeurs d’écrire des programmes arbitrairement complexes déployés sous forme de smart contracts.
Bitcoin, en revanche, est volontairement Turing-incomplet. Son langage Script est limité et ne supporte pas les boucles (loops), ce qui signifie que certains algorithmes ne peuvent pas y être implémentés. Ce choix de design est délibéré : il élimine le risque de boucles infinies et rend les transactions Bitcoin plus prévisibles et plus sûres, au prix d’une programmabilité réduite.
Le « halting problem » (problème de l’arrêt) est le défi théorique central de la Turing completeness : il est mathématiquement impossible de déterminer à l’avance si un programme Turing-complete terminera ou entrera dans une boucle infinie. Ethereum résout ce problème avec le mécanisme de gas : chaque opération coûte du gas, et quand le gas est épuisé, l’exécution s’arrête. Cela garantit que tout programme EVM finira par s’arrêter, même s’il contient une boucle infinie.
Dans l’écosystème blockchain, la Turing completeness est un spectre plutôt qu’un binaire. Des chaînes comme Solana, Avalanche, Cardano et Polkadot sont toutes Turing-complete mais avec des langages et des architectures différents. Le débat entre expressivité (Turing-complete) et sécurité (Turing-incomplet) reste fondamental dans la conception des blockchains.