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

79

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

Chat curieux
la source
21
Ne vaudra-t-il pas mieux y aller sur Google? en.wikipedia.org/wiki/Turing_completeness
aml90
2
Bonjour chat curieux, bienvenue aux programmeurs! Les appels de listes ne sont pas dans le sujet ici: j'ai supprimé cette partie de votre question. Cela dit, cette quête est extrêmement vaste: y at-il un problème spécifique sur lequel vous travaillez et qui vous fait penser à la complétude de Turing?
3
@ amalantony: juste comme une note de bas de page .
Bobby
Pour une perspective informatique, voir ici .
Raphael

Réponses:

73

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.

Jon Purdy
la source
Pour les langages impératifs, les variables simples suffisent-elles? J'avais l'impression qu'une sorte de collection (par exemple des tableaux ou des listes chaînées) serait nécessaire.
luiscubal
1
@luiscubal vous devez pouvoir spécifier une quantité arbitraire de données. Avec des variables simples, vous pouvez représenter la quantité de données que possèdent les variables elles-mêmes. Et si vous avez besoin de représenter N + 1 données différentes. On pourrait dire qu'avec des tours comme Fractran, on peut le faire même avec des variables simples ... mais ce n'est pas tout à fait ce que vous demandez.
N'est-il pas nécessaire que la langue prenne en charge les boucles ENDLESS ?
sergiol
Re, "chaque langue utile a une façon d'interagir avec le monde." Algol 60 n'avait aucune manière définie d'interagir 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 pouvaient être complètement différentes dans différentes implémentations. Mais, par la présente, je me retire de toute discussion sur le fait de savoir si Algol 60 était "utile".
Salomon Slow
15

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).

Anton Golov
la source
11
Oui, ce serait certainement la façon la plus pratique d’aborder la question. </sarcasm>
Robert Harvey
13
@RobertHarvey a un point, mais l'idée générale est tout à fait vitale. Il a été prouvé que Brainfuck est très complet et très simple en ce qui concerne les langages de programmation. Pour les langages de programmation non ésotériques, implémenter un interpréteur brainfuck peut être beaucoup plus facile et rapide que de donner une preuve rigoureuse de nulle part (je peux implémenter BF dans quelques lignes de Python, mais je ne sais pas par où commencer avec un formel. preuve que Python est complète); et des dizaines de langues ésotériques inspirées de brainfuck sont connues pour être complètes parce qu'elles savent comment elles correspondent à un brainfuck.
7
@ RobertHarvey: Pourquoi pas? Sûrement quelqu'un qui conçoit sa propre langue serait capable de lui écrire un compilateur BF (si c'était impératif, et de trouver une autre langue appropriée autrement).
Anton Golov
5
@delnan: Cependant, vous devrez prouver que votre interprète BF implémente correctement la spécification BF, mais vous devrez également 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.
Jörg W Mittag le
2
@ DarekNędza, ce n'est qu'une conséquence naturelle de la définition de la complétude de Turing; toute extension d'une langue de Turing Complete sera toujours Turing Complete.
Anton Golov
8

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.

utilisateur3067516
la source
4

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 ..

Sylwester
la source
2
"Un langage de programmation est à présent complet si vous pouvez effectuer des calculs avec." C’est la thèse de Church-Turing, pas ce qui rend une langue complète.
Rhymoid
@ Rhymoid Vous voulez donc dire que rien n'est complet à moins de pouvoir faire appel à un interprète? C'est à dire. Le calcul lambda n'est-il pas complet, même si c'est équivalent?
Sylwester
1
Je cherche toujours une définition faisant autorité des termes équivalent de Turing et Turing-complet (et Turing-puissant). J'ai déjà vu trop de cas, allant de personnes sur des babillards électroniques à des chercheurs dans leur propre journal, qui interprètent ces termes différemment.
Rhymoid
Quoi qu'il en soit, j’interprète Turing-complete comme étant une simulation équivalente à une machine de Turing universelle (UTM; elle est capable de simuler n’importe quelle machine de Turing - donc "universelle"). Dans son article de 1936, dans lequel il présente ses machines, Turing définit la notion de UTM et donne une esquisse d'une preuve que les UTM sont des simulations équivalentes au lambda calcul de Church. Ce faisant, il a prouvé qu'ils disposaient du même pouvoir de calcul. La thèse de Church-Turing affirme, en termes simples, que "c'est toute la puissance de calcul que vous obtiendrez jamais".
Rhymoid
Il a deux définitions formelles pour la page de complétude Turing de Wikipedia . L'une nécessite des E / S, l'autre pas. Celui qui ne dit pas qu'une machine est complète si elle peut calculer chaque fonction calculable par Turing. Cela ramène le calcul lambda à être complet, car vous pouvez facilement créer un programme de calcul de lambda calculant le même calcul que tout programme de machine.
Sylwester
4

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.

Hubert Lamontagne
la source
1
Je n'achète pas cet argument. Ce n'est pas parce que le problème d'arrêt est indécidable pour les machines Turing que chaque notation qui vous permet de spécifier un programme pour lequel le problème d'arrêt est indécidable est Turing complete. Seule l'inverse est évidemment vrai: si la notation est complète, il est bien sûr possible d'écrire des programmes pour lesquels le problème bloquant est indécidable.
5gon12eder
C'est une condition nécessaire. Si vous pouvez décider, pour chaque programme, s'il y a interruption ou non, la langue n'est pas complète.
gnasher729
4

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.

gnasher729
la source
-1

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.

couler
la source
2
Si vous n'êtes pas sûr, vous devriez le rechercher en premier. fractran est complètement terminé , de même que brainf * ck . Notez également que html 5 + CSS 3 est complet pour Turing car il peut implémenter la règle 110 .
1
oui oui je sais. mais tous les exemples cités sont plus ou moins ésotériques (même s’ils sont peut-être intéressants ou surprenants), ma réponse était pragmatique et très probablement pas du tout minime. Je pense qu'il est important de le souligner - cette page était n ° 1 lors de la recherche de la complétude de Turing sur Google, les réponses à cette question ne sont d'aucune utilité pour un n00bie qui veut savoir ce qui distingue HTML de PHP ou Python. Je veux dire, brainf ck ne s'appelle pas brainf ck sans raison.
flux