Que signifie être complet de Turing?

34

Je vois que la plupart des définitions de ce que signifie être Turing-complet sont, dans une certaine mesure, tautologiques. Par exemple, si vous Google "que signifie Turing Complete", vous obtenez:

Un ordinateur est complet à Turing s'il peut résoudre tout problème qu'une machine de Turing peut ...

Bien qu'il soit très bien défini si différents systèmes sont complets ou non complets de Turing, je n'ai pas vu d'explication des implications / conséquences d'être complet de Turing.

Que peut faire une machine de Turing là où il n’existe aucune machine non-Turing qui puisse également effectuer la même tâche? Par exemple, un ordinateur peut effectuer des calculs simples (1+5)/3=?, mais une calculatrice ordinaire peut également les effectuer, ce qui n’est pas complet si toutes les réponses sont correctes.

Existe-t-il un moyen de définir les capacités de Turing Machine sans se contenter de "pouvoir simuler une autre machine de Turing"?

sashoalm
la source
31
Recherchez la définition de "machine de turing". Il n’ya pas de définition circulaire, puisqu’une machine de turing n’est pas définie comme "pouvant simuler une autre machine de turing" - c’est un ordinateur théorique entièrement conçu (en gros, une machine à états à bandes infinie). Vous mélangez simplement "turing-complete" et "turing machine". Autant que je sache, nous ne connaissons toujours aucun algorithme qui ne puisse pas fonctionner sur une machine de turing, mais c'est peut-être juste ma propre ignorance.
Luaan
2
@Luaan La thèse Church-Turing serait d'accord avec vous.
Brian McCutchon
"Y a-t-il un moyen de définir les capacités de Turing Machine". Sûr. La théorie explique combien d’espace et de temps sont nécessaires pour résoudre les algorithmes avec les machines de Turing (L, NL, P, NP, PSPACE, etc.), et il existe également des problèmes qui ne peuvent pas être résolus (qui peuvent généralement être résolus en réduisant autres problèmes insolubles). Un exemple de problème qui ne peut pas être résolu par les machines de Turing est le problème d’arrêt.
Millie Smith
En matière de théorie de la CS (ou de toute autre théorie), il est toujours préférable de lire un livre sur le sujet plutôt que de le consulter sur Google et de lire quelques articles de blog sur le sujet qui sont, dans de nombreux cas, écrits par des personnes qui ne comprennent pas parfaitement le sujet. se. Un bon livre vous fera gagner du temps, vous donnera une image plus large et une meilleure compréhension.
Bozidar Sikanjic
La fonction Ackermann est un exemple frappant de ce qu'une machine de Turing peut calculer, mais pas un modèle de calcul plus limité ( récursion primitive ).
Zwol

Réponses:

13

J'ai réfléchi un moment s'il fallait ajouter une autre réponse. Les autres réponses portent sur le milieu de sa question (à propos de "turing complete", "tautology" et ainsi de suite). Permettez-moi de saisir la première et la dernière partie, et donc le tableau plus grand et légèrement philosophique:

Mais qu'est-ce que ça veut dire?

Que signifie être complet de Turing?

Existe-t-il un moyen de définir les capacités de Turing Machine sans se contenter de "pouvoir simuler une autre machine de Turing"?

De manière informelle, être complet de Turing signifie que votre mécanisme peut exécuter tous les algorithmes imaginables, quelle que soit leur complexité, leur profondeur, leur récursivité, leur complexité (longueur de code) et leur taille ou durée de stockage. nécessaire pour l'évaluer. Il va sans dire qu'il ne réussit que si le problème est calculable, mais si elle est calculable, il va réussir (arrêt).

(NB: pour découvrir pourquoi il s’agit là d’une démarche "informelle", consultez la thèse de Church-Turing qui va dans ce sens, avec une formulation plus élaborée; en tant que thèse, elle pourrait ou ne pourrait pas être correcte, cependant. Merci à @DavidRicherby pour. soulignant cette petite omission dans un commentaire.)

