Quest-ce qui rend un langage Turing-complet?

A Turing tarpit est une sorte de langage de programmation ésotérique qui sefforce dêtre Turing-complet tout en utilisant le moins déléments possible. Brainfuck est peut-être le tarpit le plus connu, mais il y en a beaucoup.

• Iota et Jot sont des langages fonctionnels avec deux et trois symboles, respectivement, basés sur Calcul combinatoire SK (I) .

• OISC ( Un ordinateur de jeu dinstructions ) désigne un type de calcul impératif qui ne nécessite quune seule instruction dun ou plusieurs arguments, généralement « soustraire et ramifier si inférieur ou égal à zéro », ou «Inverser la soustraction et sauter si emprunter». La MMU x86 implémente lancienne instruction et est donc Turing-complete.

En général, pour un langage impératif pour être Turing-complet, il lui faut:

1. Une forme de répétition conditionnelle ou de saut conditionnel (par exemple, while, if + goto)

2. Un moyen de lire et décrire une forme de stockage (par exemple , variables, bande)

Pour quun langage fonctionnel basé sur le lambda-calcul soit TC, il besoins:

1. La capacité dabstraire des fonctions sur des arguments (par exemple, abstraction lambda, citation)

2. La capacité dappliquer des fonctions à arguments (par exemple, réduction)

Il y a bien sûr dautres façons de voir le calcul, mais ce sont des modèles courants pour les bâches de Turing. Notez que les vrais ordinateurs ne sont pas des machines de Turing universelles car ils n’ont pas de stockage illimité. Ce sont à proprement parler des «machines de stockage délimitées». Si vous continuiez à leur ajouter de la mémoire, ils approcheraient de manière asymptotique les machines de Turing au pouvoir. Cependant, même les machines de stockage bornées et les machines à états finis sont utiles pour le calcul; ils ne sont tout simplement pas universels .

Strictement parlant, les E / S ne sont pas nécessaires pour lexhaustivité de Turing; TC affirme seulement quun langage peut calculer la fonction que vous voulez, pas quil peut vous montrer le résultat. En pratique, chaque langage utile a une manière dinteragir avec le monde dune manière ou dune autre.

Commentaires

• Pour les langages impératifs, des variables simples suffisent-elles? Javais limpression quune sorte de collecte (par exemple des tableaux ou des listes liées) serait nécessaire.
• @luiscubal, vous devez être en mesure de spécifier une quantité arbitraire de données. Avec des variables simples, vous pouvez représenter la quantité de données que les variables elles-mêmes ont. Que faire si vous devez représenter N + 1 éléments de données différents. On pourrait dire quavec des astuces comme les jeux de Fractran, vous pouvez le faire même avec des variables simples … mais que ‘ Ce nest pas tout à fait ce que vous ‘ demander.
• Isn ‘ t il fallait que la langue prenne en charge Boucles sans fin ?
• Re,  » chaque langue utile a un moyen dinteragir avec le monde.  » Algol 60 navait aucune manière définie dinteragir avec le monde. Toutes vos E / S dans un programme Algol 60 ont été effectuées en appelant des fonctions de bibliothèque, et les fonctions de bibliothèque peuvent être complètement différentes dans différentes implémentations. Mais, par la présente, je me retire de toute discussion sur la question de savoir si Algol 60 était  » utile.  »

Dun point de vue plus pratique: si vous pouvez traduire tous les programmes dans une langue complète de Turing dans votre langue, alors (dans la mesure où Je sais), votre langage doit être Turing-complet.Par conséquent, si vous voulez vérifier si un langage que vous avez conçu est Turing-complet, vous pouvez simplement écrire un Brainf *** dans le compilateur YourLanguage et prouver / démontrer quil peut compiler tous les programmes BF légaux.

Pour clarifier, je veux dire quen plus dun interpréteur pour YourLanguage, vous écrivez un compilateur (dans nimporte quelle langue) qui peut compiler nimporte quel programme BF vers YourLanguage (en gardant la même sémantique, bien sûr).

Commentaires

