Qu'est-ce qui rend une langue complète?

Quel est le jeu minimal de fonctionnalités / structures de langage qui rend Turing-complet?

Un tarpit de Turing est une sorte de langage de programmation ésotérique qui s'efforce d'être complet avec Turing 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 à deux et trois symboles, respectivement, basés sur le calcul de combinateur SK (I) .

• OISC ( One Instruction Set Computer ) désigne un type de calcul impératif qui ne nécessite qu'une instruction d'un ou plusieurs arguments, généralement «soustraire et dériver si inférieur ou égal à zéro» ou «inverser soustraire et ignorer si emprunter». Le MMU x86 implémente l'instruction précédente et est donc complet.

En général, pour qu'un langage impératif soit complet de Turing, il 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 certaine forme de stockage (par exemple, variables, bande)

Pour qu'un langage fonctionnel basé sur le lambda-calcul soit TC, il a besoin de:

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

2. La possibilité d'appliquer des fonctions aux arguments (par exemple, réduction)

Il y a bien sûr d'autres manières de considérer le calcul, mais ce sont des modèles courants pour les tentes de Turing. Notez que les ordinateurs réels ne sont pas des machines Turing universelles car ils ne disposent pas d’un stockage illimité. À proprement parler, ce sont des «machines de stockage délimitées». Si vous continuiez à leur ajouter de la mémoire, ils s'approcheraient de manière asymptotique des machines Turing au pouvoir. Cependant, même les machines de stockage délimité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 la complétude de Turing; TC affirme seulement qu'un langage peut calculer la fonction que vous voulez, mais pas qu'il peut vous montrer le résultat. En pratique, chaque langue utile a une manière d’interagir avec le monde.

D'un point de vue plus pratique: si vous pouvez traduire tous les programmes d'une langue complète de Turing dans votre langue, alors (autant que je sache), votre langue doit être Turing-complete. Par conséquent, si vous souhaitez vérifier si une langue que vous avez conçue est Turing-complete, vous pouvez simplement écrire un compilateur Brainf *** dans votre compilateur YourLanguage et prouver / démontrer qu'il peut compiler tous les programmes BF légaux.

Pour clarifier, je veux dire qu’en plus d’un interprète pour YourLanguage, vous écrivez un compilateur (dans n’importe quel langage) capable de compiler n’importe quel programme BF dans YourLanguage (en gardant la même sémantique, bien sûr).

Un système complet ne peut être considéré comme complet que s'il est capable de faire tout ce qu'une machine de Turing universelle peut faire. Étant donné que la machine universelle de Turing est capable de résoudre n'importe quelle fonction calculable dans le temps, les systèmes complets de Turing peuvent également le faire par extension.

Pour vérifier si quelque chose est complet, vérifiez si vous pouvez implémenter une machine de Turing à l'intérieur. En d'autres termes, vérifiez si cela 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 d'autres variables. Ceci peut souvent être simulé dans les langages de programmation avec l'utilisation de structures de données matricielles (ou équivalentes) ou, dans le cas de certains langages tels que le code machine, la possibilité de référencer d'autres variables grâce à l'utilisation de "pointeurs" (ou équivalent).
3. La capacité de simuler une machine à états finis : Bien que cela ne soit pas souvent mentionné, les machines de Turing sont en réalité une variante des machines à états finis souvent utilisées dans le développement de l'IA. Alan Turing a déclaré que l'objectif des États était de simuler les "différents modes de résolution de problèmes" d'une personne.
4. Un état "stop" : bien qu'il soit souvent mentionné un ensemble de règles doit pouvoir se répéter pour être considéré comme complet de Turing, ce n'est pas vraiment un bon critère, car la définition formelle de ce qu'un algorithme est un algorithme d'état doit toujours finalement conclure. S'ils ne peuvent pas en arriver à une conclusion, soit le résultat n'est pas complet, soit le dit algorithme n'est pas une fonction calculable. Turing des systèmes complets qui techniquement ne peuvent pas aboutir à cause de la façon dont ils fonctionnent (comme les consoles de jeu, par exemple) contournent cette limitation en étant capables de "simuler" un état d'arrêt d'une certaine manière. Ne pas confondre avec le "problème stoppant", une fonction indécidable qui le prouve '

Ce sont les véritables exigences minimales pour qu'un système soit considéré comme complet de Turing. Ni plus ni moins. S'il ne peut simuler aucun de ces éléments d'une manière ou d'une autre, ce n'est pas complet. Les méthodes proposées par d'autres personnes ne sont que des moyens, car il existe plusieurs systèmes complets Turing qui ne possèdent pas ces fonctionnalités.

Notez qu’il n’existe aucun moyen connu de créer un véritable système complet Turing. En effet, il n'existe aucun moyen connu de simuler véritablement le caractère illimité de la bande de la machine de Turing dans l'espace physique.

Un langage de programmation est à présent complet si vous pouvez effectuer des calculs avec. Il n'y a pas qu'un seul ensemble de fonctionnalités qui rend une langue complète, donc les réponses disant qu'il faut des boucles ou que vous avez besoin de variables sont fausses, car il existe des langues qui n'ont ni l'une ni l'autre mais sont complètes.