"Algorithme" signifie ce que nous entendons couramment par algorithme informatique aujourd'hui; C'est-à-dire une série d'étapes discrètes manipulant le stockage, avec une logique de contrôle mélangée. Ce n'est toutefois pas comme une machine Oracle, c'est-à-dire qu'il ne peut pas "deviner".

Exemple pour un langage pratique non-tc

Si vous vous êtes programmé, vous connaissez probablement les expressions régulières, utilisées pour faire correspondre les chaînes à un motif.

Ceci est un exemple de construction qui n'est pas Turing Complete. Vous pouvez facilement trouver des exercices où il est tout simplement impossible de créer une expression régulière correspondant à certaines phrases.

Par exemple (et cela a sûrement vexé de nombreux programmeurs dans des applications réelles), il est théoriquement et pratiquement impossible de créer une expression régulière correspondant à un langage de programmation ou à un document XML: il est impossible pour une expression rationnelle de trouver la structure de bloc ( do ... endou { ... }dans les langues; ouverture et fermeture des balises dans les documents XML) s’ils sont autorisés à avoir une profondeur arbitraire. S'il existe une limite, par exemple, vous ne pouvez avoir que 3 niveaux de "récursivité", vous pouvez alors trouver une expression régulière; mais si ce n'est pas limité, alors c'est un non-aller.

Comme il est évidemment possible de créer un programme dans un langage complet de Turing (comme C) pour analyser le code source (n'importe quel compilateur le fait), les expressions rationnelles ne pourront jamais simuler ledit programme; elles ne sont donc pas, par définition, Turing-complete.

Motivation

L'idée de la machine à turing en soi n'a rien de pratique; C'est-à-dire que Turing ne l'a certainement pas inventé pour créer un véritable ordinateur ou quelque chose du genre, contrairement à Charles Babbage ou von Neumann, par exemple. Le concept de la machine de Turing est extrêmement simple. Cela consiste en presque rien. Il réduit les ordinateurs possibles (et réels) au strict minimum imaginable.

Le but de cette simplification, à son tour, est que cela facilite la réflexion sur des questions théoriques (telles que l’arrêt des problèmes, les classes de complexité et tout ce que l’informatique théorique se dérange). Une caractéristique en particulier est qu’il est généralement très facile de vérifier si une langue ou un ordinateur donné peut simuler une machine de Turing en programmant simplement ladite machine de Turing (ce qui est si facile!) Dans cette langue.

À l'infini

Notez que vous n'avez jamais besoin de temps infini ou de stockage; mais le temps et le stockage sont sans limite. Ils auront une valeur maximale pour chaque exécution calculable, mais il n’ya aucune limite quant à la taille de cette valeur. Le fait qu'un ordinateur réel finisse par manquer de RAM est passé sous silence. Ceci est bien sûr une limite pour tout ordinateur physique, mais cela est également évident et sans intérêt pour la "puissance de calcul" théorique de la machine. En outre, nous ne sommes pas intéressés par le temps que cela prend réellement. Ainsi, notre petite machine peut utiliser des quantités arbitraires de temps et d'espace, ce qui la rend absolument impraticable.

... et au-delà

Un dernier point étonnant, alors, est qu'un tel simple, chose simple peut faire tout tout ordinateur réel concevable pourrait jamais , dans tout l'univers, accomplir (juste très lent) - au moins autant que nous connaissons aujourd'hui.

AnoE
la source
"De manière informelle, être complet de Turing signifie que votre mécanisme peut exécuter n'importe quel algorithme auquel vous pourriez penser" Eh bien, cela repose sur l'acceptation de la thèse de Church-Turing, selon laquelle les machines de Turing peuvent implémenter tous les algorithmes auxquels vous pouvez penser. Vous pouvez également utiliser les machines de Turing comme définition de l’algorithme. Dans ce cas, la déclaration informelle est simplement une version informelle de "peut simuler n’importe quelle machine de Turing" (ce qui n’est pas une mauvaise chose, mais une observation).
David Richerby
Mon impression était que le PO demande une compréhension intuitive de ce que signifie être complet. Par conséquent, ce genre de réponse désinvolte, non théorique, informatique. Merci de l'avoir signalé, je vais l'intégrer à la réponse. @DavidRicherby
AnoE
Merci! C'est le genre de réponse que je cherchais. Je pensais au problème de halte et à la manière dont les langages avec boucles simples bornées sont prévisibles (ils s'arrêtent toujours) - et donc complets. Je pensais que peut-être qu'être complet de Turing signifiait être potentiellement imprévisible d'une certaine manière (chaotique est-il le bon terme pour désigner ces fonctions?)
sashoalm
@sashoalm, content que la réponse vous plaise. Non, l'imprévisibilité ne compte pas vraiment dans le problème. Bounded for-loops (non-tc) est également un bel exemple. En fait, un autre bon exemple pour un langage tc simple (et plus réel) serait un langage qui ne contient que des variables et (non limité) while- c’est déjà suffisant pour être tc. La (dé) frontière de la structure de contrôle est l'un des éléments clés.
AnoE
38

