Existe-t-il des critères minimums pour qu'un langage de programmation soit complet?

Existe-t-il un ensemble de constructions de langage de programmation dans un langage de programmation afin que celui-ci soit considéré comme Turing Complete?

D'après ce que je peux dire sur wikipedia , la langue doit prendre en charge la récursion ou, apparemment, doit pouvoir fonctionner sans interruption. Est-ce tout ce qu'il y a à faire?

J'ai toujours pensé que les fonctions rc-récursives le clouaient . Voici ce qui définit l’ensemble des fonctions calculables; c'est le plus petit ensemble de fonctions contenant resp. fermé contre:$\mu$

1. La fonction constante$0$
2. La fonction successeur
3. Sélection des paramètres
4. Composition fonctionnelle
5. Récursion primitive
6. L' opérateur (cherchez le plus petit tel que ...)$\mu$$x$

Vérifiez le lien ci-dessus pour plus de détails; vous voyez que cela fait un langage de programmation très compact. Il est également horrible de programmer - pas de repas gratuit. Si vous laissez tomber l'un de ceux-ci, vous perdrez toute votre puissance. Il s'agit donc d'un ensemble minimal d'axiomes.

Vous pouvez les traduire littéralement en éléments syntaxiques de base pour les programmes WHILE , à savoir:

1. La constante 0
2. Incrémentation _ + 1
3. Accès variable x
4. Concaténation programme / relevé _; _
5. Boucles de compte à rebours for ( x to 0 ) do _ end
6. Boucles While while ( x != 0 ) do _ end

Existe-t-il un ensemble de calculs qui doivent pouvoir être exécutés dans un langage de programmation pour que celui-ci soit considéré comme étant complet?

Oui, pour être considéré comme complet, un langage de programmation doit pouvoir exécuter tout calcul pouvant être effectué par une machine de Turing. Donc, au minimum, on pourrait dire que vous devez être capable de mettre en œuvre une machine universelle de Turing - ou un interprète pour tout autre langage complet de Turing - en elle.

D'après ce que je peux dire sur wikipedia, la langue doit prendre en charge la récursion ou, apparemment, doit pouvoir fonctionner sans interruption. Est-ce tout ce qu'il y a à faire?

Par exemple, une langue où la seule opération autorisée est la récursivité (c’est-à-dire que la seule fonction possible que vous pouvez écrire est f(x) = f(x)Turing n'est pas complète, car vous ne pouvez y écrire que des programmes qui ne se terminent jamais. Comme je l’ai dit plus tôt, une langue complète de Turing doit pouvoir mettre en oeuvre tous les calculs pouvant être effectués par une machine de Turing, ce qui est clairement insuffisant.

En outre, une langue ne doit pas nécessairement prendre en charge la récursivité de la manière dont vous envisagez. Juste une manière illimitée d’exprimer des boucles. Cela pourrait être une récursion, mais cela pourrait aussi être une boucle while ou goto. Un langage qui n’a pas du tout de fonctions peut toujours être complet. Et encore une fois, les boucles ou les fonctions récursives ne sont pas une condition suffisante. Vous avez toujours besoin d'un moyen d'exécuter un code différent en fonction d'une condition et d'un moyen de calculer de nouvelles valeurs à partir d'anciennes (sinon toutes les boucles / récursions seraient infinies ou ne seraient pas exécutées du tout).

Pour ce qui est de savoir s’il existe un ensemble minimal d’opérations nécessaires et suffisantes, de sorte que tout langage prenant en charge ces opérations soit complet de Turing et que tout langage qui ne le soit pas ne le soit pas: non, il n’en existe pas (à moins que vous ne définissiez le terme "opération" de manière aussi vague) , cela devient sans signification):

Par exemple, comme je l'ai déjà dit, il existe des langages complets de Turing qui ne prennent pas en charge les fonctions récursives (ou aucune fonction du tout). Celles-ci peuvent toujours être complètes si elles ont une gotoinstruction ou une whileboucle (et un moyen de stocker des quantités arbitraires de données). Cependant, un langage avec des fonctions récursives n'a besoin whileni gotod'être complet de Turing. Donc goto, ne serait pas dans l'ensemble des opérations suffisantes nécessaires, mais il y a des langues qui ne sont plus Turing complète si vous supprimez goto. Ainsi, il n'y a pas un tel ensemble.

Il existe différentes instructions uniques qui conduisent à des langues complètes de Turing. L'exemple typique est "soustraire et créer une branche si zéro". Celles-ci sont bien connues dans le contexte de la programmation en langage assembleur. Voir l'article Wikipedia pour plus de détails.