• Oui, ce serait certainement la manière la plus pratique de laborder. </sarcasm>
• @RobertHarvey a un point, mais lidée générale est assez vitale. Brainfuck sest avéré être complet et très simple comme les langages de programmation. Pour les langages de programmation non ésotériques, implémenter un interpréteur brainfuck peut être beaucoup plus facile et plus rapide que de donner une preuve rigoureuse venue de nulle part (je peux implémenter BF dans quelques lignes de Python, mais je ‘ m ne sais pas par où commencer avec une preuve formelle que Python est terminé); et des dizaines de langages ésotériques inspirés de brainfuck sont connus pour être complets car ‘ sait comment ils correspondent à brainfuck.
• @RobertHarvey: Pourquoi pas? Sûrement quelquun qui conçoit son propre langage serait capable dy écrire un compilateur BF (si cétait impératif, et de trouver un autre langage approprié sinon).
• @delnan: Vous le fera devez prouver, cependant, que votre interprète BF implémente correctement la spécification BF, IOW vous devrez prouver que votre interprète BF est, en fait, un interprète BF et non un interprète pour un langage de type BF qui pourrait ou non être Turing-complet.
• @ DarekNędza, que ‘ est juste une conséquence naturelle de la façon dont la complétude de Turing est définie; toute extension dune langue Turing Complete sera toujours Turing Complete.

Un système ne peut être considéré être Turing complet sil peut faire tout ce quune machine de Turing universelle peut. Comme on dit que la machine universelle de Turing est capable de résoudre nimporte quelle fonction calculable dans le temps, les systèmes complets de Turing peuvent, par extension, le faire également.

Pour vérifier si quelque chose est Turing complet, voyez si vous peut mettre en œuvre une machine de Turing à lintérieur. En dautres termes, vérifiez sil peut simuler ce qui suit:

1. La capacité de lire et décrire des « variables » (ou des données arbitraires) : assez explicite.
2. La possibilité de simuler le déplacement de la tête de lecture / écriture : Il ne suffit pas de pouvoir récupérer et stocker des variables. Il doit également être possible de simuler la possibilité de déplacer la tête de la bande afin de référencer dautres variables. Cela peut souvent être simulé dans les langages de programmation avec lutilisation de structures de données de tableau (ou équivalent) ou, dans le cas de certains langages tels que le code machine, la capacité de référencer dautres variables grâce à lutilisation de « pointeurs » (ou équivalent).
3. La possibilité de simuler une machine à états finis : bien que cela ne soit pas souvent mentionné, les machines de Turing sont en fait une variation des machines à états finis souvent utilisées dans le développement de lIA. Alan Turing a déclaré que le but des états est de simuler les différents modes de résolution de problèmes dune personne.
4. Un état « darrêt » : Bien quil soit souvent mentionné quun ensemble de règles doit pouvoir se répéter pour être considéré comme Turing complet, ce nest pas vraiment un bon critère puisque la définition formelle de ce quest un Lalgorithme est un état, les algorithmes doivent toujours finir par conclure. Sils ne peuvent pas conclure dune manière ou dune autre, soit il nest pas complet, soit ledit algorithme nest pas une fonction calculable. Les systèmes complets Turing qui ne peuvent techniquement pas se conclure en raison de leur fonctionnement (comme les consoles de jeux, par exemple) contournent cette limitation en étant capables de «simuler» un état d’arrêt d’une manière ou d’une autre. À ne pas confondre avec le «problème d’arrêt « , une fonction indécidable qui prouve quil » est impossible de construire un système qui pourrait détecter avec une fiabilité à 100% si une entrée donnée empêchera un autre système de se conclure.

Ce sont le vrai minimum les exigences pour quun système soit considéré comme Turing complet. Ni plus ni moins. Sil ne peut pas simuler lun de ces éléments dune manière ou dune autre, ce nest pas Turing complet. Les méthodes proposées par dautres personnes ne sont que des moyens pour atteindre la fin, car il existe plusieurs systèmes complets de Turing qui ne possèdent pas ces fonctionnalités.

Notez quil ny a pas de moyen connu de construire un véritable système complet de Turing . En effet, il n’existe aucun moyen connu de simuler véritablement l’infini de la bande de la machine de Turing dans l’espace physique.

Un langage de programmation est terminé si vous pouvez faire un calcul avec lui.Il ny a pas un seul ensemble de fonctionnalités qui rend un langage complet, donc les réponses disant que vous avez besoin de boucles ou que vous avez besoin de variables sont fausses car il y a des langues que na ni mais sont terminés.