Ce n'est pas du tout tautologique.

Turing-complete est un modèle de calcul s'il peut simuler toutes les machines de Turing, c'est-à-dire qu'il est au moins aussi puissant que les machines de Turing.

Une chose que les machines de Turing peuvent faire est de simuler d’autres machines de Turing (via la machine de Turing universelle). Cela signifie que, si votre modèle de calcul ne peut pas simuler les machines de Turing, il ne peut pas faire au moins une chose que les machines de Turing peuvent faire, de sorte qu'il ne satisfait pas la définition, il n'est donc pas complet. Il n'y a pas de circularité parce que nous n'avons pas défini la complétude Turing en tant que telle: nous avons dit que la complétude Turing est la propriété de pouvoir faire tout ce que les machines Turing peuvent faire.

ab

Existe-t-il un moyen de définir les capacités de Turing Machine sans se contenter de "pouvoir simuler une autre machine de Turing"?

Je ne suis pas sûr de ce que vous entendez par "définir les capacités des machines de Turing". Les capacités sont définies en termes d'automate à états finis opérant sur la bande infinie. (Je ne vais pas répéter la définition complète mais vous pouvez la trouver, par exemple sur Wikipedia .)

David Richerby
la source
19
Je pense que OP mélange Turing machine et Turing complète. Ce qu'il recherche réellement, c'est la définition d'une machine de Turing; Votre dernière phrase est la réponse. en.wikipedia.org/wiki/Turing_machine pourrait aider.
JollyJoker
Alors, que peut faire une machine de Turing? Comme dans, si je voulais prouver que quelque chose peut émuler une machine de Turing, quel ensemble minimal de comportements dois-je être capable de démontrer que ma machine peut faire de même?
Akshat Mahajan
2
Qu'à cela ne tienne - j'ai expliqué qu'il suffisait de démontrer qu'une langue peut imiter le fonctionnement d'une machine de Turing afin de prouver qu'elle est Turing-complete.
Akshat Mahajan
17

Le modèle de calcul de Turing n'est que l'un des nombreux modèles de calcul équivalents. Il a le même pouvoir que les fonctions récursives de Gödel et le calcul lambda de Church, qui ont été proposés à peu près au même moment, ainsi que d'autres modèles tels que la machine à pointeur. Vous pouvez donc affirmer que

Un ordinateur est complet si cela peut résoudre tout problème rencontré par Excel.

Cela fonctionne car Excel est également Turing-complete. Je recommande de jeter un coup d'œil à la page de Wikipedia sur la thèse de Church-Turing et à un article de synthèse de Blass et Gurevich, intitulé Algorithmes: à la recherche de définitions absolues .


