Pourquoi Turing est-il complet?

15

J'utilise un ordinateur numérique pour écrire ce message. Une telle machine a une propriété qui, si vous y réfléchissez, est en fait assez remarquable: c'est une machine qui, si elle est programmée de manière appropriée, peut effectuer tout calcul possible .

Bien sûr, les machines à calculer d'un type ou d'un autre remontent à l'Antiquité. Les gens ont construit des machines qui effectuent l'addition et la soustraction (par exemple, un boulier), la multiplication et la division (par exemple, la règle à calcul), et des machines plus spécifiques au domaine telles que des calculatrices pour les positions des planètes.

Ce qui est frappant avec un ordinateur, c'est qu'il peut effectuer n'importe quel calcul. Tout calcul du tout. Et tout cela sans avoir à recâbler la machine. Aujourd'hui, tout le monde tient cette idée pour acquise, mais si vous vous arrêtez et y réfléchissez, c'est assez étonnant qu'un tel appareil soit possible.

J'ai deux vraies questions :

  1. Quand l'humanité a-t-elle compris qu'une telle machine était possible? Y a-t-il déjà eu un doute sérieux quant à savoir si cela peut être fait? Quand cela a-t-il été réglé? (En particulier, a-t-il été réglé avant ou après la première mise en œuvre effective?)

  2. Comment les mathématiciens ont-ils prouvé qu'une machine Turing-complete peut vraiment tout calculer?

Ce deuxième est délicat. Chaque formalisme semble avoir des choses qui ne peuvent pas être calculées. Actuellement, la «fonction calculable» est définie comme «tout ce qu'une machine de Turing peut calculer». Mais comment savons-nous qu'il n'y a pas de machine légèrement plus puissante qui puisse calculer plus de choses? Comment savons-nous que les machines de Turing sont l'abstraction correcte?

MathematicalOrchid
la source
7
Les ordinateurs (et leurs modèles théoriques, comme les machines de Turing) NE PEUVENT PAS tout calculer. Découvrez par exemple le problème de l' arrêt .
2
Réponse à la deuxième question: nous ne le prouvons pas; c'est une question de définition; il s'avère que ce que nous pensons intuitivement de "calculable" est calculable par les machines de Turing (ou quelque chose d'équivalent). Cette affirmation est connue sous le nom de thèse de Church-Turing .
sdcvvc
2
Les machines comme votre PC qui ont une mémoire finie ne sont pas équivalentes à Turing. Les machines de Turing ont une bande illimitée, ce qui signifie que plus un calcul se poursuit, plus elles peuvent potentiellement utiliser de mémoire. Les PC ne peuvent pas effectuer des calculs qui prennent un temps limité mais qui nécessitent plus de stockage qu'ils n'en ont.
Mike Samuel
3
@MikeSamuel c'est une distinction pédante et s'apparente à dire "il y a un nombre fini de particules dans l'univers, donc tout est à l'état fini". C'est une vraie déclaration, mais pas utile. Il est rarement utile de modéliser un ordinateur du monde réel comme une machine à états finis.
Artem Kaznatcheev

Réponses:

17

L'humanité a officialisé le calcul et a développé deux systèmes pour cela en 1936 avec les articles fondateurs de Alonzo Church sur -calculusλ et Alan Turing (qui aujourd'hui, le 23 juin 2012, aurait 100 ans sinon pour des circonstances méprisables menant à son décès précoce). ce qui est devenu connu sous le nom de machines de Turing. Les deux mathématiciens résolvaient le problème Entscheidungs .

Bien que l'article de Church ait été publié un peu plus tôt, Turing ne le savait pas lorsqu'il a développé ses idées, et l'approche de Turing s'est avérée plus utile pour la conception de machines du monde réel. En effet, il a montré comment concevoir une machine de Turing universelle pouvant être programmée pour exécuter n'importe quel calcul. Cette machine universelle, avec une architecture concrète basée sur le travail de John von Neumann est l'idée de base derrière la machine sur laquelle vous lisez ma réponse.

Comme vous l'avez noté, le calcul est défini comme "calculable sur une machine de Turing" et tous les autres modèles raisonnables de calcul se sont avérés équivalents dans leur puissance. La croyance que tous les modèles raisonnables de calcul sont équivalents dans les problèmes de décision qu'ils peuvent résoudre est connue sous le nom de thèse de Church-Turing . Dans sa forme originale, il est presque entièrement cru par la communauté savante. En fait, il n'est pas complètement clair ce que cela signifierait pour prouver / réfuter la thèse de Church-Turing ; à bien des égards, cela devient une question empirique.

λ calculable) l'informatique quantique est toujours équivalente au modèle de Turing.

