Quelles sont les instructions pratiques pour évaluer le & Completeness & # 8220; Turing d'une langue?

Question

J'ai lu "what-is-turing-complete" et le wikipedia page, mais je suis moins intéressé par une preuve formelle que par les implications pratiques d'être Turing Complete.

Ce que j'essaie en fait de décider, c'est si le langage des jouets que je viens de concevoir pourrait être utilisé comme langage général. Je sais que je peux le prouver si je peux écrire une machine de Turing avec elle. Mais je ne veux pas passer par cet exercice avant d’être assez certain du succès.

Existe-t-il un minimum de fonctionnalités sans lesquelles Turing Completeness est impossible? Existe-t-il un ensemble de fonctionnalités garantissant virtuellement l’exhaustivité?

(J'imagine que le branchement conditionnel et un magasin de mémoire lisible / inscriptible me mèneront presque jusqu'au bout)

EDIT:

Je pense que je suis parti sur une tangente en disant "Turing Complete". J'essaie de deviner avec une assurance raisonnable qu'un langage nouvellement inventé avec un certain ensemble de fonctionnalités (ou, en variante, un ordinateur virtuel avec un certain ensemble d'instructions) serait capable de calculer tout ce qui mérite d'être calculé. Je sais que prouver que vous pouvez construire une machine de Turing avec elle est un moyen, mais pas le seul.

Ce que j'espérais, c'était un ensemble de règles du type: "si vous pouvez faire X, Y et Z, vous pouvez probablement faire n'importe quoi".

Answer 1

Vous avez besoin d’une certaine forme de construction d’allocation dynamique ( malloc ou nouveau ou contre ), et de fonctions récursives écrire une boucle infinie. Si vous en avez et pouvez faire quelque chose d’intéressant, vous êtes presque certainement Turing-complete.

Le calcul lambda équivaut en puissance à une machine de Turing, et si vous implémentez le calcul lambda, il est plutôt amusant d’écrire des programmes lambda. Manière plus amusante qu'un programme d'écriture pour une machine de Turing!

À ma connaissance, la seule implication pratique de la complétude de Turing est que vous pouvez écrire des programmes qui ne se terminent pas. J'ai utilisé quelques langages spéciaux qui garantissent la résiliation et ne sont donc pas pas Turing-complete. Parfois, il est utile de renoncer au pouvoir expressif supplémentaire en échange d’une résiliation garantie.

Answer 2

'Intégralité de Turing' décrit la propriété de pouvoir exprimer n'importe quelle expression arbitraire calcul algorithmique , qui était le point de La machine de Turing en premier lieu. Une langue ou un système logique peut être qualifié de «Turing Complete» s'il possède cette propriété. D'un point de vue pratique, tous les langages de programmation à usage général - et un nombre étonnamment grand de langages à usage spécifique - peuvent le faire avec une définition suffisamment vague (voir ci-dessous).

Cependant, une définition stricte de Turing Completeness implique une capacité de stockage infinie, ce qui, bien sûr, n’est pas physiquement possible. Compte tenu de cela, aucune machine physique ne peut être Turing Complete, mais cette contrainte est généralement relâchée (au moins de manière informelle) lors de l'attribution de Turing Full à un langage de programmation. Un test trivial de la complétude de Turing pour un langage consiste à déterminer si celui-ci peut être utilisé pour implémenter un simulateur de Turing Machine.

Un exemple de système répandu qui n'est pas Turing Complete est l'algèbre relationnelle, la base théorique de SQL décrite dans l'article de Codd Un modèle relationnel pour les grandes banques de données partagées. Algèbre relationnelle a la propriété de Complétude de Godel , ce qui signifie qu'il peut exprimer tout calcul pouvant être défini en termes de calcul du prédicat de premier ordre (c'est-à-dire des expressions logiques ordinaires). Cependant, ce n'est pas Turing-Complete car il ne peut pas exprimer un calcul algorithmique arbitraire.

Notez que la plupart des dialectes SQL pratiques, sinon tous, étendent le modèle relationnel pur avec des constructions procédurales dans la mesure où ils sont Turing Complete au sens de la définition, tels qu'ils sont normalement appliqués aux langages de programmation. Toutefois, les requêtes SQL individuelles ne le sont généralement pas.

Quelques exemples plus flagrants de langages propres à un domaine Turing Complete sont TeX et sendmail.cf, . Dans ce dernier cas, il existe en fait un exemple célèbre de quelqu'un utilisant sendmail.cf pour implémenter un simulateur universel de Turing Machine.

Answer 3

Si vous pouvez écrire un interprète Brainf $ & amp # # dans votre langue, c'est Turing -Achevée. LOLCODE s'est avéré être Turing-complet exactement de cette façon.

Answer 4

Les exemples de langues qui ne sont pas complètes avec Turing ont souvent des boucles liées , telles que:

for i=1 to N {...}

mais il manque des boucles sans bornes qui vérifient une condition plus générale, telle que:

while bool_expr {...}

Si toutes les constructions en boucle possibles sont liées, il est garanti que votre programme se terminera. Et, bien qu'une garantie de terminaison inconditionnelle soit potentiellement utile, elle indique également que le langage n'est pas Turing-complete.

Notez également que clouer toutes les constructions de boucle possibles peut être difficile; Par exemple, je suis à peu près sûr que les modèles C ++ ne sont pas conçus pour être complets de Turing ...

Answer 5

Je ne suis pas sûr qu'il existe un "ensemble minimal de fonctionnalités", mais pour prouver qu'une langue est complète en Turing, il vous suffit de prouver qu'il peut imiter un autre système complet de Turing (pas nécessairement une machine de Turing), tant que l'autre système est connu pour être complet de Turing. http://fr.wikipedia.org/wiki/Turing_complete#Examples contient une liste complète. des systèmes complets de Turing. Certaines sont plus simples que les machines de Turing.

Answer 6

J'aimerais ajouter une mise en garde à ce que Norman Ramsey a dit: une machine de Turing a une mémoire infinie et, par conséquent, les langages de programmation considérés comme complets de Turing ne le sont que si la mémoire est également infinie.

Answer 7

Brainfuck est bien complet et n'a que des structures de boucles et des incrémentations / décrémentations en mémoire, donc c'est suffisant.

D'autre part, il n'y a aucun moyen de modifier une valeur dans le calcul lambda, mais celle-ci est complète, il est donc clairement possible de le faire sans mémoire mutable.

Il est fort probable que votre programme n’ait rien à voir avec le calcul lambda, donc pour une réponse pratique, le minimum doit être

.

1. Un moyen d'écrire dans une variable
2. Un moyen de lire une variable
3. Une forme de goto conditionnel (instruction if, boucle while, etc.)

Answer 8

Je ne me souviens pas avoir vu quoi que ce soit comme fonctionnalités minimales pour Turing Completeness. Toutefois, si votre langue prend en charge les boucles et les branches conditionnelles, les chances qu’elle soit complète sont bonnes. Cependant, le seul moyen de le prouver consiste toujours à simuler une machine de Turing ou un autre langage Turing Complete.

Answer 9

Si vous pouvez implémenter une machine de Turing (dans la mesure où elles peuvent être implémentées, car ce sont des constructions mathématiques avec une mémoire illimitée [la taille de la bande est infinie]), alors vous pouvez être sûr que Turing est terminée.

Quelques indications:

• Vous pouvez vérifier la mémoire, la manipuler en fonction de la valeur actuelle et l'utiliser pour contrôler le déroulement du programme.
• Cette mémoire peut être allouée à de la mémoire, à des chaînes que vous pouvez ajouter à une pile, à une pile sur laquelle vous pouvez allouer de la mémoire par récursivité, etc.
• Le déroulement du programme peut se faire par itération ou par récursivité basée sur la sélection.

Answer 10

Toute langue capable de ne pas prendre fin est à peu près Turing Complete. Vous pouvez rendre une langue non terminable capable en lui donnant des structures en boucle non liées (comme des boucles While ou un Goto qui peut se rejoindre à nouveau), ou en lui donnant une récursion générale (en laissant une fonction s’appeler elle-même sans restriction.)

Une fois que vous êtes terminé , vous pouvez interpréter d'autres langages de Turing Complete, y compris le vôtre.

La vraie question est "à quoi sert-il?" Si votre langue doit être utilisée dans un domaine spécifique pour résoudre des problèmes spécifiques, il peut être préférable de trouver un moyen de formuler les solutions dans une langue qui n'est pas Turing Complete et qui garantit ainsi une réponse.

Vous pouvez toujours ajouter la complétude de Turing en écrivant "Faites ceci, cela ou autre chose; mais faites-le avec le résultat fourni par X " dans toute autre langue Turing Complete, où X est fourni par une langue complète non-Turing.

Bien sûr, si vous souhaitez utiliser une seule langue, il vaut probablement mieux utiliser Turing Complete ...

Answer 11

Vous pouvez essayer d'émuler un OISC (un seul ordinateur contenant des instructions). Si vous pouvez y imiter une des instructions, puisque ces instructions simples peuvent être utilisées pour composer une machine Turing Complete, vous avez prouvé que votre langue devait également être Turing Complete.

Answer 12

  

Existe-t-il un minimum de fonctionnalités sans lesquelles Turing Completeness est impossible?   Existe-t-il un ensemble de fonctionnalités garantissant virtuellement l’exhaustivité?

Oui, vous devez conditionner le flux de contrôle aux données: ce qui est souvent exprimé par si . Par exemple, une calculatrice de poche + - * / n'est pas Turing-complete, car il n'y a aucun moyen d'exprimer des conditions.

Vous devez également pouvoir exprimer un retour vers un point précédent du programme, au-dessus duquel vous pouvez implémenter une boucle. Par exemple, BPF, qui interdit les sauts en arrière pour garantir la fin du programme, n’est pas non plus complet.

Vous avez besoin d'un espace de stockage lisible et inscriptible, de taille arbitraire. Par exemple, un langage qui ne comporte que deux variables 32 bits a une capacité de calcul limitée. Vous avez de nombreuses options pour la structure du stockage: mémoire adressée par des pointeurs, des tableaux, des piles, des cellules contre, des structures de données pures, etc.

De plus, vous pouvez construire tous les autres langages de programmation: ce n'est peut-être pas facile ni rapide, mais c'est suffisant.

Answer 13

  

... que dans les implications pratiques d'être Turing Complete.

Je doute qu’il y ait des implications pratiques à la complétude de Turing.

Si vous regardez quelques exemples de machines complètes de Turing, par exemple, la machine de Turing , vous verrez qu’ils sont si loin d’être utiles pour les calculs réels que le concept ne doit présenter qu’un intérêt théorique.