Ce qui est Turing Complete ?

Question

Que signifie l’expression « Turing Complete » signifie ?

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

Answer 1

Voici les meilleurs explication:

Une Turing système désigne un système dans lequel un programme peut être écrit qui vous permettra de trouver une réponse (même si avec aucune garantie concernant l'exécution ou de la mémoire).

Donc, si quelqu'un dit "mon nouveau truc c'est de Turing" qui signifie en principe (bien que souvent pas dans la pratique), il pourrait être utilisé pour résoudre n'importe quel problème de calcul.

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

Answer 2

Son souvent utilisé pour définir des langages de programmation « réel », où vous pouvez réellement faire la plupart de ce que vous voulez. Un meilleur exemple est certaines langues qui ne sont pas turing-complet, tels que SQL, XML et JSON.

Wikipedia sur les langues non-turing-complet

Answer 3

De wikipedia:

Turing à l'exhaustivité, nommé d'après Alan Turing, est importante dans la mesure où tous les plausible de conception pour un calcul appareil de mesure avancée peut être émulé par une machine de Turing universelle - un l'observation qui est devenu connu comme la thèse de Church-Turing. Ainsi, un machine qui peut agir comme un universel Machine de Turing peut, en principe, effectuer un calcul que toute autre programmable par ordinateur est capable de faire. Toutefois, cela n'a rien à voir avec l'effort requis pour écrire un programme pour la machine, le temps que ça peut prendre pour la machine pour effectuer le calcul, ou toutes les capacités de la la machine peut posséder qui ne sont pas liés pour le calcul.

Alors que vraiment Turing-complet des machines très probablement physiquement impossible, car ils nécessitent un espace de stockage illimité, Turing l'exhaustivité est souvent mal attribués à des machines physiques ou les langages de programmation qui serait universel, s'ils avaient illimitée le stockage. Tous les ordinateurs modernes sont Turing-complet dans ce sens.

Je ne sais pas comment vous pouvez être plus de non-techniques que l'exception en disant "turing complet signifie" capable de répondre à calculable problème donné assez de temps et d'espace"".

Answer 4

Fondamentalement, Turing-complet est une exigence concise, récursivité illimitée.

Même pas limité par la mémoire.

J’ai pensé cela indépendamment, mais Voici quelques discussions de l’assertion. Ma définition du LSP fournit plus de contexte.

Les autres réponses ici ne définissent directement l’essence fondamentale de Turing-complet.

Answer 5

Turing Complete signifie qu’il est au moins aussi puissant qu’une Machine de Turing. Cela signifie que tout ce qui peut être calculée par une Machine de Turing peut être calculé par un système complet de Turing.

Personne n’a encore trouvé un système plus puissant qu’une Machine de Turing. Donc, pour l’instant, dire un système est Turing Complete est la même chose que dire du système est aussi puissant que n’importe quel système informatique connu.