En ce qui concerne votre question, que peut faire une machine de Turing par rapport à une machine non-Turing? En général, la réponse dépend malheureusement de la machine non-Turing.

Il est toutefois possible de définir des notions non triviales de problèmes complets de Turing, par exemple:

LAfaAf(a)L

Selon cette définition, les codages appropriés du problème d’arrêt sont Turing-complete, et donc pour une classe raisonnable de machines (en fonction de la définition de "calculable efficacement"), la machine est Turing-complete ssi elle peut en réaliser ) Langage complet-Turing.

Ce formalisme englobe bien d'autres problèmes complets de Turing, dépendant de la définition du terme "calculable efficacement", tels que le problème de correspondance de Turing, et des problèmes concernant les tuiles de Wang et le jeu de la vie. N'importe lequel de ces problèmes peut servir de point de repère au lieu de résoudre le problème.

Yuval Filmus
la source
"La réponse dépend malheureusement de la machine non-Turing" - J'ai modifié ma question parce qu'elle n'était pas claire. Vous pouvez choisir n'importe quelle machine non-Turing, à condition qu'elle puisse effectuer la tâche tout en restant non-Turing-complète.
sashoalm
5
Excel is also Turing-complete.- uniquement si vous pouvez donner à Excel une mémoire infinie. Excel est limité à 1 048 576 lignes et à 16 384 colonnes, ce qui est très proche de l'infini.
MattClarke
5
@MattClarke: C'est vrai, mais du même coup, aucun système jamais construit n'est complet.
Emil
3
@ Emil: exactement, et il est important que les étudiants en CS fassent la distinction entre les capacités des modèles de calcul et les capacités des machines réelles. Ceux d’entre nous qui ont constamment repoussé les limites physiques de nos machines trouvent cette distinction facile à faire, bien sûr. Nous savons donc comment définir une version non restreinte du modèle informatique d'Excel et que ce serait Turing-complete. Même si écrire cette définition est un peu fastidieux.
Steve Jessop
4
@SteveJessop Limites physiques des machines? Comment peut-on frapper une telle chose? 640k est suffisant pour n'importe qui!
David Richerby
4

Tout d'abord, je tiens à souligner que la définition de la complétude de Turing n'est pas du tout tautologique. Prouver non seulement un modèle de calcul Turing-complete est un résultat intéressant en soi, mais cela vous permet également d'étendre immédiatement tous les résultats de la théorie de la calculabilité à cet autre modèle de calcul. Par exemple: les machines à 2 compteurs sont Turing-complete, les machines de Turing ne peuvent pas résoudre le problème d'arrêt, donc aucune machine à 2 compteurs ne le peut.

μ

Cette classe comprend les fonctions «intuitivement calculables», c’est-à-dire que le calcul pourrait être effectué par un humain en suivant un algorithme précis avec un crayon et du papier.

De toute évidence, "calculable intuitivement" n'est pas vraiment une définition formelle, l'identification de "calculable intuitivement" avec "calculable de Turing" est connue sous le nom de thèse de Church-Turing. Étant donné que de nombreuses tentatives formelles de caractérisation de la calculabilité convergent finalement vers un modèle de calcul complet de Turing, bien qu'il n'y ait jamais de preuve formelle d'une telle affirmation au sens mathématique, il y a de bonnes raisons de le croire.

tri rapide
la source
0

Une machine Turing peut calculer le même ensemble de fonctions qu'un ordinateur quantique universel, qui peut simuler n'importe quel système physique:

https://www.cs.princeton.edu/courses/archive/fall04/cos576/papers/deutsch85.pdf

En tant que telle, une machine de Turing est capable d'effectuer tout traitement de l'information autorisé par les lois de la physique, bien qu'elle ne fasse pas toujours ce traitement aussi efficacement que possible.

Alan
la source