Alan Turing a créé la machine universelle et si vous pouvez traduire nimporte quel programme conçu pour fonctionner sur la machine universelle pour sexécuter sur votre langue, cest aussi Turing complet. Cela fonctionne également indirectement de sorte que vous pouvez dire que la langue X est complète si tous les programmes pour la langue complète Y peuvent être traduits pour X puisque tous les programmes de la machine universelle peuvent être traduits en un programme Y.

La complexité temporelle , la complexité spatiale, le format dentrée / sortie facile et la facilité décriture de tout programme ne sont pas inclus dans léquation, de sorte quune telle machine peut théoriquement faire tous les calculs si les calculs ne sont pas interrompus par une perte de puissance ou la Terre avalée par le soleil.

Habituellement, pour prouver lexhaustivité, ils font un interprète pour tout langage complet avéré, mais pour que cela fonctionne, vous avez besoin de moyens dentrée et de sortie, deux choses qui ne sont vraiment pas nécessaires pour quune langue soit complète. Il suffit que votre programme puisse modifier son état au démarrage et que vous puissiez inspecter la mémoire une fois le programme arrêté.

Pour réussir un langage, il faut plus que la complétude et cest vrai pour même les bâches. Je ne pense pas que BrainFuck aurait été populaire sans , et ..

Commentaires

•  » Un langage de programmation est complet si vous pouvez faire un calcul  » Que ‘ est la thèse de Church-Turing, pas ce qui rend un langage Turing-complet.
• @Rhymoid Donc, vous voulez dire que rien nest complet à moins que vous ne puissiez faire un interpréteur? Cest-à-dire que le calcul lambda nest pas complet même sil ‘ est égal?
• Je ‘ cherche toujours une définition faisant autorité des termes équivalent de Turing et Turing-complet (et Turing-puissant). Je ‘ Jai déjà vu trop de cas, des personnes sur les babillards électroniques aux chercheurs dans leurs propres articles ‘, qui interprètent ces termes différemment.
• Quoi quil en soit, Jinterprète ‘ Turing-complete ‘ comme étant une simulation équivalente à une machine de Turing universelle (UTM; qui, à son tour, est capable de simuler nimporte quelle machine de Turing – doù ‘ universel ‘). Dans larticle de Turing ‘ de 1936, où il a présenté ses machines, il a défini la notion dUTM, et a donné une esquisse dune preuve que les UTM sont des simulations équivalentes à Church ‘ s calcul lambda. Ce faisant, il a prouvé quils avaient la même puissance de calcul. La thèse de Church-Turing affirme, en termes simples, que  » que ‘ est toute la puissance de calcul que vous ‘ Jobtiendrai jamais « .
• Il a deux définitions formelles pour Page dexhaustivité de Turing de Wikipedia . Lun nécessite des E / S, lautre ne ‘ t. Celui qui ne ‘ dit quune machine est complète si elle peut calculer toutes les fonctions calculables de Turing. Cela remet le calcul lambda à létat complet puisque vous pouvez facilement créer un programme égal en calcul lambda qui calcule la même chose que nimporte quel programme de la machine de turing.

Vous ne pouvez « pas dire sil » va boucler indéfiniment ou sarrêter.

————-

Explication: Compte tenu de certaines entrées, il est impossible de dire dans tous les cas (en utilisant une autre machine de Turing) si la chose va boucler indéfiniment ou va éventuellement sarrêter, sauf en lexécutant (ce qui vous donne une réponse si cest le cas stop, mais pas si ça boucle!).

Cela signifie que vous devez être en mesure de stocker une quantité potentiellement illimitée de données dune manière ou dune autre – il doit y avoir un équivalent à la bande infinie, peu importe comment (Sinon, il ny a quun nombre fini détats et vous pouvez alors vérifier si vous avez déjà traversé cet état avant de vous arrêter). Généralement, les machines de Turing peuvent augmenter ou réduire la taille de leur état par certains moyens contrôlables.

Puisque la machine de Turing universelle originale de Turing a un problème darrêt insoluble, votre propre machine complète de Turing doit également avoir un arrêt insoluble problème.

Les systèmes complets de Turing peuvent émuler nimporte quel autre système complet de Turing, donc si vous pouvez créer un émulateur pour un système complet de Turing bien connu dans votre système, cela prouve que votre système est également Turing complet.

