Y at-il des critères minimums pour un langage de programmation est complète Turing?

cs.stackexchange https://cs.stackexchange.com/questions/991

Question

existe-t-il un ensemble de la programmation des constructions de langage dans un langage de programmation pour qu'elle soit considérée comme complète Turing?

D'après ce que je peux dire de wikipedia , les besoins linguistiques à l'appui récursivité, ou, apparemment, doit pouvoir courir sans arrêt. Est-ce tout ce qu'il ya à faire?

Était-ce utile?

La solution

J'ai toujours bien que $ \ mu $ -recursive fonctions cloua. Voici ce qui définit l'ensemble des fonctions calculables; il est le plus petit ensemble de fonctions contenant resp. fermé contre:

  1. La constante $ 0 Fonction de $
  2. La fonction successeur
  3. Sélection des paramètres
  4. composition Fonction
  5. récursion primitive
  6. Les $ \ mu -operator $ (look pour le plus petit $ x $ tel que ...)

Vérifier lien ci-dessus pour plus de détails; vous voyez que cela fait pour un langage de programmation très compacte. Il est aussi horrible programme - pas de repas gratuit. Si vous laissez tomber l'un de ceux, vous perdrez la pleine puissance, il est donc un ensemble minimal d'axiomes.

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

  1. La 0 constante
  2. Incrémentation _ + 1
  3. x d'accès variable
  4. concaténation programme / déclaration _; _
  5. boucles Countdown for ( x to 0 ) do _ end
  6. Alors que les boucles while ( x != 0 ) do _ end

Autres conseils

  

existe-t-il un ensemble de calculs qui ont besoin d'être dans performable un langage de programmation pour qu'elle soit considérée comme complète Turing?

Oui, pour être considéré comme une langue complète Turing de programmation doit être en mesure d'effectuer tout calcul qui peut être effectué par une machine de Turing. Donc, comme une exigence minimale pourrait dire, vous devez être en mesure de mettre en œuvre une machine de Turing universelle - ou un interprète pour toute autre langue complète Turing -. Dans ce

  

D'après ce que je peux dire de wikipedia, les besoins linguistiques à récursion de soutien, ou, apparemment, doit être capable de fonctionner sans arrêt. Est-ce tout ce qu'il ya à faire?

Non

. Par exemple, une langue où l'opération n'autorisée est récursion (la seule fonction possible, vous pouvez écrire est f(x) = f(x), n'est pas Turing complet parce que tout ce que vous pouvez écrire dans ce sont des programmes qui ne se terminerait jamais. Comme je l'ai dit plus tôt, un Turing besoins linguistiques complets pour être en mesure de mettre en œuvre tout calcul qui peut être effectué par une machine de Turing. Il est donc clair que ne pas suffire.

Aussi une langue ne doit pas soutenir récursion dans la façon dont vous pensez. Juste une façon d'exprimer librement des boucles. Cela pourrait être récursion, mais il pourrait aussi être une boucle while ou goto. Une langue qui ne fonctionne pas du tout peut encore être complet Turing. Et des boucles à nouveau ou fonctions récursives ne sont pas une condition suffisante. Vous avez encore besoin d'une manière d'exécuter du code différent selon une condition et un moyen de calculer de nouvelles valeurs de vieux (sinon toutes les boucles / récursivité serait soit infinie ou non courir du tout).

Quant à savoir s'il y a un ensemble minimal de des opérations nécessaires et suffisantes, de sorte que toute langue qui soutient ces opérations est complète et toute Turing langue qui ne l'est pas: Non, il n'y a pas (sauf si vous définissez « opération "si vaguement, qu'il devient vide de sens):

Par exemple, comme je l'ai déjà dit, il y a des langues complètes Turing ne prennent pas en charge les fonctions récursives (ou toutes les fonctions du tout). Ceux-ci peuvent encore être Türing complète si elles ont une déclaration de goto ou d'une boucle de while (et un moyen de stocker des quantités de données arbitraires). Cependant, une langue avec des fonctions récursives ne nécessite ni while ni goto être complète Turing. Alors goto ne serait pas dans l'ensemble des opérations nécessaires et suffisantes, mais il y a des langues que si vous supprimez goto ne sont plus complets de Turing. Ainsi, il n'y a pas ensemble.

