Author Archives: demensdeum

Je présente à votre attention une traduction des premières pages de l’article d’Alan Turing – « SUR LES NUMÉROS INFORMATIQUES AVEC APPLICATION AU PROBLÈME DE RÉSOLUTION » 1936. Les premiers chapitres contiennent une description des ordinateurs, qui sont devenus plus tard la base de l’informatique moderne.

La traduction complète de l’article et l’explication peuvent être lues dans le livre du vulgarisateur américain Charles Petzold, intitulé « Reading Turing ». Un voyage à travers l’article historique de Turing sur la calculabilité et les machines de Turing&#8221 ; (ISBN 978-5-97060-231-7, 978-0-470-22905-7)

Article original :
https://www.astro.puc.cl/~rparra/tools/PAPERS/turing_1936.pdf

—

À PROPOS DES NOMBRES CALCULABLES AVEC APPLICATION AU PROBLÈME DE RÉSOLUTION

A. M. TURING

[Reçu le 28 mai 1936 – Lu le 12 novembre 1936]

Les nombres calculables peuvent être brièvement décrits comme des nombres réels dont les expressions sous forme de fractions décimales sont calculables d’un nombre fini de façons. Bien qu’à première vue cet article traite les nombres comme calculables, il est presque aussi simple de définir et d’explorer les fonctions calculables d’une variable entière, d’une variable réelle, d’une variable calculable, de prédicats calculables, etc. Cependant, les problèmes fondamentaux associés à ces objets calculables sont les mêmes dans chaque cas. Pour une considération détaillée, j’ai choisi les nombres calculables comme objet calculable car la méthode pour les considérer est la moins lourde. J’espère décrire bientôt la relation entre les nombres calculables et les fonctions calculables, etc. Parallèlement, des recherches seront menées dans le domaine de la théorie des fonctions d’une variable réelle exprimée en termes de nombres calculables. Selon ma définition, un nombre réel est calculable si sa représentation sous forme de fraction décimale peut être écrite par une machine.

Dans les paragraphes 9 et 10, je donne quelques arguments pour montrer que les nombres calculables incluent tous les nombres qui sont naturellement considérés comme calculables. En particulier, je montre que certaines grandes classes de nombres sont calculables. Ils comprennent, par exemple, les parties réelles de tous les nombres algébriques, les parties réelles des zéros des fonctions de Bessel, les nombres π, e et autres. Cependant, les nombres calculables n’incluent pas tous les nombres définissables, comme en témoigne l’exemple suivant d’un nombre définissable qui n’est pas calculable.

Bien que la classe des nombres calculables soit très vaste et similaire à bien des égards à la classe des nombres réels, elle reste néanmoins dénombrable. Au §8, je considère certains arguments qui semblent soutenir le contraire. Lorsqu’un de ces arguments est correctement appliqué, on en tire des conclusions qui, à première vue, sont similaires à celles de Gödel*. Ces résultats ont des applications extrêmement importantes. En particulier, comme indiqué ci-dessous (§11), le problème de résolution ne peut pas être résolu.

Dans son récent article, Alonzo Church** a introduit l’idée de « calculabilité efficace », qui est équivalente à mon idée de « calculabilité » mais a une définition complètement différente. Church arrive également à des conclusions similaires concernant le problème de la résolution. La preuve de l’équivalence de la « calculabilité » et de la « capacité à être effectivement comptée » est présentée en annexe de cet article.

1. Ordinateurs

Nous avons déjà dit que les nombres calculables sont les nombres dont les décimales sont dénombrables par des moyens finis. Une définition plus claire est nécessaire ici. Cet article ne tentera pas réellement de justifier les définitions données ici avant d’arriver au §9. Pour l’instant, je noterai simplement que la justification (logique) (de cela) est que la mémoire humaine est, par nécessité, limitée.

Comparons une personne en train de calculer un nombre réel avec une machine capable de remplir seulement un nombre fini de conditions q1, q2, …, qR ; Appelons ces conditions « m-configurations ». Cette machine (c’est-à-dire ainsi définie) est équipée d’un « ruban » (analogue au papier). Cette courroie traversant la machine est divisée en tronçons. Appelons-les « carrés ». Chacun de ces carrés peut contenir une sorte de « symbole ». À tout moment, il n’existe qu’un seul carré de ce type, disons le ième, contenant le symbole qui se trouve « dans cette machine ». Appelons un tel carré un « symbole numérisé ». Un “caractère scanné” est le seul caractère dont la machine est, pour ainsi dire, “directement consciente”. Cependant, en modifiant sa configuration m, la machine peut effectivement mémoriser certains des caractères qu’elle a “vus” (numérisés) précédemment. Le comportement possible de la machine à tout moment est déterminé par la configuration m qn et le symbole scanné***. Appelons cette paire de symboles qn, « configuration ». La configuration ainsi désignée détermine le comportement possible d’une machine donnée. Dans certaines de ces configurations dans lesquelles le carré scanné est vide (c’est-à-dire ne contient pas de caractère), la machine écrit un nouveau caractère sur le carré scanné, et dans d’autres de ces configurations, elle efface le caractère scanné. Cette machine est également capable de se déplacer pour scanner une autre case, mais de cette manière elle ne peut se déplacer que vers la case adjacente à droite ou à gauche. En plus de chacune de ces opérations, la configuration m de la machine peut être modifiée. Dans ce cas, certains des caractères écrits formeront une séquence de chiffres, qui constitue la partie décimale du nombre réel calculé. Le reste ne sera que des notes inexactes destinées à « aider la mémoire ». Dans ce cas, seules les marques inexactes mentionnées ci-dessus pourront être effacées.

J’affirme que les opérations considérées ici incluent toutes les opérations utilisées dans le calcul. La justification de cette affirmation est plus facile à comprendre pour le lecteur qui comprend la théorie des machines. Par conséquent, dans la section suivante, je continuerai à développer la théorie en question, basée sur une compréhension de la signification des termes « machine », « bande », « scanné », etc.

*Gödel « Sur les phrases formellement indécidables des Principia Mathematics (publié par Whitehead et Russell en 1910, 1912 et 1913) et des systèmes associés, partie I », Journal of Mathematics. Physique, bulletin mensuel en allemand n° 38 (pour 1931, pp. 173-198.
** Alonzo Church, « An Undecidable Problem in Elementary Number Theory », American J. of Math., n° 58 (1936), pp. 345-363.
*** Alonzo Church, « Une note sur le problème de la résolution », J. of Symbolic Logic, n° 1 (1936), pp. 40-41