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"?

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.

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.

$a$$b$

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 .)

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:

$L$$A$$f$$a \in A$$f(a) \in 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.

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.

$\mu$

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.

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.