Cela conduit à une caractérisation: un langage est complet si seulement et s'il est capable de simuler les opérations d'extraction et de stockage des entiers en mémoire et d'effectuer l'opération "soustraction et branche si zéro".

Ce n'est pas une réponse générale à votre question, mais selon le théorème de programmation structurée , tout ce dont vous avez besoin est la capacité de faire une sélection (par exemple, ifen C / C ++) et une répétition (par exemple, whileen C / C ++). Edit: comme l'a souligné Dave Clarke dans les commentaires, le théorème de la programmation structurée requiert également une séquence. Au départ, je ne l'avais pas énuméré, car je pensais que le lecteur comprendrait que des blocs d'instructions de base, tels que ceux mentionnés plus tard pour lire et écrire dans le magasin de mémoire, étaient également nécessaires). Il vaut évidemment mieux être explicite; vous devez être capable de faire ces choses aussi.

Étant donné que les deux peuvent être implémentés en utilisant une instruction de saut conditionnel (par exemple, JNZen x86), cela suffit également pour l'équivalence de Turing.

Notez que d'autres éléments sont nécessaires, à savoir la possibilité d'écrire un nombre illimité de symboles (par exemple, des bits ... 0 ou 1) dans une sorte de mémoire de stockage externe. En ce sens, les ordinateurs réels ne sont pas équivalents à Turing, car aucun d’entre eux n’a une capacité de stockage infinie. Le modèle de Turing est toujours utile, car la quantité de mémoire est généralement énorme, et même si tout problème qu'un ordinateur réel peut résoudre peut être résolu par un automate fini déterministe, l'utilisation de ce modèle de calcul n'est pas particulièrement utile (car nombre d’États serait ridiculement énorme).

Notez que ce n'est pas nécessairement en contradiction avec la réponse de sepp2k; c'est en quelque sorte une façon différente de penser à la même question.

MODIFIER:

Notez également que vous n’avez pas vraiment besoin des deux ifet whileen C / C ++. Vous pouvez simuler en ifutilisant whilecomme suit:

bool C;
// some code that sets C
if(C) { /* some other code /* }
// rest of the program

Le code suivant est toujours équivalent:

bool C;
// some code that sets C
bool C2 = C;
while(C2) { /* some other code /* C2 = false; }
// rest of the program

Eh bien ... la construction devrait fonctionner et être possible si vous êtes prudent, c'est. Notez également que si vous avez des fonctions récursives, vous aurez éventuellement besoin de la sélection; comme les fonctions récursives sans sélection ne peuvent pas réellement implémenter les cas de base, toute fonction récursive entraînerait une récursion infinie.

MODIFIER:

De plus, en ce qui concerne votre question sur le point de savoir si la capacité à écrire un programme qui ne s’arrête pas est suffisante pour l’équivalence de Turing, la réponse est non. c'est nécessaire, mais pas suffisant. Nous pouvons résoudre le problème d’arrêt des programmes écrits dans une langue qui ne peut pas exprimer des programmes qui ne s’arrêtent pas; la réponse est "le programme s'arrête" pour toutes les instances. Cependant, nous pouvons définir un langage où la seule instruction entraîne la machine à entrer dans une boucle infinie ... un tel langage n'est pas équivalent à Turing.

Les combinateurs et où, et sont suffisants pour exprimer tout terme lambda (fermé), donc toute fonction calculable. Voir cette page wikipedia pour plus de détails.K ( S x y z ) = ( x z ( y z ) ) ( K x y ) = $\mathbf{S}$$\mathbf{K}$$(\mathbf{S}\ x\ y\ z) = (x\ z\ (y\ z))$$(\mathbf{K}\ x\ y) = x$

En fait, le terme lambda est une base suffisante pour exprimer tous les termes lambda. Voir plus tard dans la même page wikipedia .$\mathbf{X}=\lambda x.((x\ \mathbf{S})\ \mathbf{K})$

Les constructions de langage sont interchangeables

Il n'y a pas de critères minimaux concernant les constructions qui doivent être fournies nativement par un langage de programmation. Si elle fournit des constructions étranges qui peuvent en quelque sorte être alambiquées pour exprimer un système complet de Turing, alors apparemment ces constructions sont "tout aussi appropriées" que toutes les autres.

Pour le prouver, un langage qui fournit uniquement une opération "soustraction et branche si zéro" est Turing complet; il existe des langages complets Turing qui ne fournissent pas de construction séparée "soustraction et branche si zéro", alors qu'il n'y a pas de construction ou un ensemble de constructions qui est obligatoire.

Les effets de toute construction de langage TP-complète peuvent être imités par les constructions de tout autre langage TP-complet.