Les raisons historiques de l’adoption de la machine de Turing en tant que modèle de calcul principal.

Je crois comprendre que le modèle de Turing est devenu le "standard" dans la description du calcul. Je voudrais savoir pourquoi. Si le modèle TM est devenu plus largement utilisé que d’autres modèles théoriquement équivalents (à ma connaissance), comme le μ-récursion de Kleene ou le calcul lambda (je comprends). que le premier n’est apparu que plus tard et que le dernier n’était pas conçu à l’origine comme un modèle de calcul, mais il montre que des alternatives existent depuis le début).

Tout ce à quoi je peux penser, c'est que le modèle MT représente plus fidèlement les ordinateurs que nous avons réellement que ses alternatives. Est-ce la seule raison?

Cela semble être vrai dans le contexte de (certains domaines de) l'informatique mais pas en général.

Une des raisons a à voir avec la thèse de l'Église. La raison principale en est que certains experts, comme Godel, ne pensaient pas que les arguments selon lesquels les modèles de calcul précédents / autres traduisent exactement le concept intuitif de calcul étaient convaincants. Il y a divers arguments, Church en a eu, mais ils n'ont pas convaincu Godel. D'autre part l'analyse de Turing a été convaincant pour Godel il a été accepté comme le modèle de calcul efficace. Les équivalences entre différents modèles sont prouvées plus tard (je pense par Kleene).

La seconde raison est technique et un développement ultérieur lié à l’étude de la théorie de la complexité. Définir les mesures de complexité telles que le temps, l'espace et le non déterminisme semble être plus facile avec les machines de Turing qu'avec d'autres modèles tels que les fonctions -calculus et -recursive.$\lambda$$\mu$

Par ailleurs, les fonctions -recursive étaient et sont toujours utilisées comme principal moyen de définir la calculabilité dans les livres de théorie de la logique et de la calculabilité. Ils sont plus faciles à utiliser lorsque l’on se soucie uniquement de l’efficacité et non de la complexité. Le livre de Kleene "Metamathematics" a beaucoup influencé ce développement. De plus, -calculus semble être plus courant dans l'informatique de type CMU / européenne, comme les langages de programmation et la théorie des types. Certains auteurs préfèrent les modèles RAM et Register Machine. (Il me semble que, pour une raison quelconque, les Américains ont adopté le modèle sémantique de Turing et les Européens ont adopté le modèle syntaxique de Church, Chruch était américain et Turing britannique. C’est une opinion / observation personnelle et d’autres ont un point de vue différent.$\mu$$\lambda$. Voir également ces articles de Viggo Stoltenberg-Hansen et John V. Tucker I , II .)

Quelques ressources pour en savoir plus:

Robert I. Soare a rédigé plusieurs articles sur l'historique de ces développements. Personnellement, j'aime bien celui du Handbook of Computability Theory. vous pouvez trouver plus en vérifiant les références dans cet article.

Une autre bonne ressource est l'article de Neil Immerman sur la calculabilité sur SEP (voir également l'article de Church-Turing Thesis de B. Jack Copeland).

Les œuvres rassemblées par Godel contiennent de nombreuses informations sur ses vues. Les introductions de ses articles sont particulièrement bien écrites.

" Metamathematics " de Kleene est un très bon livre.

Enfin, si vous n'êtes toujours pas satisfait, vérifiez les archives de la liste de diffusion FOM , et si vous ne trouvez pas de réponse dans les archives, envoyez un e-mail à la liste de diffusion.

J'aimerais affaiblir l'affirmation selon laquelle les MT sont le modèle de calcul principal, ou du moins, pointent vers une autre dimension de la question. Il est clair que les technologies de l’information sont dominantes dans les parties de la science informatique plus complexes et axées sur les algorithmes, mais dans la théorie et la pratique du langage de programmation, elles ne sont pas particulièrement dominantes. Il y a diverses raisons à cela, mais la plus importante est peut-être que les MT ou les programmes qui y sont exécutés (contrairement aux calculs lambda ou aux calculs de processus) ne sont pas construits de manière algébrique. Cela rend difficile le développement de théories de types, qui ont été le pilier de la théorie du langage de programmation.

L'un des avantages des machines Turing est qu'elles fonctionnent sur des chaînes plutôt que sur des nombres naturels ou des termes lambda, car l'entrée et la sortie de nombreux problèmes peuvent naturellement être formulées en tant que chaînes. Je ne sais pas si cela compte comme une raison «historique» ou non.

Outre le fait que les machines de Turing constituent un modèle convaincant de calcul papier-plume (la «notion intuitive de calcul»), je pense qu'elles possèdent une série de fonctionnalités souvent utiles, en particulier pour prouver des théorèmes à leur sujet:

• ils sont faciles à décrire formellement et ont une sémantique opérationnelle simple;
• il est facile de donner une définition concrète de leur complexité temporelle et spatiale;
• des modèles plus réalistes (et complexes) d'ordinateurs électroniques, tels que des machines à accès aléatoire, peuvent être simulés par les mémoires de traduction avec une surcharge polynomiale, et inversement.

Ce fut le premier à avoir un impact et a donc été établi, en particulier dans la théorie de la complexité. C'est une raison faible, mais les gens travaillent de cette façon. Nous travaillons d'abord sur d'anciens problèmes ouverts au lieu d'en déclarer de nouveaux.