La thèse de Church-Turing prétend que tout problème calculable peut être calculé par une machine de Turing. Cela signifie qu’un ordinateur plus puissant qu’une machine de Turing n’est pas nécessaire pour résoudre des problèmes calculables. L’idée de la complétude de Turing est étroitement liée à cela. Un système est Turing complet s’il peut calculer toutes les fonctions calculables de Turing. Un langage de programmation Turing complet est théoriquement capable d’exprimer toutes les tâches réalisables par les ordinateurs ; presque tous les langages de programmation sont Turing complets.
En général, pour qu’un langage impératif soit Turing-complet, il faut :
- Une forme de répétition conditionnelle ou de saut conditionnel (par exemple, des boucles
while, conditionnelsif+goto) - Un moyen de lire et d’écrire une forme de stockage (par exemple, des variables, une bande)
Pour vérifier si quelque chose est terminé, voyez si vous pouvez implémenter une machine de Turing à l’intérieur. En d’autres termes, vérifiez les conditions suivantes :
1) Peut prendre des décisions — La « langue » qui ne prend en charge que +, -, *, et / sur des entiers n’est pas Turing complet car il ne peut pas faire un choix basé sur son entrée, mais une machine de Turing peut le faire.
2) Peut fonctionner pour toujours — Turing a prouvé qu’on ne peut pas prédire si un programme se terminera en le simulant sur un ordinateur. En termes simples, nous ne pouvons pas prédire le chemin d’un programme sans l’exécuter. Les systèmes complets de Turing peuvent fonctionner dans des « boucles infinies », un terme utilisé (en simplifiant à l’excès) pour décrire un programme qui ne se termine pas.
Si nous prenions Java, Javascript ou Python et supprimions la possibilité de faire n’importe quelle sorte de boucle, de GOTO ou d’appel de fonction, Turing ne serait pas complet car il ne peut pas effectuer un calcul arbitraire qui ne se termine jamais. Coq est un prouveur de théorème qui ne peut pas exprimer des programmes qui ne se terminent pas, donc ce n’est pas Turing complet.
3) Peut utiliser une mémoire infinie — Un langage qui était exactement comme Java mais qui se terminerait une fois qu’il utilisait plus de 4 Go de mémoire ne serait pas Turing complet, car une machine de Turing peut utiliser une mémoire infinie. C’est pourquoi nous ne pouvons pas en fait construire une machine de Turing, mais Java est toujours un langage Turing complet car Java Langue n’a aucune restriction l’empêchant d’utiliser une mémoire infinie. C’est l’une des raisons pour lesquelles les expressions régulières ne sont pas complètes de Turing.
4) Peut lire et écrire des données dans la RAM– Un langage qui ne permet de travailler qu’avec la mémoire à travers push et pop les opérations sur une pile ne seraient pas terminées par Turing. Si j’ai une ‘langue’ qui lit une chaîne une fois et ne peut utiliser la mémoire qu’en poussant et en sautant d’une pile, il peut me dire si chaque ( dans la chaîne a son propre ) plus tard en poussant quand il voit ( et éclater quand il voit ). Cependant, il ne peut pas me dire si chaque ( a sa propre ) plus tard et tous [ has its own ] plus tard (notez que ([)] répond à ce critère mais ([]] ne fait pas). Une machine de Turing peut utiliser sa mémoire vive pour suivre ()‘sable []‘s séparément, mais ce langage avec seulement une pile ne le peut pas.
5) Peut simuler n’importe quelle autre machine de Turing — Une machine de Turing, lorsqu’on lui donne un « programme » approprié, peut prendre le « programme » d’une autre machine de Turing et le simuler sur une entrée arbitraire. Si vous aviez un langage interdit d’implémenter un interpréteur Python, ce ne serait pas Turing complet.
En bref, si un langage a une RAM infinie, une exécution conditionnelle et une certaine forme d’exécution répétée, il est probablement Turing complet.
La plupart des langages de programmation modernes (par exemple Go, Python, Java, JavaScript, Perl, etc.) sont tous complets de Turing car ils implémentent chacun toutes les fonctionnalités mentionnées ci-dessus. Ensuite, il y a des « environnements informatiques » que vous ne vous attendriez pas à être Turing Complete, mais qui le sont vraiment.
- Par exemple, les feuilles de calcul Excel sont complètes. Ce n’est pas tout à fait une surprise, car ils incluent un langage de programmation à part entière pour écrire des macros/extensions. Mais même sans l’utiliser, le langage de formule d’Excel peut être considéré comme Turing complet
- Les pierres rouges dans le jeu Minecraft définir un langage Turing-complet.
- Le jeu de la vie de Conway (avec une démo ici), une forme d’automate beaucoup plus amusante que celles sur lesquelles nous nous sommes concentrés dans ce cours, est également complet à Turing
