Quelles sont les directives pratiques pour évaluer la «complétude de Turing» d'une langue?

Question

J'ai lu "ce-que-la-turing-complet" et la page wikipedia, mais je suis moins intéressé par une preuve formelle que dans les implications pratiques de Turing.

Ce que je suis réellement en train de décider si le jouet de la langue, j'ai juste conçu peut être utilisé comme un usage général de la langue. Je sais que je peux le prouver, c'est si je peux écrire une machine de Turing avec elle. Mais je ne veux pas passer par cet exercice jusqu'à ce que je suis assez certain de la réussite.

Est-il un ensemble minimal de fonctionnalités sans qui Turing l'Exhaustivité est impossible? Est-il un ensemble de fonctionnalités qui garantit pratiquement l'intégralité?

(Ma conjecture est que les branchements conditionnels et accessible en lecture/écriture de la mémoire store obtenez-moi la plupart du chemin)

---

EDIT:

Je pense que je suis parti sur une tangente en disant "Turing Complet". Je suis en train d'essayer de deviner avec une certitude raisonnable qu'une nouvelle langue inventée avec un certain ensemble de caractéristiques (ou alternativement, une machine virtuelle avec un certain jeu d'instructions) serait en mesure de calculer quelque chose d'intéressant à l'informatique. Je sais prouver que vous pouvez construire une machine de Turing avec elle est un moyen, mais pas uniquement.

Ce que j'espérais était un ensemble de lignes directrices comme: "si ça peut faire X,Y et Z, il peut sans doute faire quelque chose".

Answer 1

Vous avez besoin d'une certaine forme d'allocation dynamique de construire (malloc ou cons va faire) et les fonctions récursives ou d'une autre façon d'écrire une boucle infinie. Si vous avez ceux-ci et peuvent faire quoi que ce soit intéressant, vous êtes presque certainement Turing-complet.

Le lambda calcul est équivalent à la puissance d'une machine de Turing, et si vous mettez en œuvre lambda calcul, il est en fait assez amusant écrit lambda calcul des programmes. Manière plus de plaisir que d'écrire un programme pour une machine de Turing!

La seule conséquence pratique de Turing-complétude je suis conscient, c'est que vous pouvez écrire des programmes qui ne se termine. J'ai utilisé un couple de but spécial les langues qui garantissent la résiliation et ne sont donc pas Turing-complet. Parfois, il est utile de donner plus de force expressive en échange de la garantie de la résiliation.

Answer 2

'Turing Exhaustivité, la description du bien de pouvoir parler de tout arbitraire algorithmique de calcul, qui a été le point de Turing Machine en premier lieu. Une langue ou d'une logique de système peut être décrit comme "Turing Complet", si elle a cette propriété. À partir d'un point de vue pratique, tous les langages de programmation d'usage - et un nombre surprenant de ceux - pouvez le faire de manière lâche définition (voir ci-dessous).

Cependant, une définition stricte de Turing à l'Exhaustivité implique l'infinie capacité de stockage, ce qui n'est évidemment pas physiquement possible. Compte tenu de cela, pas de machine physique peut éventuellement être Turing, mais cette contrainte est généralement détendue (au moins de façon informelle) lors de l'attribution de Turing à l'Exhaustivité d'un langage de programmation. Un banal test de Turing de l'Exhaustivité pour une langue est de savoir si le langage peut être utilisé pour mettre en œuvre un simulateur de Machine de Turing.

Un exemple d'un vaste système qui n'est pas Turing est de l'Algèbre Relationnelle, la base théorique derrière SQL comme décrit dans Codd papier d' Un modèle relationnel pour les grandes banques de données partagée. L'Algèbre relationnelle a la propriété de Godel l'Exhaustivité, ce qui signifie qu'il peut exprimer tout calcul, qui peut être défini en termes de premier ordre prédicat de calcul (c'est à dire ordinaire des expressions logiques). Cependant, il n'est pas Turing-Complet, car il ne peut exprimer l'arbitraire d'un calcul algorithmique.

Notez que la plupart, si pas tous des dialectes SQL étendre le pur modèle relationnel avec les constructions dans la mesure où ils sont Turing par la définition s'applique normalement à des langages de programmation. Toutefois, un particulier d'une requête SQL en gros, ne l'est pas.

Certains plus flagrants exemples de Turing spécifiques au domaine des langues TeX et sendmail.cf,. Dans ce dernier cas, il est en fait un célèbre-ish exemple de quelqu'un à l'aide de sendmail.cf à mettre en œuvre une Machine de Turing universelle simulateur.

Answer 3

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

Answer 4

Des exemples de langues qui ne sont pas Turing-complet ont souvent délimitée boucles, comme:

for i=1 to N {...}

mais le manque illimitée des boucles de contrôle plus général de l'état, comme:

while 

Si possible toutes les boucles sont bornées, votre programme est garanti pour mettre fin. Et, bien qu'étant un inconditionnel de la résiliation de la garantie est potentiellement utile, c'est aussi une indication que la langue n'est pas Turing-complet.

Notez également que le clouer tous les possible les constructions de bouclage peut être difficile; par exemple, je suis sûr que les modèles C++ n'étaient pas destinés à être Turing-complet...

Answer 5

Je ne sais pas s'il existe un "ensemble minimal de fonctionnalités", mais pour prouver qu'un langage est Turing complet, il suffit de prouver qu'il peut émuler un autre système complet Turing (pas nécessairement une machine Turing), tant que le un autre système est connu comme étant Turing complet. http://en.wikipedia.org/wiki/Turing_complete#Examples a une liste complète de systèmes complets de Turing. Certains d'entre eux sont plus simples que les machines Turing.