Qu’est-ce que Turing Complete ?

Question

Que signifie l'expression « Turing complet » ?

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

Answer 1

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 (mais sans aucune garantie concernant le temps d'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 n'importe quel problème de calcul.

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

Answer 2

Voici l'explication la plus simple

Alan Turing a créé une machine capable de prendre un programme, de l'exécuter et d'afficher un résultat.Mais il a ensuite dû créer différentes machines pour différents programmes.Il a donc créé la « Machine de Turing universelle » qui peut prendre N'IMPORTE QUEL programme et l'exécuter.

Les langages de programmation sont similaires à ces machines (bien que virtuelles).Ils prennent des programmes et les exécutent.Désormais, un langage de programmation est appelé "Turing complet", 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 additionne.La machine de Turing peut facilement exécuter ce programme.Mais imaginez maintenant que, pour une raison quelconque, votre langage de programmation ne puisse pas faire le même ajout, alors c'est une machine de Turing incomplète.D'un autre côté, s'il peut exécuter n'importe quel programme comme la machine de Turing universelle, alors c'est Turing complet.

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

Mise à jour:Vous pouvez en savoir plus sur mon article de blog : "JavaScript est terminé pour Turing" — Expliqué

Answer 3

Depuis Wikipédia:

La complétude de Turing, nommée d’après Alan Turing, est significatif en ce sens que chaque conception plausible d’un système informatique l’appareil jusqu’à présent avancé peut être émulé par une machine de Turing universelle — une observation qui est devenue connue sous le nom de la thèse de Church-Turing.Ainsi, un machine qui peut agir comme un La machine de Turing peut, en principe, effectuer un calcul que tout autre programmable est capable de.Cependant, cela n’a rien à voir avec l’effort requis pour écrire un programme pour la machine, le temps que cela peut prendre pour que la machine effectue la calcul, ou toute capacité que le que la machine peut posséder et qui n’ont aucun rapport au calcul.

Bien que les machines vraiment Turing-Complete soient très probablement physiquement impossibles, car elles nécessitent un stockage illimité, l'exhaustivité Turing est souvent attribuée à des machines physiques ou des langages de programmation qui seraient universelles si elles avaient un stockage illimité.Tous les ordinateurs modernes sont Turing-complet en ce sens.

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

Answer 4

Définition informelle

Un langage complet de Turing est capable d’effectuer n’importe quel calcul.Le Thèse Church-Turing déclare que tout calcul réalisable peut être effectué par une machine de Turing.UN Machine de Turing est une machine avec une mémoire vive 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 son démarrage.

Choses qui peuvent rendre une langue NON Turing complète

Une machine de Turing peut prendre des décisions en fonction de ce qu'elle voit en mémoire - La « langue » qui ne prend en charge que +, -, *, et / sur des nombres entiers, Turing n'est pas complet car il ne peut pas faire de choix en fonction de ses entrées, mais une machine de Turing le peut.

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

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

Une machine de Turing possède une mémoire vive - Un langage qui vous permet uniquement de travailler avec la mémoire push et pop les opérations sur une pile ne seraient pas complètes de Turing.Si j'ai un « langage » qui lit une chaîne une fois et ne peut utiliser la mémoire qu'en poussant et en sortant d'une pile, il peut me dire si chaque ( dans la chaîne a le sien ) plus tard en poussant quand il voit ( et éclater quand il voit ).Cependant, il ne peut pas me dire si chaque ( a sa propre ) plus tard et chaque [ a sa propre ] plus tard (notez que ([)] répond à ces critères mais ([]] ne fait pas).Une machine de Turing peut utiliser sa mémoire vive pour suivre ()'sable []est séparément, mais ce langage avec seulement une pile ne le peut pas.

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

Exemples de langages complets de Turing

Si votre langage dispose d'une mémoire vive infinie, d'une exécution conditionnelle et d'une certaine forme d'exécution répétée, il est probablement Turing complet.Il existe des systèmes plus exotiques qui peuvent encore réaliser tout ce qu'une machine de Turing peut réaliser, ce qui en fait également un Turing complet :

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

Answer 5

Fondamentalement, la complétude de Turing est une exigence concise et 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 du LSP fournit plus de contexte.

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

Answer 6

Turing Complete signifie qu'il est au moins aussi puissant qu'un 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é de système plus puissant qu’une machine de Turing.Ainsi, 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 Thèse Church-Turing).

Answer 7

En termes simples, un système Turing-complet peut résoudre n’importe quel problème informatique possible.

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

Ainsi, en pratique, aucun système n’est Turing-complet.

Certains systèmes se rapprochent plutôt de la complétude de Turing en modélisant une mémoire illimitée et en effectuant tous les calculs possibles pouvant tenir dans la mémoire du système.

Answer 8

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

Je recommande fortement The Annotated Turing

@Mark, je pense que ce que vous expliquez est un mélange entre la description de l'Universal Turing Machine et Turing Complete.

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

Answer 9

Ce que je comprends en termes simples :

Turing complet : Un langage/programme de programmation capable d’effectuer des calculs est Turing complet.

Par exemple :

1. Pouvez-vous ajouter deux nombres en utilisant Just HTML.(La réponse est 'Non', vous devez utiliser javascript pour effectuer l'addition.), 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 l'ajout de deux nombres en utilisant ces langages.

J'espère que cela t'aides.

Answer 10

Comme Waylon Flinn a dit:

Turing Complete signifie qu'il est au moins aussi puissant qu'une machine de Turing.

Je pense que c'est incorrect, un système est Turing complet s'il est exactement aussi puissant que la machine de Turing, c'est-à-direchaque calcul effectué par la machine peut être effectué par le système, mais tout calcul effectué par le système peut également être effectué par la machine de Turing.

Answer 11

En termes de langage pratique familiers à la plupart des programmeurs, la manière habituelle de détecter l'exhaustivité de Turing est de savoir si le langage autorise ou autorise la simulation d'instructions while imbriquées et illimitées (par opposition au style Pascal pour les instructions, avec des limites supérieures fixes).

Answer 12

Une base de données relationnelle peut-elle saisir les latitudes et les longitudes des lieux et des routes, et calculer le chemin le plus court entre eux - non.C'est un problème qui montre que SQL n'est pas complet.

Mais C++ peut le faire et résoudre n’importe quel problème.Il en est ainsi.