https:\/\/www.astro.puc.cl\/~rparra\/tools\/PAPERS\/turing_1936.pdf<\/a><\/p>\nSUR LES NOMBRES CALCULABLES AVEC APPLICATION AU PROBLEME DE RESOLUTION<\/p>\n
A.M. TURING<\/p>\n
[Re\u00e7u le 28 mai 1936 – Lu le 12 novembre 1936]<\/p>\n
Les nombres \u00ab calculables \u00bb peuvent \u00eatre bri\u00e8vement d\u00e9crits comme des nombres r\u00e9els dont les expressions sous forme de fractions d\u00e9cimales sont calculables d’un nombre fini de fa\u00e7ons. Bien qu’\u00e0 premi\u00e8re vue cet article traite les nombres comme calculables, il est presque aussi simple de d\u00e9finir et d’explorer les fonctions calculables d’une variable enti\u00e8re, d’une variable r\u00e9elle, d’une variable calculable, de pr\u00e9dicats calculables, etc. Cependant, les probl\u00e8mes fondamentaux associ\u00e9s \u00e0 ces objets calculables sont les m\u00eames dans chaque cas. Pour une consid\u00e9ration d\u00e9taill\u00e9e, j’ai choisi les nombres calculables comme objet calculable car la m\u00e9thode pour les consid\u00e9rer est la moins lourde. J’esp\u00e8re d\u00e9crire bient\u00f4t la relation entre les nombres calculables et les fonctions calculables, etc. Parall\u00e8lement, des recherches seront men\u00e9es dans le domaine de la th\u00e9orie des fonctions d’une variable r\u00e9elle exprim\u00e9e en termes de nombres calculables. Selon ma d\u00e9finition, un nombre r\u00e9el est calculable si sa repr\u00e9sentation d\u00e9cimale peut \u00eatre \u00e9crite par une machine.<\/p>\n
Aux paragraphes 9 et 10, je donne quelques arguments pour montrer que les nombres calculables incluent tous les nombres qui sont naturellement consid\u00e9r\u00e9s comme calculables. En particulier, je montre que certaines grandes classes de nombres sont calculables. Ils comprennent, par exemple, les parties r\u00e9elles de tous les nombres alg\u00e9briques, les parties r\u00e9elles des z\u00e9ros des fonctions de Bessel, les nombres \u03c0, e et autres. Cependant, les nombres calculables n’incluent pas tous les nombres d\u00e9finissables, comme en t\u00e9moigne l’exemple suivant d’un nombre d\u00e9finissable qui n’est pas calculable.<\/p>\n
Bien que la classe des nombres calculables soit tr\u00e8s vaste et similaire \u00e0 bien des \u00e9gards \u00e0 la classe des nombres r\u00e9els, elle reste n\u00e9anmoins d\u00e9nombrable. Au \u00a78, je consid\u00e8re certains arguments qui semblent soutenir le contraire. Lorsqu\u2019un de ces arguments est correctement appliqu\u00e9, on en tire des conclusions qui, \u00e0 premi\u00e8re vue, sont similaires \u00e0 celles de G\u00f6del*. Ces r\u00e9sultats ont des applications extr\u00eamement importantes. En particulier, comme indiqu\u00e9 ci-dessous (\u00a711), le probl\u00e8me de r\u00e9solution ne peut pas avoir de solution.<\/p>\n
Dans un article r\u00e9cent, Alonzo Church a introduit l’id\u00e9e de \u00ab calculabilit\u00e9 efficace \u00bb, qui est \u00e9quivalente \u00e0 mon id\u00e9e de \u00ab calculabilit\u00e9 \u00bb mais a une d\u00e9finition compl\u00e8tement diff\u00e9rente. Church arrive \u00e9galement \u00e0 des conclusions similaires concernant le probl\u00e8me de la r\u00e9solution. La preuve de l\u2019\u00e9quivalence de \u00ab calculabilit\u00e9 \u00bb et \u00ab effectivement calculable \u00bb est pr\u00e9sent\u00e9e en annexe de cet article.<\/p>\n
1. Ordinateurs<\/p>\n
Nous avons d\u00e9j\u00e0 dit que les nombres calculables sont les nombres dont les d\u00e9cimales sont d\u00e9nombrables par des moyens finis. Une d\u00e9finition plus claire est n\u00e9cessaire ici. Cet article ne tentera pas r\u00e9ellement de justifier les d\u00e9finitions donn\u00e9es ici avant d’arriver au \u00a79. Pour l\u2019instant, je noterai simplement que la justification (logique) (de cela) est que la m\u00e9moire humaine est, par n\u00e9cessit\u00e9, limit\u00e9e.<\/p>\n
Comparons une personne en train de calculer un nombre r\u00e9el avec une machine capable de remplir seulement un nombre fini de conditions q1, q2, …, qR ; Appelons ces conditions \u00ab m-configurations \u00bb. Cette machine (c’est-\u00e0-dire ainsi d\u00e9finie) est \u00e9quip\u00e9e d’un \u00ab ruban \u00bb (analogue au papier). Cette courroie traversant la machine est divis\u00e9e en tron\u00e7ons. Appelons-les \u00ab carr\u00e9s \u00bb. Chacun de ces carr\u00e9s peut contenir une sorte de \u00ab symbole \u00bb. \u00c0 tout moment, il n\u2019existe qu\u2019un seul carr\u00e9 de ce type, disons le i\u00e8me, contenant le symbole qui se trouve \u00ab dans cette machine \u00bb. Appelons un tel carr\u00e9 un \u00ab symbole num\u00e9ris\u00e9 \u00bb. Un “caract\u00e8re scann\u00e9” est le seul caract\u00e8re dont la machine est, pour ainsi dire, “directement consciente”. Cependant, en modifiant sa configuration m, la machine peut effectivement m\u00e9moriser certains des caract\u00e8res qu’elle a “vus” (num\u00e9ris\u00e9s) pr\u00e9c\u00e9demment. Le comportement possible de la machine \u00e0 tout moment est d\u00e9termin\u00e9 par la configuration m qn et le symbole scann\u00e9***. Appelons cette paire de symboles qn, \u00ab configuration \u00bb. La configuration ainsi d\u00e9sign\u00e9e d\u00e9termine le comportement possible d’une machine donn\u00e9e. Dans certaines de ces configurations dans lesquelles le carr\u00e9 scann\u00e9 est vide (c’est-\u00e0-dire ne contient pas de caract\u00e8re), la machine \u00e9crit un nouveau caract\u00e8re sur le carr\u00e9 scann\u00e9, et dans d’autres de ces configurations, elle efface le caract\u00e8re scann\u00e9. Cette machine est \u00e9galement capable de se d\u00e9placer pour scanner une autre case, mais de cette mani\u00e8re elle ne peut se d\u00e9placer que vers la case adjacente \u00e0 droite ou \u00e0 gauche. En plus de chacune de ces op\u00e9rations, la configuration m de la machine peut \u00eatre modifi\u00e9e. Dans ce cas, certains des caract\u00e8res \u00e9crits formeront une s\u00e9quence de chiffres, qui constitue la partie d\u00e9cimale du nombre r\u00e9el calcul\u00e9. Le reste ne sera que des notes inexactes destin\u00e9es \u00e0 \u00ab\u00a0aider la m\u00e9moire\u00a0\u00bb. Dans ce cas, seules les marques inexactes mentionn\u00e9es ci-dessus pourront \u00eatre effac\u00e9es.<\/p>\n
J’affirme que les op\u00e9rations consid\u00e9r\u00e9es ici incluent toutes les op\u00e9rations utilis\u00e9es dans le calcul. La justification de cette affirmation est plus facile \u00e0 comprendre pour le lecteur qui a une compr\u00e9hension de la th\u00e9orie des machines. Par cons\u00e9quent, dans la section suivante, je continuerai \u00e0 d\u00e9velopper la th\u00e9orie en question, bas\u00e9e sur une compr\u00e9hension de la signification des termes \u00ab machine \u00bb, \u00ab bande \u00bb, \u00ab scann\u00e9 \u00bb, etc.<\/p>\n
*G\u00f6del \u00ab Sur les phrases formellement ind\u00e9cidables des Principia Mathematics (publi\u00e9 par Whitehead et Russell en 1910, 1912 et 1913) et des syst\u00e8mes associ\u00e9s, partie I \u00bb, Journal of Mathematics. Physique, bulletin mensuel en allemand n\u00b0 38 (pour 1931, pp. 173-198.
\n** Alonzo Church, \u00ab Un probl\u00e8me ind\u00e9cidable dans la th\u00e9orie \u00e9l\u00e9mentaire des nombres \u00bb, American J. of Math., n\u00b0 58 (1936), pp. 345-363.
\n*** Alonzo Church, \u00ab Une note sur le probl\u00e8me de r\u00e9solution \u00bb, J. of Symbolic Logic, n\u00b0 1 (1936), pp. 40-41<\/p>\n","protected":false},"excerpt":{"rendered":"
Je pr\u00e9sente \u00e0 votre attention une traduction des premi\u00e8res pages de l’article d’Alan Turing \u00ab SUR LES NUM\u00c9ROS COMPUTABLES AVEC UNE APPLICATION AU PROBL\u00c8ME DE R\u00c9SOLUTION \u00bb de 1936. Les premiers chapitres contiennent une description des ordinateurs, qui deviendront plus tard la base de l’informatique moderne. La traduction compl\u00e8te de l’article et l’explication peuvent \u00eatre […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[],"class_list":["post-70","post","type-post","status-publish","format-standard","hentry","category-notes"],"translation":{"provider":"WPGlobus","version":"3.0.2","language":"fr","enabled_languages":["en","ru","zh","de","ja","fr","es","pt","hi"],"languages":{"en":{"title":true,"content":true,"excerpt":false},"ru":{"title":true,"content":true,"excerpt":false},"zh":{"title":true,"content":true,"excerpt":false},"de":{"title":true,"content":true,"excerpt":false},"ja":{"title":true,"content":true,"excerpt":false},"fr":{"title":true,"content":true,"excerpt":false},"es":{"title":false,"content":false,"excerpt":false},"pt":{"title":true,"content":true,"excerpt":false},"hi":{"title":true,"content":true,"excerpt":false}}},"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/70","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/comments?post=70"}],"version-history":[{"count":1,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/70\/revisions"}],"predecessor-version":[{"id":73,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/70\/revisions\/73"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/media?parent=70"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/categories?post=70"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/tags?post=70"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}