Artem Kaznatcheev
la source
1
L'article de Turing de 1936, par rapport au travail de Church à l'époque, était beaucoup plus convaincant dans son argument selon lequel toute fonction numérique qui peut être calculée de manière algorithmique par un humain peut être calculée par une machine de Turing. Les formalismes de Church n'avaient évidemment pas cette propriété, et à ce jour la réduction d'autres systèmes de calcul aux machines de Turing est vitale en raison de l'analyse originale de Turing de ce que les machines de Turing peuvent calculer.
Carl Mummert
1
@CarlMummert Je suis définitivement d'accord, mais le travail de Church doit être mentionné pour être complet. De plus, ce n'est pas du tout insignifiant, alors que la majeure partie de la théorie A est construite autour des MT, la théorie B est beaucoup plus conviviale pour lambda-calc. C'est donc aussi en partie une différence de cultures.
Artem Kaznatcheev
Attendez - vous dites donc qu'il n'a pas été prouvé qu'il n'y a pas de système de calcul plus puissant? Ce n'est qu'une supposition ?
MathematicalOrchid
@MathematicalOrchid tous raisonnables modèles de calcul (raisonnables: environ moyens à une seule fois travailler sur des sections finies d'objets et de faire une seule des nombreuses options finiment) que je connais ont été montré équivalent aux machines de Turing.
Artem Kaznatcheev le
2
@MathematicalOrchid Pour fournir une réponse potentiellement plus simple à votre question de suivi: à droite, personne n'a prouvé qu'il n'y a pas de modèle de calcul raisonnable plus puissant qu'une MT. "Hypothèse" est un mot pour cela; l '"hypothèse" en est une autre. Nous pourrions nous réveiller demain et découvrir un nouveau et meilleur modèle informatique sur CNN. C'est peu probable, mais possible.
Patrick87
-2

Il y a une raison pour laquelle on l'appelle une machine de Turing, et c'est parce qu'elle a été inventée par Alan Turing. Il a rédigé un document à ce sujet en 1936, établissant ces concepts. Si vous voulez en savoir plus sur les machines de Turing, vérifiez le papier. Il était sérieusement douté, avant qu'il n'en conçoive et n'en construise un qui fendait l'Enigma, que ce concept puisse réellement fonctionner. Cependant, les Britanniques étaient assez désespérés et il était un génie, alors ils lui faisaient confiance et cela a payé massivement.

Cependant, quand on y pense un peu plus, ce n'est vraiment pas si étonnant du tout. On savait bien avant Turing que toutes les mathématiques pouvaient être réduites à un ensemble d'axiomes. Tout ce que vous auriez à faire est de donner à l'ensemble d'instructions la capacité d'exécuter ces axiomes, et c'est parti.

Chiot
la source
Turing n'a pas conçu ni construit d'énigme (bien qu'il ait conçu un autre ordinateur qui n'a jamais été construit). Votre deuxième paragraphe est bien rédigé: une grande partie de l'excitation à l'époque de Turing (et c'était d'ailleurs le point de son propre article) liée aux limites du calcul.
Marcin
On lui faisait confiance? Seulement jusqu'à ce qu'il soit publiquement prouvé qu'il était homosexuel, nous l'avons tué pour cela. Il a également été prouvé qu'il existe un ensemble de problèmes qui peuvent être énoncés dans n'importe quel cadre axiomatique qui ne peuvent jamais être prouvés avec ces axiomes.
@ TonyHopkinson: Je sais. Cependant, le travail de la MT n'est pas de tout calculer , mais seulement de calculer ce qui peut être calculé. Votre déclaration indique seulement qu'il existe des calculs qui ne peuvent pas être prouvés comme étant corrects. Cela ne signifie pas qu'ils ne peuvent pas être réalisés.
@Marcin: Je n'ai jamais laissé entendre que Turing a conçu ou construit l'Enigma. J'ai dit qu'il jouait un rôle critique dans la machine qui a fait fendre l'Enigma.
7
Cette réponse est fausse . Turing n'a pas conçu une MT pour casser l'énigme, il a aidé à concevoir la Bombe qui était une machine spécialisée pour attaquer le chiffre Enigma et non universelle. De plus, on ne savait pas que les mathématiques pouvaient être réduites à un ensemble d'axiomes. En fait, en 1931, Godel prouve le contraire et c'est sur les idées de cette preuve que se fonde l'œuvre de Turing. Même le premier commentaire sur la lecture du document original de Turing est trompeur. Bien que le papier soit excellent, si vous voulez simplement apprendre les bases, un manuel moderne comme Sipser est meilleur.
Artem Kaznatcheev