Pourquoi Turing est-il complet?

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?

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$\lambda$ 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.

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

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.