Alan Turing a créé la machine de turing universelle et si vous pouvez traduire n'importe quel programme conçu pour fonctionner sur la machine universelle et le faire fonctionner dans votre langue, il est également complet. Cela fonctionne aussi indirectement pour que vous puissiez dire que la langue X est complète si tous les programmes de traduction complète de la langue 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é de l'espace, le format facile d'entrée / sortie et la facilité d'écriture d'un programme ne sont pas inclus dans l'équation. Cette machine peut donc théoriquement effectuer tous les calculs si les calculs ne sont pas interrompus par une panne de courant ou que la Terre n'est pas engloutie par le soleil.

Habituellement, pour prouver l’exhaustivité, ils ont recours à un interprète pour toute langue prouvée, mais pour que cela fonctionne, vous avez besoin de moyens d’entrée et de sortie, deux choses qui ne sont vraiment pas nécessaires pour qu’une 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é.

Cependant, pour réussir une langue, il faut plus que maîtriser la complétude, et cela est vrai même pour les ridicules. Je ne pense pas que BrainFuck aurait été populaire sans ,et ..

Vous ne pouvez pas dire si ça va boucler infiniment ou s'arrêter.

-------------

Explication: Avec certaines entrées, il est impossible de dire dans tous les cas (en utilisant une autre machine de Turing) si la chose va se mettre en boucle indéfiniment ou s’arrêter éventuellement, sauf en l’exécutant (ce qui vous donne une réponse s’il s’arrête, mais pas si ça boucle!).

Cela signifie que vous devez pouvoir stocker une quantité potentiellement illimitée de données - il doit y avoir un équivalent à la bande infinie, peu importe la complexité! (Sinon, il n'y a qu'un nombre fini d'états et vous pouvez ensuite vérifier si vous avez déjà traversé cet état et éventuellement arrêter). En règle générale, les machines de Turing peuvent augmenter ou réduire la taille de leur état par certains moyens contrôlables.

Étant donné que la première machine universelle Turing de Turing a un problème d’arrêt insoluble, votre propre machine complète Turing doit également avoir un problème d’arrêt insoluble.

Les systèmes complets Turing peuvent émuler n'importe quel autre système complet Turing. Ainsi, si vous pouvez créer un émulateur pour un système complet Turing bien connu dans votre système, cela prouvera que votre système est également complet.

Par exemple, supposons que vous souhaitiez prouver que Snakes & Ladders est complet, dans un tableau comportant un motif de grille répété à l'infini (avec une version différente en haut et à 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 un tableau équivalent où la position X et Y sur la grille est la valeur actuelle des 2 compteurs. et le chemin actuel est l'état actuel. Coup! Vous venez de prouver que Snakes & Ladders sont complets.

Une condition nécessaire est une boucle avec un nombre maximal d’itérations qui n’est pas déterminé avant l’itération, ou une récursivité dans laquelle la profondeur de récursivité maximale n’est pas déterminée avant. Par exemple, les boucles ... in ... telles que vous les retrouvez dans de nombreuses langues plus récentes ne suffisent pas pour compléter la procédure (mais elles auront d'autres moyens). Notez que cela ne signifie pas un nombre limité d'ité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 à l'avance.

Par exemple, la fonction Ackermann ne peut pas être calculée dans un langage sans ces fonctionnalités. Par ailleurs, de nombreux logiciels très complexes et très utiles peuvent être écrits sans nécessiter ces fonctionnalités.

D'autre part, avec chaque nombre d'itérations et chaque profondeur de récursivité calculée, il est non seulement possible de décider si un programme sera interrompu ou non, mais il sera également interrompu.

Je sais que ce n'est pas la bonne réponse formelle, mais une fois que vous prenez le "minimum" de "Turing-complete" et que vous mettez "pratique" à sa place, vous verrez les caractéristiques les plus importantes qui distinguent un langage de programmation d'un langage de balisage sont

• les variables
• conditionnels (si / alors ...)
• loopage (loop / break, while ...)

ensuite venir

• 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 l’a fait avec des commentaires conditionnels), ou une sorte de construction de boucle (qui, en l’absence de conditions, finirait probablement par ressembler à quelque chose du genre <repeat n='4'>...</repeat>). faire l'une ou l'autre de ces choses rendra HTML + (?) significativement plus puissant que le HTML simple, mais ce serait quand même plus un balisage qu'un langage de programmation; à chaque nouvelle fonctionnalité, vous en faites moins un langage déclaratif et plus impératif.

la quête de la minimalité en logique et en programmation est certes importante et intéressante, mais si je devais enseigner à n00bies «ce qu’est la programmation» et «comment apprendre à programmer», je commencerais à peine avec la largeur et la largeur voulues des fondements théoriques de la complétude de Turing. toute l'essence de la cuisine et de la programmation consiste à faire des choses dans le bon ordre, à répéter jusqu'à ce que tout soit prêt, comme l'a fait votre mère. Ceci résume bien pour moi.

là encore, je n'ai jamais fini mon CS.