Qu'est-ce que Turing Complete?

Que signifie l'expression "Turing Complete"?

Pouvez-vous donner une explication simple, sans entrer dans trop de détails théoriques?

Voici l'explication la plus brève:

Un système Turing Complete signifie un système dans lequel un programme peut être écrit qui trouvera une réponse (bien que sans aucune garantie concernant l'exécution ou la mémoire).

Donc, si quelqu'un dit "mon nouveau truc est Turing Complete", cela signifie en principe (bien que souvent pas en pratique) qu'il pourrait être utilisé pour résoudre tout problème de calcul.

Parfois, c'est une blague ... un gars a écrit un simulateur Turing Machine dans vi, il est donc possible de dire que vi est le seul moteur de calcul jamais nécessaire dans le monde.

Voici l'explication la plus simple

Alan Turing a créé une machine qui peut prendre un programme, l'exécuter et afficher un résultat. Mais ensuite, il a dû créer différentes machines pour différents programmes. Il a donc créé "Universal Turing Machine" qui peut prendre n'importe quel programme et l'exécuter.

Les langages de programmation sont similaires à ces machines (bien que virtuels). Ils prennent des programmes et les exécutent. Maintenant, un langage de programmation est appelé "Turing complete", s'il peut exécuter n'importe quel programme (quel que soit le langage) qu'une machine Turing peut exécuter avec suffisamment de temps et de mémoire.

Par exemple: disons qu'il existe un programme qui prend 10 nombres et les ajoute. La machine de Turing peut facilement exécuter ce programme. Mais imaginez maintenant que pour une raison quelconque, votre langage de programmation ne peut pas effectuer le même ajout. Cela le rendrait "Turing incomplet" (pour ainsi dire). D'un autre côté, si elle peut exécuter n'importe quel programme que la machine universelle de Turing peut exécuter, alors c'est Turing complet.

La plupart des langages de programmation modernes (par exemple Java, JavaScript, Perl, etc.) sont tous Turing complets car ils implémentent chacun toutes les fonctionnalités requises pour exécuter des programmes comme l'ajout, la multiplication, la condition if-else, les instructions de retour, les moyens de stocker / récupérer / effacer données et ainsi de suite.

Mise à jour: vous pouvez en savoir plus sur mon article de blog: "JavaScript is Turing Complete" - Explained

De wikipedia :

L'exhaustivité de Turing, du nom d'Alan Turing, est importante en ce que chaque conception plausible d'un appareil informatique jusqu'à présent avancé peut être émulée par une machine Turing universelle - une observation qui est devenue connue sous le nom de thèse de Church-Turing. Ainsi, une machine pouvant servir de machine de Turing universelle peut, en principe, effectuer tout calcul dont tout autre ordinateur programmable est capable. Cependant, cela n'a rien à voir avec l'effort requis pour écrire un programme pour la machine, le temps que cela peut prendre à la machine pour effectuer le calcul ou les capacités que la machine peut posséder qui ne sont pas liées au calcul.

Alors que les machines vraiment complètes de Turing sont très probablement physiquement impossibles, car elles nécessitent un stockage illimité, l'exhaustivité de Turing est souvent attribuée de manière lâche à des machines physiques ou à des langages de programmation qui seraient universels s'ils avaient un stockage illimité. Tous les ordinateurs modernes sont Turing-complets dans ce sens.

Je ne sais pas comment vous pouvez être plus non technique que cela, sauf en disant "turing complete signifie" capable de répondre à un problème calculable avec suffisamment de temps et d'espace "".

Définition informelle

Un langage complet de Turing est celui qui peut effectuer n'importe quel calcul. La thèse de Church-Turing indique que tout calcul réalisable peut être effectué par une machine de Turing. Une machine Turing est une machine avec une mémoire à accès aléatoire infinie et un `` programme '' fini qui dicte quand elle doit lire, écrire et se déplacer dans cette mémoire, quand elle doit se terminer avec un certain résultat et ce qu'elle doit faire ensuite. L'entrée d'une machine de Turing est mise en mémoire avant de démarrer.

Choses qui peuvent rendre un langage NON Turing complet

Une machine de Turing peut prendre des décisions en fonction de ce qu'il voit dans la mémoire - La « langue » qui soutient que +, -, *et /sur les entiers ne sont pas Turing complet car il ne peut pas faire un choix en fonction de son entrée, mais une machine de Turing peut.

Une machine Turing peut fonctionner indéfiniment - Si nous prenions Java, Javascript ou Python et supprimions la possibilité de faire tout type de boucle, GOTO ou appel de fonction, ce ne serait pas Turing complet car il ne peut pas effectuer un calcul arbitraire qui ne termine jamais. Coq est un prouveur de théorème qui ne peut pas exprimer des programmes qui ne se terminent pas, donc ce n'est pas Turing complet.

Une machine Turing peut utiliser une mémoire infinie - Un langage qui était exactement comme Java mais qui se terminerait une fois qu'il aurait utilisé plus de 4 gigaoctets de mémoire ne serait pas Turing complet, car une machine Turing peut utiliser une mémoire infinie. C'est pourquoi nous ne pouvons pas réellement construire une machine Turing, mais Java est toujours un langage complet Turing car le langage Java n'a aucune restriction l'empêchant d'utiliser une mémoire infinie. C'est une des raisons pour lesquelles les expressions régulières ne sont pas complètes.

Une machine Turing a une mémoire à accès aléatoire - Un langage qui vous permet uniquement de travailler avec de la mémoire pushet des popopérations sur une pile ne serait pas Turing complet. Si j'ai un `` langage '' qui lit une chaîne une fois et ne peut utiliser la mémoire qu'en poussant et en sautant à partir d'une pile, il peut me dire si chaque élément (de la chaîne a le sien )plus tard en poussant quand il voit (et en sautant quand il voit ). Cependant, il ne peut pas me dire si chacun (a le sien )plus tard et chacun [a le sien ]plus tard (notez que ([)]cela répond à ces critères mais ([]]ne le fait pas). Une machine de Turing peut utiliser sa mémoire à accès aléatoire pour suivre ()« s et[]est séparément, mais cette langue avec seulement une pile ne peut pas.

Une machine Turing peut simuler n'importe quelle autre machine Turing - Une machine Turing, lorsqu'elle reçoit un «programme» approprié, peut prendre le «programme» d'une autre machine Turing et le simuler sur une entrée arbitraire. Si vous aviez un langage qui était interdit d'implémenter un interpréteur Python, ce ne serait pas Turing complet.

Exemples de langues complètes de Turing

Si votre langue a une mémoire à accès aléatoire infinie, une exécution conditionnelle et une certaine forme d'exécution répétée, c'est probablement Turing complet. Il existe des systèmes plus exotiques qui peuvent encore réaliser tout ce qu'une machine Turing peut faire, ce qui les rend également complets:

• Calcul lambda non typé
• Le jeu de la vie de Conway
• Modèles C ++
• Prolog

Fondamentalement, l'intégralité de Turing est une exigence concise, une récursion illimitée.

Pas même limité par la mémoire.

J'y ai pensé indépendamment, mais voici une discussion de l'affirmation. Ma définition de LSP fournit plus de contexte.

Les autres réponses ici ne définissent pas directement l'essence fondamentale de la complétude de Turing.

Turing Complete signifie qu'elle est au moins aussi puissante qu'une machine de Turing . Cela signifie que tout ce qui peut être calculé par une machine de Turing peut être calculé par un système Turing Complete.

Personne n'a encore trouvé un système plus puissant qu'une machine de Turing. Donc, pour le moment, dire qu'un système est Turing Complete revient à dire que le système est aussi puissant que n'importe quel système informatique connu (voir la thèse de Church-Turing ).

En termes simples, un système complet de Turing peut résoudre tout problème de calcul possible.

L'une des principales exigences est que la taille du bloc-notes soit illimitée et qu'il est possible de revenir en arrière pour accéder aux écritures antérieures sur le bloc-notes.

Ainsi, dans la pratique, aucun système n'est complet à Turing.

Certains systèmes se rapprochent plutôt de la complétude de Turing en modélisant la mémoire illimitée et en effectuant tout calcul possible pouvant tenir dans la mémoire du système.

Je pense que l’importance du concept "Turing Complete" réside dans la capacité à identifier une machine informatique (pas nécessairement un "ordinateur" mécanique / électrique) qui peut voir ses processus être déconstruits en instructions "simples", composées de plus en plus simples instructions qu'une machine universelle pourrait interpréter puis exécuter.

Je recommande vivement The Annotated Turing

@ Mark, je pense que ce que vous expliquez est un mélange entre la description de la machine de Turing universelle et Turing Complete.

Quelque chose qui est Turing Complete, dans un sens pratique, serait une machine / processus / calcul pouvant être écrit et représenté comme un programme, à exécuter par une machine universelle (un ordinateur de bureau). Bien qu'il ne prenne pas en compte le temps ou le stockage, comme mentionné par d'autres.

Ce que je comprends en termes simples:

Turing Complete: Un langage / programme de programmation capable de faire du calcul est Turing complete.

Par exemple :

1. Pouvez-vous ajouter deux nombres en utilisant Just HTML . (Ans est ' Non ', vous devez utiliser javascript pour effectuer l'ajout.), Par conséquent, HTML n'est pas Turing Complete.

2. Des langages comme Java, C ++, Python, Javascript, Solidity pour Ethereum, etc. sont Turing Complete car vous pouvez effectuer des calculs comme ajouter deux nombres à l'aide de ces langages.

J'espère que cela t'aides.

Son complet s'il peut tester et se brancher (a un «si»)

Une machine de Turing nécessite que tout programme puisse effectuer des tests de condition. C'est fondamental.

Considérez un rouleau de piano de joueur. Le piano du joueur peut jouer un morceau de musique très compliqué, mais il n'y a jamais de logique conditionnelle dans la musique. C'est Turing complet.

La logique conditionnelle est à la fois la puissance et le danger d'une machine Turing Complete.

Le rouleau de piano est garanti de s'arrêter à chaque fois. Il n'y a pas de telle garantie pour une MT. C'est ce qu'on appelle le «problème de l'arrêt».

Comme l'a dit Waylon Flinn :

Turing Complete signifie qu'elle est au moins aussi puissante qu'une machine de Turing.

Je crois que c'est incorrect, un système est Turing complet s'il est exactement aussi puissant que la machine de Turing, c'est-à-dire que tous les calculs effectués par la machine peuvent être effectués par le système, mais aussi tous les calculs effectués par le système peuvent être effectués par la machine de Turing .

En termes de langage pratique familier à la plupart des programmeurs, la manière habituelle de détecter l'intégralité de Turing est si le langage permet ou permet la simulation des instructions imbriquées sans limite (par opposition au style Pascal pour les instructions, avec des limites supérieures fixes).

Une base de données relationnelle peut-elle entrer des latitudes et des longitudes de lieux et de routes et calculer le chemin le plus court entre elles - non. Il s'agit d'un problème qui montre que SQL n'est pas Turing complet.

Mais C ++ peut le faire et peut faire n'importe quel problème. Il en est ainsi.