Il existe différentes instructions simples qui conduisent à des langues complètes Turing. L'exemple typique est « soustraient et branche si zéro ». Ceux-ci sont bien connus dans le contexte de la programmation en langage assembleur. Voir l'article de Wikipedia pour plus de détails.

Cela conduit à une caractérisation: une langue est Türing complet si et seulement si elle est en mesure de simuler les opérations d'extraction et de stockage des entiers en mémoire et exécuter la « branche et soustrayez si zéro » opération sur eux.

Ce n'est pas une réponse générale à votre question, mais par le théorème , tout ce qui est nécessaire est la possibilité de faire la sélection (par exemple, if en C / C ++) et la répétition (par exemple, while en C / C ++). Edit: comme l'a souligné Dave Clarke dans les commentaires, le théorème de programmation structuré nécessite également la séquence. Je ne l'ai pas énumérer d'abord cela depuis que je pris pour acquis le lecteur comprendra que les blocs de base d'autres instructions, comme celles fait allusion plus tard pour la lecture et l'écriture dans la mémoire de la mémoire, etc., sont également nécessaires). Il est, bien sûr, il vaut mieux être explicite; vous devez être en mesure de faire ces choses aussi.

Étant donné que ces éléments peuvent être mis en oeuvre en utilisant une instruction de saut conditionnel (par exemple, dans JNZ x86), qui est également suffisante pour équivalence de Turing.

A noter que d'autres éléments sont nécessaires, à savoir, la possibilité d'écrire un nombre illimité de symboles (par exemple, les bits 0 ou 1 ...) à une sorte de banque de mémoire externe. En ce sens, les ordinateurs réels ne sont pas équivalents Turing, car aucun d'entre eux ont une quantité infinie de stockage. Le modèle de Turing est toujours utile, cependant, puisque la quantité de mémoire est généralement énorme, et même si aucun problème un véritable ordinateur peut résoudre peut être résolu par un automate fini déterministe, en utilisant ce modèle de calcul est pas particulièrement utile (depuis le nombre d'états serait absurdement énorme).

Notez que ce n'est pas nécessairement en désaccord avec la réponse de sepp2k; c'est un peu juste une façon différente de penser à la même question.

EDIT:

Notez également que vous n'avez pas vraiment besoin à la fois if et while en C / C ++. Vous pouvez simuler if en utilisant while comme 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 faites attention, c'est. Notez également que si vous avez des fonctions récursives, vous éventuellement besoin aussi la sélection; puisque les fonctions récursives sans sélection ne peut pas vraiment mettre en œuvre des cas de base, de sorte que toute fonction récursive entraînerait une récursion infinie.

EDIT:

En outre, en ce qui concerne votre question de savoir si la possibilité d'écrire un programme qui ne arrêt est suffisante pour l'équivalence Turing, la réponse est non; il est nécessaire, mais pas suffisante. Nous pouvons résoudre le problème de l'arrêt des programmes écrits dans une langue qui ne peuvent pas exprimer des programmes qui ne parviennent pas à arrêter; la réponse est « le programme ne se arrête » pour toutes les instances. Cependant, nous pouvons définir une langue où la seule instruction, la machine à entrer dans une boucle infinie ... un tel langage n'est pas équivalent Turing.

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

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

Les constructions de langage sont interchangeables

Il n'y a pas de critères minimums fixés sur ce qui construit doit en mode natif être fourni par un langage de programmation. Si elle fournit des constructions étranges qui peuvent être en quelque sorte alambiquée d'exprimer un système Turing-complet, alors apparemment ces constructions sont « tout aussi bien » que les autres.

Pour le prouver - une langue qui fournit uniquement une opération est complète Turing « et soustraire branche si zéro »; il existe des langues complètes Turing ne fournissent pas une « branche et si substract zéro » séparée construction, ergo il n'y a pas de construction ou un ensemble de constructions qui est obligatoire.

Les effets de toute construction de langage TP-complet peuvent être émulés par les constructions de toute autre langue TP-complet.

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top