Par exemple, supposons que vous vouliez prouver que Snakes & Ladders est Turing complet, étant donné un tableau avec un motif de grille infiniment répété (avec une version différente sur le dessus et côté gauche). Sachant que la machine Minsky à 2 compteurs est Turing complète (qui a 2 compteurs illimités et 1 état sur un nombre fini), vous pouvez construire une carte équivalente où la position X et Y sur la grille est la valeur actuelle des 2 compteurs et le chemin actuel est létat actuel. Claquer! Vous venez de prouver que Snakes & Les échelles de Turing sont complètes.

Commentaires

• Je ne ‘ t acheter cet argument. Ce nest pas parce que le problème darrêt est indécidable pour les machines de Turing que toute notation qui vous permet de spécifier un programme pour lequel le problème darrêt est indécidable est Turing complète. Seul linverse est évidemment vrai: si la notation est Turing complète, alors il est bien sûr possible décrire des programmes pour lesquels le problème darrêt est indécidable.
• It ‘ est une condition nécessaire. Si vous pouvez décider pour chaque programme sil sarrête, alors la langue nest pas ‘ t Turing terminée.

Une condition nécessaire est une boucle avec un nombre ditérations maximum qui nest pas déterminé avant litération, ou une récursivité où la profondeur de récursivité maximale nest pas déterminée à lavance. Par exemple, les boucles for … in … telles que vous les trouvez dans de nombreux langages plus récents ne sont pas suffisantes pour rendre le langage complet (mais elles auront dautres moyens). Notez que cela ne signifie pas un nombre limité ditérations ou une profondeur de récursivité limitée, mais que les itérations maximales et la profondeur de récursivité doivent être calculées à lavance.

Par exemple, la fonction Ackermann ne peut pas être calculée dans un langage sans ces fonctionnalités. Dun autre côté, de nombreux logiciels très complexes et très utiles peuvent être écrits sans avoir besoin de ces fonctionnalités.

Dun autre côté, avec chaque nombre ditérations et chaque profondeur de récursivité calculés à lavance, pas seulement peut-on décider si un programme sarrêtera ou non, mais il sarrêtera .

Je sais que ce nest pas la réponse formellement correcte, mais une fois que vous retirez le « minimal » de « Turing-complete » et que vous remettez le « pratique » à sa place, vous verrez les caractéristiques les plus importantes qui distinguent un langage de programmation de un langage de balisage sont

• variables
• conditionnelles (if / then …)
• loopage (loop / break, while …)

prochaine com e

• fonctions anonymes et nommées

pour tester ces assertions, commencez avec un langage de balisage, disons HTML. nous pourrions inventer un HTML + avec des variables uniquement, ou des conditions uniquement (MS la fait avec des commentaires conditionnels), ou une sorte de construction de boucle (qui en labsence de conditionnelles finirait probablement par quelque chose comme <repeat n="4">...</repeat>). faire lun de ceux-ci rendra HTML + significativement (?) plus puissant que le HTML simple, mais ce serait toujours plus un balisage quun langage de programmation; à chaque nouvelle fonctionnalité, vous en faites moins un langage déclaratif et plus un langage impératif.

la quête de la minimalité dans la logique et la programmation est certes importante et intéressante, mais si je devais enseigner à n00bies jeunes ou vieux « quest-ce que la programmation » et « comment apprendre à programmer », je commencerais à peine avec toute létendue et la largeur des fondements théoriques de lexhaustivité de Turing.Lessence même de la cuisine et de la programmation consiste à faire des choses, dans le bon ordre, à répéter jusquà ce que vous soyez prêt, comme votre mère la fait. cela me résume.

encore une fois, je nai jamais terminé mon CS.

Commentaires

• Si vous nêtes pas sûr, vous devriez dabord le rechercher. fractran est turing terminé , tout comme brainf * ck . Notez également que html 5 + CSS 3 est Turing complet car il peut implémenter règle 110 .
• oui oui oui je sais. mais tous les exemples donnés sont plus ou moins ésotériques (bien que peut-être intéressants ou surprenants), m La réponse était pragmatique et très probablement pas minimale du tout. Je pense quil est ‘ important de le signaler – cette page était n ° 1 lors de la recherche de lexhaustivité de Turing sur Google, les réponses ici sont à mon humble avis de peu dutilité pour, par exemple, un n00bie qui veut savoir ce qui distingue HTML de PHP ou Python. je veux dire, brainf ck ne sappelle pas brainf ck sans raison.