Une machine de Turing est-elle «par définition» la machine la plus puissante?

54

Je conviens qu'une machine de Turing peut résoudre "tous les problèmes mathématiques possibles". Mais c’est parce qu’il ne s’agit que d’une représentation machine d’un algorithme: faites ceci en premier, puis faites-le, et enfin en sortie.

Je veux dire que tout ce qui peut être résolu peut être représenté par un algorithme (parce que c'est précisément la définition de «résoluble»). C'est juste une tautologie. Je n'ai rien dit de nouveau ici.

Et en créant une représentation automatique d’un algorithme, il résoudra tous les problèmes possibles et n’a rien de nouveau. C'est aussi une simple tautologie. Donc, en gros, quand on dit qu'une machine de Turing est la machine la plus puissante, cela signifie en réalité que la machine la plus puissante est la machine la plus puissante!

Définition du "plus puissant": Ce qui peut accepter n'importe quelle langue.
Définition de "Algorithme": Processus permettant de faire n'importe quoi. Représentation de la machine "Algorithm": Une machine qui peut tout faire.

Il est donc logique que la représentation d’un algorithme par la machine soit la machine la plus puissante. Quelle est la nouvelle chose qu'Alan Turing nous a donnée?

Sounak Bhattacharya
la source
9
Le retourneur ne peut pas résoudre le problème d’arrêt. Cependant, il n'y a aucune preuve qu'il n'y a pas de machine pour le résoudre. Le modèle est en quelque sorte une MT avec une approche oracle ou complètement différente. Si vous suivez la thèse de l'Église, TM ne représente que les machines que nous utilisons actuellement.
Eugene
16
C'est la machine la plus puissante que nous sachions construire . Eh bien, en fait non, nous ne pouvons construire que des automates finis.
Raphaël
13
Votre problème est que vous pensez aux MT comme quelque chose qui est venu après. Ce n'était pas. Il était (et est) utilisé pour définir la classe des problèmes calculables par Turing . De nombreux modèles équivalents ont été trouvés, mais cela ne change pas la définition.
Raphaël
3
Il existe des centaines d'architectures informatiques différentes (Turing-complete), toutes avec des jeux d'instructions très différents. Je ne pense pas qu'il soit évident du tout qu'il n'y a pas de problème que l' on peut résoudre , mais un autre ne peut.
BlueRaja - Danny Pflughoeft
5
... ce que vous dites n'est pas simplement la thèse de Church-Turing ? Autant que nous sachions, personne n'a réfuté cette thèse, mais nous ne pouvons pas exclure l'existence d'un modèle de calcul différent, "raisonnable" (c'est-à-dire utilisable d'une manière ou d'une autre) et plus puissant que les MT.
Bakuriu

Réponses:

135

Je conviens qu'une machine de Turing peut résoudre "tous les problèmes mathématiques possibles".

Eh bien, vous ne devriez pas, parce que ce n'est pas vrai. Par exemple, les machines de Turing ne peuvent pas déterminer si les polynômes à coefficients entiers ont des solutions entières ( dixième problème de Hilbert ).

Turing Machine est-elle «par définition» la machine la plus puissante?

Non, nous pouvons imaginer une hiérarchie infinie de machines plus puissantes . Cependant, la machine de Turing est la machine la plus puissante que nous sachions, du moins en principe, construire. Ce n’est cependant pas une définition: c’est juste que nous n’avons aucune idée de la manière de construire quelque chose de plus puissant, ou même si cela est possible.

Quelle est la nouvelle chose qu'Alan Turing nous a donnée?

Une définition formelle de l'algorithme. Sans une telle définition (par exemple, la machine de Turing), nous n'avons que des définitions informelles d'algorithme, du type "procédure finement spécifiée pour résoudre quelque chose". OK super. Mais quelles étapes individuelles ces procédures sont-elles autorisées à suivre?

Les opérations arithmétiques de base sont-elles des étapes? Est-ce que trouver le gradient d'une courbe est une étape? Est-ce que trouver des racines de polynômes est une étape? La recherche de racines entières de polynômes est-elle une étape? Chacune de celles-ci semble à peu près aussi naturelle. Cependant, si vous les autorisez toutes, vos "procédures finement spécifiées" sont plus puissantes que les machines de Turing, ce qui signifie qu'elles peuvent résoudre des problèmes qui ne peuvent pas être résolus par des algorithmes. Si vous permettez tout sauf le dernier, vous êtes toujours dans les domaines du calcul de Turing.

Si nous n'avions pas de définition formelle de l'algorithme, nous ne pourrions même pas poser ces questions. Nous ne serions pas en mesure de discuter de ce que les algorithmes peuvent faire, parce que nous ne savons pas ce qu'est un algorithme est .

David Richerby
la source
3
Les commentaires ne sont pas pour une discussion prolongée; cette conversation a été déplacée pour discuter .
DW
Ne voulez-vous pas dire des solutions rationnelles? Je pense que des solutions entières sont possibles à faire en un nombre fini d'étapes.
Trenin
2
a+iba,bZ
Je l'ai. De plus, ce que je pensais être possible s'avère être beaucoup plus difficile que je ne le pensais.
Trenin
64

Vous n'êtes pas correct lorsque vous faites plusieurs fois des déclarations sur le fait que ceci ou cela est "juste une tautologie". Permettez-moi donc de placer vos revendications dans un contexte historique.

Tout d'abord, vous devez préciser les concepts que vous utilisez. Quel est un problème? Qu'est-ce qu'un algorithme? Qu'est ce qu'une machine? Vous pensez peut-être que cela est évident, mais une bonne partie des années 1920 et 1930 a été dépensée par des logiciens pour essayer de comprendre ces choses. Plusieurs propositions, parmi lesquelles les machines de Turing, ont été les plus réussies. Il s'est avéré par la suite que les autres propositions étaient équivalentes aux machines de Turing. Vous devez imaginer une époque où le mot "ordinateur" signifiait une personne, pas une machine. Vous ne faites que surfer sur la vague et les conséquences des brillantes inventions d'esprits brillants d'il y a cent ans, sans vous en rendre compte.

Les machines de Turing sont décrites concrètement en termes d'états, d'une tête et d'une bande de travail. Il est loin d’être évident que cela épuise les possibilités informatiques de l’univers dans lequel nous vivons. Ne pourrions-nous pas créer une machine plus puissante utilisant l’électricité, l’eau ou des phénomènes quantiques? Que faire si nous volons une machine de Turing dans un trou noir à la bonne vitesse et dans la bonne direction, afin qu’elle puisse effectuer une infinité d’étapes dans ce qui nous apparaît comme du temps fini? Vous ne pouvez pas simplement dire «évidemment pas» - vous devez d’abord faire des calculs en relativité générale. Et si les physiciens trouvaient un moyen de communiquer et de contrôler des univers parallèles, de manière à pouvoir faire fonctionner une infinité de machines de Turing en parallèle?

Il ne pas question qu'à l' heure actuelle nous ne pouvons pas faire ces choses. Ce qui est important, cependant, est que vous compreniez que Turing devait penser à ce qui était physiquement possible (sur la base des connaissances en physique de l’époque). Il n'a pas simplement écrit "une simple tautologie". Loin de là, il a soigneusement analysé ce que le calcul signifie de manière informelle, puis il a proposé un modèle formel, argumenté très soigneusement que ce modèle rend compte de ce que les gens comprenaient par "calcul", et il en a tiré d'importants théorèmes. L'un de ces théorèmes dit que les machines de Turing ne peuvent pas résoudre tous les problèmes mathématiques (contrairement à l'une de vos fausses déclarations). Tout cela dans un seul papier, écrit pendant la vaccination d’été, alors qu’il était étudiant.était l'invention de l'idée de l'ordinateur moderne polyvalent. Après cela, ce n’était plus qu’une simple affaire d’ingénierie.

Cela répond-il à ce que Turing a contribué à l’humanité au-delà d’une simple tautologie? Et avez-vous lu son journal ?

Andrej Bauer
la source
19
"Vous devez imaginer une époque où le mot" ordinateur "signifiait une personne, pas une machine." Ceci est un rappel très utile. Essentiellement, Turing a essayé de simuler efficacement, avec sa "machine", les opérations qu’une personne pouvait faire avec un stylo et du papier à ce moment-là pour calculer quelque chose.
Sorrop
2
"Son théorème sur l'existence de machines universelles était l'invention de l'ordinateur moderne polyvalent." - Eh bien .... dans le monde mathématique, peut-être. Des personnes comme Konrad Zuse ont développé des ordinateurs à usage général de manière indépendante.
Raphaël
6
@AndrejBauer Cela suggère toujours une chronologie et une dépendance qui n'existaient pas, pas dans tous les cas. Je ne vous en veux pas - peu de gens savent ce que Zuse a fait quand. Le fait est qu'il a construit des ordinateurs à partir de 1935 tout au long de la Seconde Guerre mondiale sans grande intervention, voire aucune, de l'extérieur de l'Allemagne. Il a également développé son Plankalkül pendant cette période. J'imagine que c'était avec les ordinateurs, comme avec beaucoup d'autres choses: le temps était mûr, et beaucoup d'esprits pensaient dans le même sens. Le fait est que, malgré toutes ses contributions, Turing n’a pas inventé l’informatique .
Raphaël
12
@Raphael: Konrad Zuse ne savait pas que sa machine pouvait traiter tous les problèmes informatiques (nous savons maintenant que ses machines SONT Turing complètes - mémoire modulo). Ce que Turing a contribué n’est PAS l’idée que les machines peuvent effectuer des calculs - Babbage l’a déjà fait avant Zuse ou Turing. Turing a contribué à l’idée que les jeux d’instructions et les langages de programmation n’ont guère d’importance en théorie. Ce n'est pas une idée évidente. Ironiquement, c'est cette idée qui anime le développement des processeurs et des langages de programmation
slebetman
1
"les jeux d'instructions et les langages de programmation n'ont pas vraiment d'importance en théorie" - c'est clairement faux. Les différences peuvent avoir de l' importance, mais elles ne le sont pas toujours. Turing a défini un certain modèle de calcul et a affirmé qu'il était aussi puissant que possible. Pris entre les limites de la mémoire infinie et des modèles plus puissants, je ne suis pas sûr que cette affirmation soit valable. Donc, d’une certaine manière, il n’a fait rien d’autre que Zuse, si ce n’était avec les mathématiques au lieu du métal.
Raphaël
23

Que "tout ce qui peut être résolu puisse être représenté par un algorithme" n’est pas évident du tout.

Cela a fait l'objet d'intenses débats depuis qu'Alan Turing, qui a repris les idées de Alonzo Church, a proposé une définition des nombres calculables qui prenait la forme de la machine à laquelle vous faites référence. Fait important, ces personnes n'étaient pas les seules à travailler sur ce genre de choses à cette époque.

Nous l'appelons encore une thèse - ou une conjecture - puisque "tout ce qui peut être calculé" n'est clairement pas un objet mathématique précis, dont la structure et l'étendue pourraient être étudiées de manière non spéculative.

André Souza Lemos
la source
1
Mais tout ce qui peut être résolu doit être résolu par un "processus" (par définition). Nous ne connaissons peut-être pas le processus permettant de résoudre un problème "résolu" particulier à l'heure actuelle. Dans ce cas, cela signifie que le problème peut être résolu mais ne peut pas être résolu maintenant. Cela ne signifie-t-il pas que "tout ce qui peut être résolu peut être représenté par un algorithme" parce que "processus" = "algorithme"? Pourquoi dites-vous que ce n'est pas évident?
Sounak Bhattacharya
13
Qu'est-ce qu'un "processus"? Vous voyez, il est facile de tourner en rond, en substituant un concept incertain à un autre. La tentative de Turing était en fait une expérience de pensée incarnée, qui nourrit encore notre imagination, même de nos jours. Ce n'est pas une petite chose.
André Souza Lemos
@SounakBhattacharya Par un processus (d'années et de génie), Sir Andrew Wiles a prouvé que le dernier théorème de Fermat était vrai. Imaginez-vous qu’un MT aurait pu prendre cette décision?
OJFord
1
@OllieFord Eh bien, si la preuve est suffisamment rigoureuse pour que chaque étape puisse être exprimée en termes d'axiomes existants bien spécifiés, la preuve peut être vérifiée par une machine de Turing. Nous pourrions alors spécifier une machine de Turing qui énumère toutes les preuves possibles et sûrement (mais très très lentement) la machine trouverait une telle preuve. Une simple implémentation physique de cette machine de Turing prendrait plus de 400 ans et beaucoup plus de temps que la durée de vie attendue de l'univers.
Gmatht
19

Tout d’abord, il est important de garder à l’esprit que Turing Machines a été initialement conçue par Turing, non pas comme un modèle de tout type d’ordinateur physiquement réalisable, mais plutôt comme une limite idéale à ce qui est calculable par un humain calculant de manière mécanique pas à pas. manière (sans aucune utilisation de l'intuition). Ce point est largement incompris - voir [1] pour un excellent exposé sur ce sujet et sur des sujets connexes.

Les limitations de finitude proposées par Turing pour ses machines de Turing sont basées sur les limitations supposées de l'appareil sensoriel humain. Les généralisations des analyses de Turing sur des dispositifs informatiques réalisables physiquement (et des thèses analogues de Church-Turing) ne sont venues que beaucoup plus tard (1980) à cause de Robin Gandy - avec des limitations basées sur les lois de la physique. Comme le dit Odifreddi à la p. 51 de [2] (bible de la théorie de la récurrence classique)

Les machines Turing sont des appareils théoriques, mais elles ont été conçues en tenant compte des contraintes physiques. En particulier, nous avons incorporé dans notre modèle des restrictions provenant de:

  • (a) ATOMISM, en s'assurant que la quantité d'informations pouvant être codée dans n'importe quelle configuration de la machine (en tant que système fini) est limitée; et

  • (b) RELATIVITÉ, en excluant les actions à distance et en faisant en sorte que l'effet causal se propage par le biais d'interactions locales. Gandy [1980] a montré que la notion de machine de Turing est suffisamment générale pour englober, de manière précise, tout dispositif informatique satisfaisant à des limitations similaires.

et sur p. 107: (Théorie générale des dispositifs déterministes discrets)

L'analyse (Church [1957], Kolmogorov et Uspenskii [1958], Gandy [1980]) part des hypothèses de l'atomisme et de la relativité. Le premier réduit la structure de la matière à un ensemble fini de particules de base de dimensions limitées, et justifie ainsi la possibilité théorique de démanteler une machine en un ensemble de constituants de base. Ce dernier impose une limite supérieure (la vitesse de la lumière) à la vitesse de propagation des changements de causalité, et justifie donc la possibilité théorique de réduire l'effet de causalité produit dans un instant t sur une région limitée de l'espace V, aux actions produites par les régions. dont les points se trouvent dans la distance c * t à partir d’un certain point V. Bien entendu, les hypothèses ne tiennent pas compte des systèmes qui sont continus ou qui permettent une action à distance illimitée (comme les systèmes gravitationnels de Newton).

L’analyse de Gandy montre que LE COMPORTEMENT EST RÉCURSIF POUR TOUT APPAREIL FIXÉ LIANT À LA COMPLEXE DE SES CONFIGURATIONS POSSIBLES (en ce sens que les niveaux de construction conceptuelle à partir de constituants et le nombre de constituants dans toute partie structurée de toute configuration, sont délimitées), ET FIXED FINITE, DES ENSEMBLES D'INSTRUCTIONS POUR DES ACTIONS LOCALES ET GLOBALES (le premier expliquant comment déterminer l'effet d'une action sur des parties structurées, le second comment assembler les effets locaux). En outre, l'analyse est optimale en ce sens que, lorsqu'elle est précise, tout assouplissement des conditions devient compatible avec tout comportement, et fournit ainsi une description suffisante et nécessaire du comportement récursif.

L'analyse de Gandy donne une perspective très éclairante sur la puissance et les limites de Turing Machines. Il vaut la peine de le lire pour approfondir ses connaissances sur ces questions. Soyez averti cependant que le document de Gandy de 1980 [3] est considéré comme difficile, même par certains cognoscenti. Vous trouverez peut-être utile de consulter d’abord les documents de [4] de J. Shepherdson et A. Makowsky.

[1] Sieg, Wilfried. Procédures mécaniques et expérience mathématique. [pp. 71–117 en mathématiques et esprit. Documents de la Conférence sur la philosophie des mathématiques tenue au Amherst College, Amherst, Massachusetts, du 5 au 7 avril 1991. Édité par Alexander George. Logic Comput. Philos., Oxford Univ. Presse, New York, 1994. ISBN: 0-19-507929-9 MR 96m: 00006 (Rapporteur: Stewart Shapiro) 00A30 (01A60 03A05 03D20)

[2] Odifreddi, Piergiorgio. Théorie de la récursion classique. La théorie des fonctions et des ensembles de nombres naturels. Avec une préface de GE Sacks. Etudes sur la logique et les fondements de la mathématique, 125. North-Holland Publishing Co., Amsterdam-New York, 1989. xviii + 668 p. ISBN: 0-444-87295-7 MR 90d: 03072 (Rapporteur: Rodney G. Downey ) 03Dxx (03-02 03E15 03E45 03F30 68Q05)

[3] Gandy, Robin. Thèse de l'Eglise et principes de mécanismes. Le symposium de Kleene. Actes du symposium tenu à l'Université du Wisconsin, Madison, Wisconsin, du 18 au 24 juin 1978, sous la direction de Jon Barwise, H. Jerome Keisler et Kenneth Kunen. Etudes sur la logique et les fondements des mathématiques, 101. North-Holland Publishing Co., Amsterdam-New York, 1980. xx + 425 p. ISBN: 0-444-85345-6 MR 82h: 03036 (Reviewer: Douglas Cenzer) 03D10 (03A05)

[4] La machine de Turing universelle: une enquête d'un demi-siècle. Deuxième édition. Edité par Rolf Herken. Computerkultur [Culture informatique], II. Springer-Verlag, Vienne, 1995. xvi + 611 p. ISBN: 3-211-82637-8 MR 96j: 03005 03-06 (01A60 03D10 03D15 68-06)

Bill Dubuque
la source
2
Merci beaucoup! J'ai toujours pensé que les machines de Turing étaient étrangement inélégantes, mais cela explique parfaitement pourquoi cela peut être mal conçu.
PJTraill
6

La meilleure discussion populaire sur cette question que j'ai jamais lue est l'essai du professeur Scott Aaronson du MIT Qui peut nommer le plus grand nombre? , dans lequel il explore, entre autres, les implications des machines super-Turing, des machines super-duper-Turing et des machines super-duper-pooper-Turing.

James Brock
la source
2
Après "super-duper-pooper", il y a "super-duper-ooper-flooper", ou du moins c'est ce que je me souviens de quand j'avais peut-être 7 ou 8 ans. C'est probablement la terminologie formelle correcte.
Peter Cordes
4

Non, les MT ne sont pas très puissants. Deux exemples:

a) Il pourrait y avoir d'autres machines qui calculent les mêmes résultats qu'une MT, mais avec un algorithme plus rapide (par exemple, les facteurs premiers calculant les ordinateurs quantiques). "Plus rapide" est un type de pouvoir.

b) Les MT ne peuvent pas représenter des nombres réels généraux avec une précision parfaite. Mais un ordinateur analogique (AC) pourrait être capable de représenter et de faire de l'arithmétique avec des nombres réels avec une précision parfaite. Ce serait plus puissant que n'importe quel TM.


Bien sûr (b) nécessite que notre univers ait des propriétés continues (gravité?) Que le AC peut utiliser pour représenter les valeurs réelles. Peut-être que chaque propriété physique, y compris la gravité, est quantifiée. Mais nous pouvons spéculer sur les machines dans un univers continu. Donc, les MT ne sont pas les plus puissants "par définition".

Adam Gawne-Cain
la source
3
Bienvenue sur le site! "Plus puissant" dans le contexte de la théorie du calcul signifie généralement "capable de calculer plus de fonctions", plutôt que "capable de calculer en moins d'étapes", donc je ne suis pas sûr que votre (a) compte vraiment. En outre, on ne voit pas comment un ordinateur pourrait utiliser de vraies valeurs. Comment pourriez-vous entrer une valeur réelle qui n'était pas, par exemple, un réel calculable? Comment diriez-vous à quelqu'un d'autre quelle valeur il devrait apporter à sa machine continue et comment géreriez-vous le bruit? Mais c’est peut-être une objection idiote du type «Comment produiriez-vous assez de ruban pour que la machine de Turing puisse l’utiliser»?
David Richerby
-4

Si vous examinez la complexité des calculs, une machine de Turing est la machine la plus puissante, car elle possède une mémoire illimitée, et aucune machine réelle ne l’a. Toute machine réelle ne peut résoudre des problèmes de taille arbitraire; ils ne peuvent même pas lire un problème, encore moins le résoudre.

Par contre, si vous tentiez de mettre en place une vraie machine de Turing, supposons qu’elle arrête et sonne une alarme s’il n’ya plus de bande, vous constaterez qu’il faudrait beaucoup plus d’étapes pour effectuer tout type de calcul. que disons la vraie machine dans un téléphone pas cher, et serait beaucoup plus lent à résoudre de vrais problèmes. Vous constaterez également que l'écriture d'une réponse sur une bande n'est pas une très bonne interface utilisateur. Et vous constaterez que beaucoup de gens utilisent des ordinateurs non pas pour résoudre des problèmes, mais pour envoyer des photos nues à leurs amis et pour regarder des vidéos de chats, et une machine de Turing ne sert à rien du tout.

gnasher729
la source
12
Pourriez-vous préciser comment cela répond à la question?
David Richerby
1
De toute évidence, une vraie machine de Turing serait capable de traiter des photos et des vidéos. Bien sûr, un certain type de périphérique de sortie d’image serait nécessaire pour que les humains puissent le voir, mais cela s’applique à n’importe quel ordinateur; un CPU + mémoire sur une carte de circuit n'est pas "aucune utilisation pour ça du tout" non plus.
Hyde
1
Parmi les modèles de machines avec une mémoire infinie, les TM ne sont pas les plus puissants!
Raphaël