Machine de Turing : traduction des textes fondateurs

La Machine de Turing : les textes fondateurs

La calculabilité des nombres et son application au problème de la décision [Entscheidungsproblem] (A. M. Turing)

Traduction Dominique Bonnaud

L’immersion dans les textes fondateurs est un exercice fortement conseillé. Au même titre que La richesse des Nations d’Adam Smith (1776), ou De l’origine des espèces de Charles Darwin (1859), La calculabilité des nombres et son application au problème de la décision d’Alan Turing (1937), est l’un de ces textes. D’un côté, deux ouvrages diffusés en direction d’un public relativement large, de l’autre, un simple article réservé à des spécialistes, mais l’impact et l’importance dans l’histoire des idées et l’histoire tout court sont les mêmes. Tout commence dans l’été 1900, à Paris, où l’Exposition universelle bat son plein, lors du 2e Congrès international des mathématiciens, lorsque David Hilbert (1862-1943), professeur à l’université allemande de Göttingen, souvent considéré comme un des plus grands mathématiciens du 20e siècle, en tout cas la plus importante personnalité de cette discipline en son temps, lance le programme des recherches du siècle à venir en recensant 23 grands problèmes ouverts dont les réponses sont censées faire progresser la discipline. Ce programme est en effet à l’origine de nombreux travaux et réflexions, dont ceux de Turing.

Problèmes et choix de traduction

C’est après avoir traduit les articles de Turing que j’ai pris connaissance de la traduction de Julien Basch (in Turing/Girard, La machine de Turing, Seuil, Points Sciences, 1995). La prise en compte des corrections que cette dernière présente ou apporte au texte original de Turing m’est alors apparue indispensable : celles de la section 7 (Description détaillée de la machine universelle) par le mathématicien américain d’origine polonaise Emil Post (« Recursive Unsolvability of a Problem of Thue », The Journal of Symbolic Logic, vol. 12, 1947, pp. 1-11), et celles de la démonstration du théorème (iii’) de la section 10. Ces corrections sont reportées directement, en rouge pour les distinguer, dans la traduction proposée ci-dessous. Quant aux corrections de la section 11 (Application au problème de la décision) émanant de Turing lui-même sur les indications du mathématicien suisse Paul Bernays, spécialiste de logique mathématique longtemps assistant et collaborateur de David Hilbert, dans l’erratum à son article original, j’ai adopté le choix de la traduction Basch en les incorporant également directement sans distinction de couleur.

Pour un texte scientifique où la précision de la terminologie est un élément essentiel, il s’est également, et rapidement, avéré que la première version de notre traduction devait être révisée en tenant compte de cette terminologie spécifique. Exemple : formula ou quantor. Après avoir traduit le premier terme par « énoncé », et fort embarrassé pour trouver un équivalent français au second, une rapide initiation à la logique formelle m’a permis de réaliser que tous deux ont une acception précise dans cette discipline, et qu’il n’est pas possible de les traduire autrement que par « formule » et « quantificateur ». De même pour diagonal process, que j’avais d’abord malencontreusement traduit par « procédure oblique », alors que l’argument diagonal de Cantor ne laisse aucun doute, et qu’il faut donc traduire par « procédé diagonal » comme le fait d’ailleurs Basch.

Mais, s’il est des choix de traduction impératifs, il en est d’autres facultatifs. En fait, certains choix sont souhaitables pour l’harmonisation des diverses traductions possibles et disponibles. Exemple de traduction facultative : le titre, « Théorie des nombres calculables, suivie d’une application… » (Basch), « La calculabilité des nombres et son application… » (Ma traduction). L’une et l’autre traduction sont possibles, et leur différence n’est pas susceptible de produire de la confusion et du contresens. Dans les deux cas, il est bien question des mêmes choses. Je n’avais donc aucune raison de modifier mon choix. Mais autre exemple, autre option : Circular and circle-free machines, que j’ai d’abord traduit par « machines circulaires et non-circulaires ». C’est un choix cohérent possible, mais j’ai finalement opté pour « cyclique » et « acyclique » de la traduction Basch, non seulement parce que cette dernière est bien meilleure, mais aussi dans un souci d’harmoniser le vocabulaire technique. De même pour choice machines, que Basch traduit par « machines à choix », mais que l’on pourrait tout aussi bien traduire, et peut-être mieux, par « machines à options » ou, en tenant compte du contexte et de la définition donnée par Turing lui-même, « machines partiellement déterministes ». Là encore, l’harmonisation et l’antériorité ont prévalu pour conserver la traduction « machines à choix ».

En revanche, j’ai suivi une autre voie pour traduire l’anglais determine. En effet, outre le sens primitif de « déterminer », il possède aussi, dans le contexte du problème de la décision abordé par Turing, le sens dérivé de « décider », determination étant le terme anglais utilisé pour « décision » au sens que lui a donné la discipline des mathématiques. Or, il m’a semblé que plusieurs occurrences de la traduction Basch négligent ce sens dérivé, pourtant d’une grande importance dans cet article. Sans écarter totalement le sens traditionnel, j’ai rétabli le sens dérivé pour toutes les occurrences susceptibles de s’y rapporter.

Traduction des lettres et symboles. Deux possibilités s’offrent au traducteur : garder les lettres utilisées par Turing, dont certaines sont en correspondance mnémonique avec des termes de la langue anglaise (par exemple R pour right, L pour left), ou les franciser comme le fait la traduction Basch qui transforme R en D pour droite, et L en G pour gauche, avec des effets en cascade sur les autres lettres utilisées. En revanche et avec sagesse, cette traduction n’est pas allée jusqu’à modifier les noms de fonctions, probables mnémoniques de termes anglais : fonction trouver, f = find ; fonction comparer, cp = compare ; fonction comparer-effacer, cpe = compare erase ; fonction configurer : con = configure ; fonction commencer : b = begin ; fonction simuler : sim = simulate ; fonction montrer : sh = show ; etc. Le choix d’adopter D et G pour R et L m’obligeant à modifier d’autres symboles, plutôt que de me singulariser ou de raffiner sans raison valable, outre les risques d’omission et d’erreur que représentent des modifications systématiques, la reproduction des mêmes transformations que celles de la traduction Basch est apparue comme la solution la plus raisonnable, avec l’avantage de ne pas dérouter le lecteur susceptible d’aborder l’une ou l’autre de ces traductions.

De même, j’ai suivi le choix judicieux de Basch en actualisant la notation de la logique formelle, légèrement différente à l’époque de Turing et de Gödel. C’est ainsi que le quantificateur (x) au sens de « pour tout x » s’écrit aujourd’hui <math>\forall </math> x, et & (le signe tironien dit esperluette ou commercial) le symbole conjonctif s’écrit désormais ˄, sans compter les risques de confusion, & étant maintenant utilisé dans la logique linéaire au sens de « avec ».

Tous les autres choix et différences sont personnels, purement stylistiques et, dans la mesure du possible, ne compromettent en rien le sens du texte.

Dominique BONNAUD

Chargé d’études documentaires

Canopé-CNDP Chasseneuil-du-Poitou

La calculabilité des nombres et son application au problème de la décision [Entscheidungsproblem<ref name="ftn1"> En allemand dans le texte. En logique mathématique, l’Entscheidungsproblem, ou problème de la décision, est le fait de déterminer de façon mécanique, par un algorithme, si un énoncé est un théorème de la logique égalitaire du premier ordre, c’est-à-dire s’il se dérive dans un système de déduction (voir système à la Hilbert, calcul des séquents, déduction naturelle), sans autres axiomes que ceux de l’égalité (note du traducteur).</ref>] (A. M. Turing)

Sources et versions de l’article original en ligne :

Alan Turing, « On Computable Numbers, with an Application to the Entscheidungsproblem », dans Proc. London Math. Soc., 2^e série, vol. 42, 1937, pp. 230-265.

http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

http://www.wolframscience.com/prizes/tm23/images/Turing.pdf

http://www.thocp.net/biographies/papers/turing_oncomputablenumbers_1936.pdf

(Reçu le 28 mai 1936- Lu le 12 novembre 1936)

On peut définir sommairement les nombres « calculables » comme les nombres réels qui, exprimés en décimales, sont calculables avec des moyens finis. Bien que le sujet de cet article soit ostensiblement les nombres calculables, il est pratiquement tout aussi facile de définir et d’étudier des fonctions calculables d’une variable entière ou d’une variable réelle ou calculable, des prédicats calculables, et ainsi de suite. Les enjeux fondamentaux inhérents sont, toutefois, les mêmes dans tous les cas, et mon choix de traiter plus particulièrement des nombres calculables se justifie par la technique la moins lourde que leur étude nécessite. J’espère donner bientôt un compte-rendu sur les relations entre nombres calculables, fonctions, etc. Il comprendra un développement de la théorie des fonctions d’une variable réelle exprimée en termes de nombres calculables. Conformément à ma définition, un nombre est dit calculable si sa partie décimale peut être écrite par une machine.

En §§ 9, 10 je présente quelques arguments dans l’intention de montrer que les nombres calculables comprennent tous les nombres qui pourraient intrinsèquement être considérés comme calculables. En particulier, je démontre que certaines grandes catégories de nombres sont calculables. Elles comprennent, par exemple, les parties réelles de tous les nombres algébriques et des zéros des fonctions de Bessel, les nombres π, e, etc. Les nombres calculables ne comprennent cependant pas tous les nombres définissables, et l’on présente un exemple d’un nombre définissable qui n’est pas calculable.

Bien que l’ensemble des nombres calculables soit immense et, à bien des égards, comparable à celui des nombres réels, il est néanmoins dénombrable. J’examine en § 8 certains arguments qui sembleraient prouver le contraire. Par l’utilisation judicieuse de l’un de ces arguments, l’on aboutit à des conclusions qui sont en apparence les mêmes que celles de Gödel<ref name="ftn2"> Kurt Gödel, « Über formal unentscheidhare Sätze dze Principia Mathematica und verwandter Systeme, I », Monatshefte Math. Phys., 38, 1931, pp. 173-198 [« Sur les propositions formellement indécidables des Principia Mathematica et des systèmes apparentés, I », trad. fr. de J.-B. Scherrer, in Jean-Yves Girard, Le Théorème de Gödel, Seuil, Points Sciences, 1989. Note du traducteur].</ref>. Ces résultats [231] ont d’importantes applications. En particulier, il est montré (§ 11) que le problème de la décision (Entscheidungsproblem) d’Hilbert ne peut avoir de solution.

Dans un article récent, Alonzo Church<ref name="ftn3"> Alonzo Church, « An unsolvable problem of elementary number theory », American J. of Math., 58, 1936, pp. 345-363.</ref> a introduit la notion de « calculabilité effective », équivalente à ma « calculabilité (computabilité) », mais définie de façon très différente. Church parvient à des conclusions similaires sur le problème de la décision<ref name="ftn4"> Alonzo Church, « A note on the Entscheidungsproblem », Journal of Symbolic Logic, I, 1936, pp. 40-41. </ref>. La démonstration de l’équivalence entre « ma calculabilité » et la « calculabilité effective » de Church est esquissée dans un appendice au présent article.

1 Machines à calculer.

Nous avons dit que les nombres calculables sont ceux dont les décimales sont calculables avec des moyens finis, ce qui réclame une définition un peu plus explicite, mais aucune véritable tentative pour justifier les définitions présentées ne sera tentée avant § 9. Dans l’immédiat, je me contenterai de dire que cette justification repose sur le fait que la mémoire humaine est nécessairement limitée.

Nous pouvons comparer un homme en train de calculer un nombre réel à une machine susceptible seulement de passer par un nombre fini d’états, q₁, q₂, …,q_n que l’on appellera « m-configurations ». La machine est équipée d’une « bande » (l’analogue du papier), qui la parcourt et est divisée en sections (appelées « cases »), chacune à même de porter un « symbole ». À chaque instant, il n’y a « dans la machine » qu’une seule case, dite la case r contenant le symbole S(r). Nous pouvons l’appeler la « case inspectée », et le symbole sur cette case le « symbole inspecté ». Ce dernier est le seul et l’unique dont la machine est, pour ainsi dire, « directement consciente ». Cependant, en modifiant sa m-configuration, la machine peut effectivement garder la mémoire de quelques-uns des symboles qu’elle a « vus » (inspectés) auparavant. À chaque instant, le fonctionnement possible de la machine est déterminé par la m-configuration q_n et le symbole inspecté S(r). On appellera ce binôme (q_n, S(r)) la « configuration », et c’est elle qui conditionne l’évolution possible de la machine : dans certaines des configurations où la case inspectée est blanche (i.e. ne porte aucun symbole), la machine inscrit un nouveau symbole dans la case ; dans d’autres, elle efface le symbole inspecté. Dans son parcours, la machine peut aussi changer de case, mais seulement en glissant d’un seul rang à droite ou à gauche de la case inspectée. Enfin, la m-configuration peut être modifiée. Certains des symboles inscrits [232] formeront la suite de chiffres formant la partie décimale du nombre réel calculé. Les autres ne sont que des marques qui servent d’« aide-mémoire ». Seules ces dernières serviront à effacer.

À mon sens, ces opérations englobent toutes celles utilisées dans le calcul de la valeur d’un nombre. Il sera plus facile de justifier ce point de vue discutable lorsque le lecteur sera familiarisé avec la théorie des machines. Par conséquent, dans la section suivante, je poursuis le développement de cette théorie en supposant compris ce que l’on entend par « machine », « bande », « case inspectée », etc.

2 Définitions.

Machines automatiques.

Si, à chaque étape, le fonctionnement d’une machine (dans le sens de § 1) est entièrement déterminé par sa configuration, nous parlerons de « machine automatique » (ou a-machine).

Dans certains cas, il nous faudrait utiliser des machines (machines à choix ou c-machines<ref name="ftn5"> On pourrait dire aussi « à options » ou, en tenant compte de la définition qui en est donnée, partiellement déterministes (Note du traducteur).</ref>) dont le fonctionnement n’est que partiellement déterminé par sa configuration (d’où l’utilisation du mot « possible » en § 1). Lorsqu’une telle machine atteint l’une de ces configurations ambiguës, elle ne peut poursuivre sa tâche jusqu’à ce qu’un opérateur extérieur ait effectué un choix arbitraire. Nous serions dans le cas d’être obligés d’utiliser ces machines pour opérer sur des systèmes axiomatiques. Dans cet article, je ne traite que de machines automatiques et, par conséquent, j’omettrai souvent le préfixe a-.

Machines à calculer.

On appellera machine à calculer une a-machine qui imprime deux familles de symboles, dont ceux de la première (appelés chiffres) se limitent aux chiffres 0 et 1 (la deuxième famille comprenant tous les autres). Si la machine est équipée d’une bande vierge et se met en route à partir de sa bonne m-configuration initiale, on appellera suite calculée par la machine, la suite de symboles, tous de la première famille, qu’elle imprime, et nombre calculé par la machine, le nombre réel dont la notation décimale binaire est obtenue en préfixant cette suite d’une virgule.

À chaque étape du fonctionnement de la machine, on dira que le numéro de la case inspectée, la suite complète des symboles sur la bande et la m-configuration, décrivent la configuration complète de cette étape. On appellera transitions de la machine ses modifications et celles de la bande d’une configuration complète à la suivante.

[233] Machines cycliques et acycliques.

On appellera cyclique une machine à calculer qui n’inscrit jamais qu’un nombre fini de symboles de la première famille. Dans le cas contraire, elle est dite acyclique.

Une machine sera cyclique si elle atteint une configuration à partir de laquelle plus aucun mouvement n’est possible, ou bien si elle continue à fonctionner, et éventuellement à imprimer des symboles de la deuxième famille, mais ne peut plus du tout imprimer de symboles de la première. Le sens du terme « cyclique » sera expliqué en § 8.

Suites et nombres calculables.

On dit qu’une suite est calculable s’il existe une machine acyclique pouvant la calculer. Un nombre est calculable s’il existe une machine acyclique qui calcule sa partie décimale.

Pour éviter toute confusion, nous parlerons plus souvent de suites calculables que de nombres calculables.

3. Exemples de machines à calculer.

I Pour calculer la suite 010101… on peut construire une machine à quatre m-configurations, « b », « c », « e », « f », et capable d’imprimer les symboles « 0 » et « 1 ». Le fonctionnement de cette machine est décrit dans le tableau suivant, dans lequel les signes de la colonne « opérations » signifient :

« D » : « la machine se déplace de façon à inspecter la case immédiatement à droite de celle qu’elle inspectait précédemment ».

« G » : même chose à gauche.

« E » : « le symbole inspecté est effacé ».

« I » : « impression » du symbole dans la case inspectée.

Ce tableau (ainsi que tous ceux qui suivent) doit être ainsi compris : pour une configuration décrite dans les deux premières colonnes, la machine suit dans l’ordre les instructions de la troisième, puis se place dans la m-configuration décrite dans la dernière. Lorsque la deuxième colonne est vide, cela signifie que le fonctionnement exprimé dans les troisième et quatrième colonnes s’applique quel que soit le symbole ou l’absence de symbole. La m-configuration initiale de la machine est b et la bande est vierge.

ConfigurationFonctionnement

m-config.symboleopérationsm-config. finale

baucunI0, Dc

caucunDe

eaucunI1, Df

faucunDb

[234] Si, contrairement aux définitions de § 1, nous autorisons, dans la colonne des opérations, les instructions D et G à apparaître plus d’une fois par ligne, nous pouvons simplifier considérablement le tableau.

m-config.symboleopérationsm-config. finale

aucunI0b

b ~0D, D, I1b

1D, D, I0b

II. Un exemple légèrement plus compliqué se trouve dans la possibilité, pour calculer la suite 001011011101111011111…, de construire une machine à cinq m-configurations, « o », « q », « p », « f », « b » et pouvant imprimer les symboles « ə », « x », « 0 » et « 1 ». Les trois premiers symboles inscrits sur la bande seront « əə0 », et les chiffres suivants dans une case sur deux. Sur les cases intermédiaires nous n’imprimons invariablement que des « x ». Ces « x » nous servent à « marquer l’emplacement » et sont effacés dès que nous n’en avons plus besoin. Par ailleurs, nous nous arrangeons pour qu’il n’y ait aucun blanc dans la suite de chiffres sur les cases alternées.

ConfigurationFonctionnement

m-config.symboleopérationsm-config. finale

bIə, D, Iə, D, I0, D, D, I0, G, Go

1D, Ix, G, G, Go

o ~

0q

n’importe lequel (0 ou 1)D, Dq

q ~

aucunI1, Gp

xE, Dq

p ~əDf

aucunG, Gp

n’importe lequelD, Df

f ~

aucunI0, G, Go

Un tableau des premières configurations complètes de la machine est présenté ci-dessous pour illustrer son fonctionnement. Celles-ci sont décrites en notant la suite de symboles présents sur la bande, [235], avec la m-configuration inscrite sous le symbole inspecté. Les configurations complètes successives sont séparées par des doubles points.

_  : ə ə 0 _ 0 : ə ə 0 _ 0 : ə ə 0 _ 0 : ə ə 0 _0 _  : ə ə 0 _ 0 _ 1 : ə ə 0 _ 0 _ 1 : ə ə 0 _ 0 _ 1 :

boqqqppp

ə ə 0 _ 0 _ 1 : ə ə 0 _ 0 _ 1 : ə ə 0 _ 0 _ 1 : ə ə 0 _ 0 _ 1 _ _  : ə ə 0 _ 0 _ 1 _ 0 :

ffffo

ə ə 0 _ 0 _ 1 x 0 : … .

o

On pourrait aussi écrire ce tableau en inscrivant la m-configuration dans un espace créé immédiatement à gauche du symbole inspecté.

b _  : ə ə o 0 _ 0 : ə ə q 0 _ 0 : … .(C)

Cette forme est moins facile à suivre, mais nous l’utiliserons par la suite à des fins théoriques.

La convention d’inscrire les chiffres uniquement une case sur deux est très pratique, et je l’utiliserai constamment. J’appellerai cette seule suite de cases les C-cases, et l’autre suite de cases intermédiaires les E-cases. Les symboles des E-cases seront les seuls à pouvoir être effacés. Ceux des C-cases forment une suite continue sans aucun blanc jusqu’à la fin. Il n’est pas nécessaire d’avoir plus d’une E-case entre deux C-cases : on peut satisfaire un besoin apparent d’E-cases supplémentaires par une variété suffisamment riche de symboles imprimables sur les E-cases existantes. Si un symbole ß se trouve dans une C-case S, et un symbole α dans l’E-case suivante à droite de S, on dira alors de S et de ß qu’ils sont marqués avec α. On appellera marquage de ß (ou de S) avec α la procédure d’impression de α sur cette case à droite de S.

4. Tableaux abrégés.

Il existe certains types de traitements utilisés dans presque toutes les machines et, dans certaines machines, ils le sont à de nombreuses reprises. Ces traitements comprennent la reproduction et la comparaison de suites de symboles, l’effacement de tous les symboles d’une forme donnée, etc. Là où de tels traitements sont effectués, nous pouvons simplifier considérablement les tableaux des m-configurations en utilisant des « tableaux types », où apparaissent des lettres majuscules et des lettres minuscules grecques, qui sont les unes et les autres des « variables ». En remplaçant totalement chaque lettre majuscule par une m-configuration [236] et chaque minuscule grecque par un symbole, nous obtenons le tableau pour une m-configuration.

Il faut considérer que les tableaux types ne sont rien de plus que des abréviations : ils ne sont pas essentiels. Du moment que le lecteur comprend comment obtenir les tableaux complets à partir des tableaux types, il n’est pas nécessaire d’en donner des définitions exactes.

Prenons un exemple [fonction trouver, f = find] :

m-config.symbolefonctionnementm-configuration finale

əGf₁(E, B, α) À partir de la m-configuration f(E, B, α) la machine trouve le symbole α qui est le plus à gauche (le « premier α ») et la m-configuration devient E. S’il n’y a pas d’α la m-configuration devient B.

f(E, B, α) ~ non əGf(E, B, α)

aucunGf(E, B, α)

αE

f₁(E, B, α) ~non αDf₁(E, B, α)

aucunDf₂(E, B, α)

αE

f₂(E, B, α) ~non αDf₁(E, B, α)

aucunDB

S’il nous fallait remplacer totalement les variables par des m-configurations et des symboles, par exemple E par q, B par r, et α par x, nous obtiendrions un tableau complet pour la m-configuration f(q, r, x). On appellera f une « fonction de m-configuration » ou « m-fonction ».

Dans une m-fonction, les seules expressions admissibles pour un remplacement de variables sont les m-configurations et les symboles de la machine. Elles doivent être énumérées plus ou moins explicitement, et certaines peuvent être de la forme p(e, x) ; elles sont même indispensables si l’on utilise la moindre des m-fonctions. Si nous n’insistions pas sur cette énumération explicite, mais nous contentions d’établir que la machine a un certain nombre de m-configurations (énumérées) et toutes les m-configurations obtenues par substitution de m-configurations dans certaines m-fonctions, nous aurions en général obtenu une infinité de m-configurations ; par exemple, nous devrions alors dire que la machine, ayant la m-configuration q et toutes celles obtenues en substituant une m-configuration à E dans p(E), aurait les m-configurations q, p(q), p(p(q)), p(p(p(q))), etc.

Notre règle d’interprétation est alors la suivante : on nous a fourni les noms des m-configurations de la machine, la plupart exprimées en termes de m-fonctions, ainsi que des tableaux types, et nous ne voulons que le tableau complet pour toutes les m-configurations de la machine. On l’obtient par substitutions réitérées des variables dans les tableaux types.

[237] Autres exemples.

Dans les commentaires ci-dessous, on utilise le symbole « → » dans le sens de « la machine se place dans la m-configuration… . »)

[fonction effacer : e = erase]

[m-config.symboleopérationsm-config. finale]

e(E, B, α)f(e₁(E, B, α), B, α)À partir de e(E, B, α) le premier α est effacé et → E. S’il n’y a pas d’α → B.

e₁(E, B, α)EE

e(B, α)e(e (B, α), B, α)À partir de e(B, α) toutes les lettres α sont effacées et → B.

L’interprétation de ce dernier exemple semble un peu plus difficile que celle de la plupart des autres. Supposons que dans la liste des m-configurations d’une certaine machine apparaisse e(b, x) (= q comme exemple de substitution). On obtient le tableau :

e (b, x)e(e(b, x), b, x)

Ou

qe(q, b, x).

Ou encore, en plus détaillé :

qe(q, b, x)

e (q, b, x)f(e₁(q, b, x), b, x)

e₁(q, b, x)Eq.

De là, nous pourrions remplacer e₁(q, b, x) par q’, puis présenter le tableau de f (avec les substitutions adéquates) et obtenir en fin de compte un tableau complet où n’apparaîtrait plus aucune m-fonction.

[fonction impression finale, pe = print at end]

[m-config.symboleopérationsm-config. finale]

pe(E, ß)f(pe₁(E, ß), E, ə) À partir de pe(E, ß) la machine imprime ß à la fin de la suite de symboles et → E.

n’importe lequelD, D pe₁ (E, ß)

pe₁(E, ß) ~

aucun IßE

l(E)GE

r(E)DE

[fonction trouver, f = find]

f’(E, B, α)f(l(E), B, α) À partir de f’(E, B, α), comme à partir de f(E, B, α), la machine trouve le premier symbole α, le plus à gauche, mais avant se déplace à gauche → E₁. S’il n’y a pas d’α → B.

f’’(E, B, α)f(r(E), B, α)À partir de f’’(E, B, α) pareillement mais à droite → E₁. S’il n’y a pas d’α → B.

[fonction copier, c = copy]

c(E, B, α)f’(c_l(E), B, α)À partir de c(E, B, α). la machine inscrit le premier symbole marqué avec α à la fin de la suite de symboles et → E.

c₁(E)ßpe(E, ß).

[238] Cette dernière ligne engendre toutes celles que l’on obtient en remplaçant ß par tout symbole susceptible d’apparaître sur la bande de la machine concernée.

m-config.symboleopérationsm-config. finale

[fonction copier-effacer, ce = copy erase]

ce(E, B, α)c(e(E, B, α), B, α)

ce(B, α)ce(ce(B, α), B, α) ce(B, α). À la fin, la machine recopie dans l’ordre tous les symboles marqués avec α, efface les lettres α et → B.

[fonction remplacer, re = replace]

re(E, B, α, ß)f(re₁(E, B, α, ß), B, α)re(E, B, α, ß). La machine remplace le premier α par ß et → E ou → B s’il n’y a pas d’α.

re₁(E, B, α, ß)E, IßE

re(B, α, ß)re(re(B, α, ß), B, α, ß)re(B, α, ß). La machine remplace tous les α par ß et → B.

cr(E, B, α) c(re(E, B, α, a, a), B, α)

cr(B, α) cr(cr(B, α), re(B, a, α), α)cr(B, α). Même recopie que ce(B, α) mais sans effacer les marques α. On utilise cette m-configuration lorsqu’il n’y a pas de lettres « a » déjà présentes sur la bande.

[fonction comparer, cp = compare]

cp(E₁, U, E, α, ß) f’(cp₁(E₁, U, ß), f(U, E, ß), α)cp(E₁, U, E, α, ß). La machine compare le premier symbole marqué avec α et le premier marqué avec ß et, s’il n’y a ni α ni ß, → E, → E ; si les symboles y sont tous deux et sont égaux, → U.

cp₁(E, U, ß)γf’(cp₂(E, U, γ), U, ß)

γE

cp₂(E, U, γ) ~

non γU.

[fonction comparer-effacer, cpe = compare erase]

cpe(E₁, U, E, α, ß)cp(e(e(E₁, E, ß), U, E, α, ß)cpe(E₁, U, E, α, ß) la machine fait la même comparaison que cp(E₁, U, E, α, ß) entre les premiers symboles marqués α et ß, mais les efface s’ils sont égaux.

cpe(U, E, α, ß)cpe(cpe(U, E, α, ß), U, E, α, ß)cpe(U, E, α, ß). la machine compare la suite des symboles marqués avec α et celle marquée avec ß et, si elles sont égales, → E, sinon → U. Certains des symboles α et ß sont effacés.

[239]

n’importe lequelDq(E)

q(E) ~

aucunDq₁(E)

n’importe lequelDq(E)

q₁(E) ~

aucunE

q(E, α)q(q₁(E, α)) q(E, α). La machine trouve le dernier symbole α, et → E.

αE

q₁(E, α) ~

non αGq₁(E, α)

[fonction impression finale, pe = print at end]

pe₂(E, α, ß)pe(pe(E, ß), α)pe₂(E, α, ß). La machine imprime α ß à la fin sur les deux dernières C-cases.

[fonction copier-effacer, ce = copy erase]

ce₂(B, α, ß)ce(ce(B, ß), α)

ce₃(B, α, ß, γ)ce(ce₂(B, ß, γ), α)ce₃(B, α, ß, γ). À la fin, la machine recopie les symboles marqués avec α, puis ceux marqués avec ß, et enfin ceux marqués avec γ ; elle efface les marques α, ß, γ, puis → B.

[fonction effacer, e = erase]

əDe₁(E)e(E). À partir de là les marques sont effacées de tous les symboles marqués sur les E-cases, et → E.

e(E) ~

non əGe(E)

n’importe lequelD, E, De₁(E)

e₁(E) ~

aucunE

5. Énumération des suites calculables.

Une suite calculable γ est déterminée par la description d’une machine qui calcule cette suite. Ainsi, le tableau de la p. 234 détermine la suite 001011011101111… . En fait, toute suite calculable peut être décrite au moyen d’un tableau de ce genre.

Il sera utile de mettre ces tableaux dans un format standard. En premier lieu, supposons que le tableau se présente sous le même forme que le premier tableau, par exemple, I p. 233, à savoir que les seules opérations admises dans la colonne du même nom sont de l’une des formes E : E, D : E, G : Iα : Iα, D : Iα, G : D : G : ou l’opération nulle (N). Le tableau peut toujours être mis sous cette forme en introduisant de nouvelles m-configurations. Maintenant, numérotons les m-configurations q₁, q₂, … q_R, de la même façon qu’en § 1. La m-configuration initiale est toujours q₁. Nous numérotons de même les symboles S₁, S₂, …, S_m [240] et, en particulier, S₀ = blanc, S₁ = 0, S₂ = 1. Désormais, les lignes du tableau prennent l’une des trois formes suivantes (quels que soient i, j, k, m).

m-config.symboleopérationsm-config. finale

q_iS_jIS_k, Gq_m(N₁)

q_iS_jIS_k, Dq_m(N₂)

q_iS_jIS_kq_m(N₃)

Des lignes telles que

q_iS_jE, Dq_m

sont à réécrire ainsi

q_iS_jIS₀, Dq_m

et des lignes telles que

q_iS_jDq_m

réécrites ainsi

q_iS_jIS_j, Dq_m

De cette manière, nous réduisons chaque ligne du tableau en une ligne d’une des formes (N₁), (N₂) ou (N₃).

À partir de chaque ligne de la forme (N₁), formons l’expression q_iS_jS_kGq_m ; à partir de chaque ligne de la forme (N₂), l’expression q_iS_jS_kDq_m ; et à partir de chaque ligne de forme (N₃) l’expression q_iS_jS_kNq_m.

Notons à la suite toutes les expressions ainsi formées à partir du tableau de la machine et séparons-les par des points-virgules. Nous obtenons ainsi une description complète de la machine. Dans cette description, nous remplacerons q_i par la lettre « C » suivie de i fois la lettre « A », et S_j par « C » suivi de j fois « B ». On peut appeler cette nouvelle description la description standard (D.S) de la machine. Elle n’est composée que des caractères « A », « B », « C », « G », « D », « N », et « ; ».

Enfin, si nous remplaçons les signes par des chiffres : « A » par « 1 », « B » par « 2 », « C » par « 3 », « G » par « 4 », « D » par « 5 », « N » par « 6 », et « ; » par « 7 », nous obtiendrons une description de la machine sous la forme d’une suite de chiffres arabes. On peut appeler l’entier représenté par cette suite le nombre descriptif (N.D) de la machine. Le N.D détermine exclusivement la D.S et la structure de la [241] machine. On peut noter M(n) la machine dont le N.D est n.

À chaque suite calculable correspond au moins un nombre descriptif, tandis qu’à un nombre descriptif correspond au plus une suite calculable. L’ensemble des suites et des nombres calculables est par conséquent dénombrable.

Cherchons le nombre descriptif de la machine I de § 3. En renommant les m-configurations, on obtient le nouveau tableau :

q₁S₀IS₁, Dq₂

q₂S₀IS₀, Dq₃

q₃S₀IS₂, Dq₄

q₄S₀IS₀, Dq₁

On pourrait obtenir d’autres tableaux en ajoutant des lignes inutiles telle que :

q₁S₁IS₁, Dq₂

On obtiendrait à partir de ce tableau la première forme standard de la machine :

q₁S₀S₁Dq_2 ; q₂S₀S₀Dq_3 ; q₃S₀S₂Dq_4 ; q₄S₀S₀Dq_1 ;

Et la description standard :

 ; CACCBDCAA ; CAACCDCAAA ; CAAACCBBDCAAAA ; CAAAACCDCA

Enfin un nombre descriptif de la machine :

31332531173113353111731113322531111731111335317

Et, avec la ligne inutile, cet autre N.D :

3133253117311335311173111332253111173111133531731323253117

Un nombre sera dit satisfaisant s’il est le nombre descriptif d’une machine acyclique. En § 8, l’on démontre qu’il ne peut exister de procédure générale pour décider si un nombre donné est satisfaisant ou ne l’est pas.

6. La machine à calculer universelle.

Il est possible de créer une unique machine U utilisable pour calculer n’importe quelle suite calculable. Si cette machine est équipée d’une bande au début de laquelle est inscrite la D.S d’une machine à calculer quelconque M, [242] U calculera alors une suite identique à celle que M calculerait. Dans cette section, j’explique dans ses grandes lignes le fonctionnement de U, dont le tableau complet est présenté dans la suivante.

Supposons d’abord que nous disposons d’une machine M’, qui inscrira dans les C-cases la suite des configurations complètes de M. On pourrait exprimer celles-ci sous la même forme qu’à la p. 235, à l’aide du second modèle (C) où tous les symboles figurent sur une seule ligne. Ou, mieux, nous pourrions transformer ce modèle (comme en § 5) en remplaçant chaque m-configuration par « C » suivi du nombre adéquat de « A », et en remplaçant chaque symbole par « C » suivi du nombre adéquat de « B ». Les nombres de lettres « A » et « B » doivent être les mêmes que ceux choisis en § 5, de sorte que, en particulier, blanc soit remplacé par « C », « 0 » par « CB » et 1 par « CBB ». Il faut réaliser ces substitutions après l’assemblage des configurations complètes, comme dans (C). Des difficultés surviennent si nous procédons d’abord aux substitutions, car les blancs de chaque configuration complète devraient alors tous être remplacés par des « C », de sorte qu’une configuration complète ne puisse être exprimée au moyen d’une suite finie de symboles.

Ainsi, si, dans la description de la machine II de § 3, nous remplaçons « o » par « CAA », « ə » par « CBBB », « q » par « CAAA », la suite (C) devient :

CA : CBBBCBBBCAACBCCB : CBBBCBBBCAAACBCCB :… (C₁)

(c’est la suite de symboles sur les C-cases).

Dès lors, il n’est pas difficile de voir que, si M peut être construite, c’est aussi le cas de M’. Chaque étape du calcul dans le mode de fonctionnement de la machine M’ va se référer aux règles de fonctionnement (i.e., la D.S.) de la machine M, incluses d’une manière ou d’une autre dans M’. Si nous ne considérons ces règles que dans leur faculté d’être retirées et remplacées par d’autres, nous obtenons quelque chose de très proche de la machine universelle.

Il manque encore un élément : pour le moment, la machine M’ n’imprime pas de chiffres. Nous pouvons y pallier en imprimant entre deux configurations complètes successives les chiffres apparus dans celle qui est la plus récente des deux. La suite (C₁) devient alors :

CA : 0 : 0 : CBBBCBBBCAACBCCB : CBBBCBBBCAAACBCCB : CBBB… (C₂)

Il n’est pas très évident que les E-cases soient en nombre suffisant pour le « gros » du travail nécessaire, mais c’est pourtant le cas.

Les suites de lettres comprises entre les doubles points dans des expressions telles que (C₁) peuvent être utilisées comme descriptions standard des configurations complètes. Si les lettres sont remplacées par des chiffres, comme en § 5, nous obtiendrons la description [243] d’une configuration complète sous la forme d’un nombre entier, que l’on peut appeler son nombre descriptif.

7. Description détaillée de la machine universelle.

Nous présentons ci-dessous le tableau du fonctionnement de cette machine universelle. Ses m-configurations sont toutes celles qui apparaissent dans la première et la dernière colonne du tableau, ainsi que toutes celles notées sur les tableaux complets provenant du développement des m-fonctions qui y figurent. Par exemple, e(anf) apparaît dans le tableau et c’est une m-fonction. Son tableau non abrégé est (voir p. 239)

əDe₁(anf)

e(anf) ~

non əGe(anf)

n’importe lequelD, E, De₁(anf)

e₁(anf) ~

aucunanf

Par conséquent, e₁(anf) est une m-configuration de U.

Lorsque l’on va mettre U en route, la bande qui la parcourt présente :

- les symboles « əə », l’un dans une C-case et l’autre dans la E-case suivante.

- puis, uniquement dans des C-cases (un seul symbole par case), la D.S de la machine, composée d’un certain nombre d’instructions séparées par des points-virgules.

- un double deux-points « ‡ » sur la C-case qui suit immédiatement la D.S.

Chaque instruction comprend cinq parties consécutives :

(i) un « C » suivi d’une série de « A », qui décrit la m-configuration pertinente.

(ii) un « C » suivi d’une série de « B », qui décrit le symbole inspecté.

(iii) un « C » suivi d’une autre série de « B », qui indique le symbole destiné à changer celui de la case inspectée.

(iv) « G », « D » ou « N », qui indique si la machine doit se déplacer à gauche, à droite, ou ne pas se déplacer.

(v) un « C » suivi d’une série de « A », qui décrit la m-configuration finale.

La machine U doit pouvoir imprimer les symboles « A », « B », « C », « 0 », « 1 », « u », « v », « w », « x », « y », « z », « : ». La D.S de la machine est composée des symboles « ; », « A », « B », « C », « D », « G » et « N ».

[244] Tableau auxiliaire type.

[fonction configurer : con = configure]

non AD, Dcon(E, α)À partir de con(E, α). En partant d’une C-case, disons S, la machine marque avec des α la suite (C) des cases qui définissent la configuration (m-configuration et symbole) la plus proche à droite de la case inspectée S, et → E.

con(E, α) ~

AG, Iα, Dcon₁ (E, α)

AD, Iα, Dcon₁(E, α)

con₁(E, α) ~CD, Iα, Dcon₂(E, α)

aucunIC, D, Iα, D, D, DE

ligne nécessaire pour introduire la représentation C de la case blanche lorsque la configuration complète de la machine finit par un q, notamment au démarrage de la machine ou lorsqu’un mouvement à droite fait passer au-delà de la dernière case inspectée. La correction rend valide la comparaison effectuée un peu plus loin dans fmp.

BD, Iα, Dcon₂(E, α)

con₂ (E, α) ~

non BD, DE L’appel con(E, ) place la machine, dans la configuration finale, sur la quatrième case à droite de la dernière case de la suite (C) trouvée, dont les marques sont effacées le cas échéant.

Tableau de U.

[fonction commencer : b = begin]

bf(b₁, b₁, ‡)À partir de b. La machine inscrit : DA sur les C-cases juste après le ‡, et → anf.

b₁D, D, I :, D, D, IC, D, D, IAanf

anfq(anf₁, :)anf. La machine marque avec y la configuration de la dernière configuration complète, et → fom.

anf₁con(fom, y)

 ;D, Iz, Gcon(fmp, x)fom. La machine trouve le dernier point-virgule non marqué avec z, le marque avec z, et la configuration suivante avec x, puis → fmp.

fom ~zG, Gfom

ni z ni  ;Gfom

fmpcpe(c(fom, x, y), sim, x, y)fmp. La machine compare les suites respectivement marquées avec x et avec y, efface toutes les lettres x et y, puis → sim si les suites sont égales, sinon → fom.

À partir de anf, d’un point de vue général, la machine trouve la dernière instruction correspondante à la dernière configuration, instruction que l’on peut ensuite reconnaître comme celle qui suit le dernier point-virgule marqué avec z, puis → sim..

[245]

[fonction simuler : sim = simulate]

simf’(sim₁, sim₁, z)sim. La machine marque les instructions à suivre, en particulier avec u, la partie relative aux opérations à effectuer (direction de déplacement et symbole à imprimer), et la m-configuration finale avec y. Les lettres z sont ensuite effacées, et → mf.

sim₁con(sim₂, )

Asim₃

sim₂ ~

non AG, Iu, D, D, Dsim₂

non AG, Iye(mf, z)

sim₃ ~

AG, Iy, D, D, Dsim₃

mfq(mf, :)

non AD, Dmf₁ mf₁. La machine marque la dernière configuration complète en quatre phases : le symbole immédiatement à gauche de la configuration est marqué avec x ; le reste de la configuration est divisé en deux parties, dont toute celle de gauche est marquée avec v, et celle de droite avec w ; les marques de la configuration sont effacées ; elle imprime un double point après l’ensemble, et → sh.

mf₁ ~

AG, G, G, Gmf₂

BD, Ix, G, G, Gmf₂

mf₂ ~ :mf₄

CD, Ix, G, G, Gmf₃

non  :D, Iv, G, G, Gmf₃

mf₃ ~

 :mf₄

mf₄con(l(l(mf₅)), )

n’imp. lequelD, Iw, Dmf₅

mf₅ ~

aucunI :sh

[fonction montrer : sh = show]

shf(sh₁, inst, u)sh. Les instructions (marquées avec u) sont examinées. Si la machine découvre qu’elles impliquent « Imprimer 0 » ou « Imprimer 1 », alors elle imprime 0 : ou 1 : à la fin, et → inst.

sh₁G, G, Gsh₂

CD, D, D, Dsh₃

sh₂ ~

non Cinst

BD, Dsh₄

sh₃ ~

non Binst

BD, Dsh₅

sh₄ ~

non Bpe₂(inst, 0, :)

Binst

sh₅ ~

non Bpe₂(inst, 1, :)

[246]

instq(l(inst₁), u)inst. La nouvelle configuration complète est inscrite et, en exécutant les instructions marquées de la machine simulée, modifie la m-configuration, la case inspectée et le symbole marqué sur la case précédemment inspectée. Les lettres u, v, w, x, y sont effacées, et → anf.

inst₁aD, Einst₁(α)

inst₁(G)ce₅(ov, v, y, x, u, w)

inst₁(D)ce₅(ov, v, x, u, y, w)

inst₁(N)ec₅(ov, v, x, y, u, w)

ove(anf)

8. Application du procédé diagonal.

On peut penser que les arguments qui démontrent que l’ensemble des nombres réels n’est pas dénombrable démontreraient aussi que l’ensemble des nombres et des suites calculables ne peut pas l’être non plus<ref name="ftn6"> Cf. Hobson, Theory of Functions of a Real Variable, 2^e éd., 1921, pp. 87-88.</ref>. On pourrait croire, par exemple, que la limite d’une suite de nombres calculables doit être calculable. À l’évidence, ce n’est vrai que si cette suite est définie par une règle.

Nous pourrions aussi appliquer le procédé diagonal. « Supposons que l’ensemble des suites calculables soit dénombrable, soit α_n la n-ième suite calculable, et ϕ_n(m) le m-ième chiffre de α_n. Soit alors la suite ß dont le n-ième chiffre est égal à 1 - ϕ_n(n). Puisque ß est calculable, il existe un nombre K tel que, quel que soit n, 1 - ϕ_n(n) = ϕ_K(n). Par exemple, avec n = K, nous obtenons 1 = 2ϕ_K(K), i.e. 1 est pair, ce qui est impossible. Par conséquent, l’ensemble des suites calculables n’est pas dénombrable ».

L’erreur de ce raisonnement réside dans le postulat que ß est calculable. Ce serait vrai si nous pouvions énumérer les suites calculables avec des moyens finis, mais ce problème d’énumération des suites calculables équivaut à celui de trouver si un nombre donné est le N.D. d’une machine acyclique, et nous ne disposons d’aucune procédure générale pour le réaliser en un nombre fini d’étapes. En fait, en utilisant correctement l’argument du procédé diagonal, nous pouvons montrer l’impossibilité d’une telle procédure générale.

La démonstration la plus simple et la plus directe consiste à montrer que, si ce procédé général existait, il existerait alors une machine qui calculerait ß. Cette démonstration, bien que parfaitement recevable, présente l’éventuel inconvénient de laisser au lecteur l’impression qu’« il y a vraisemblablement quelque chose de suspect ». Celle que je présenterai échappe à cet inconvénient et donne un aperçu de ce que veut dire le concept de « machine acyclique ». Elle ne dépend pas de la construction de la suite ß, mais de celle de ß’, dont le n-ième chiffre est ϕ_n(n).

[247] Supposons qu’il existe une telle procédure, ceci revient à la possibilité de créer une machine D qui, équipée de la D.S d’une quelconque machine à calculer M, testera cette D.S et, si M est cyclique, marquera la S.D avec le symbole « n », et avec « o » si elle est acyclique. En combinant les machines D et U, nous pourrions construire une machine N pour calculer la suite ß’. La machine D a sans doute besoin d’une bande pour fonctionner, et nous pouvons supposer qu’elle utilise les E-cases au-delà de la dernière des C-cases marquées avec des symboles, et qu’elle efface tout le « gros » du travail réalisé par D, dès qu’elle a rendu son verdict.

Le mouvement de cette machine N se décompose en phases. Dans les N - 1 premières phases, entre autres choses, les entiers 1, 2,…, N - 1 ont été inscrits et testés par la machine D. Un certain nombre d’entre eux, disons R(N - 1), se sont révélés être les N.D de machines acycliques. Pendant la phase N, la machine D teste le nombre N. Si N est satisfaisant, i.e. s’il est le N.D d’une machine acyclique, alors R(N) = 1 + R(N - 1) et l’on calcule les R(N) premiers chiffres de la suite dont N est un N.D. Le R(N)-ième chiffre de cette suite est inscrit en tant que l’un des chiffres de la suite ß’ calculée par H. Si N n’est pas satisfaisant, alors R(N) = R(N - 1) et la machine aborde la phase (N + 1) de son mouvement.

À partir de sa construction, on peut constater que N est acyclique, car chaque phase de son mouvement s’achève en un nombre fini d’étapes. En effet, d’après notre hypothèse sur D, c’est en un nombre fini d’étapes que l’on parvient à décider si N est satisfaisant. Si N n’est pas satisfaisant, alors la phase N s’achève. Si N est satisfaisant, cela signifie que la machine M(N), dont le N.D est N, est acyclique et que l’on peut dès lors calculer son R(N)-ième chiffre en un nombre fini d’étapes. Lorsque ce chiffre a été calculé et inscrit comme le R(N)-ième chiffre de ß’, la phase N s’achève. Il en résulte que N est acyclique.

Soit, maintenant, K le N.D de N. Que fait N dans la phase K de son mouvement ? Elle doit tester si K est satisfaisant et rendre le verdict « o » ou « n ». Puisque K est le N.D de N qui est acyclique, le verdict ne peut être « n ». Mais il ne peut non plus être « o » car, si tel était le cas, pendant la phase K de son mouvement, N devrait en effet calculer les R(K - 1) + 1 = R(K) premiers chiffres de la suite calculée par la machine dont le N.D est K, et écrire le R(K)-ième chiffre comme l’un de ceux de la suite calculée par N. Le calcul des R(K – 1) premiers chiffres s’effectuerait sans problème, mais les instructions pour le calcul du R(K)-ième reviendraient à « calculer les R(K) premiers chiffres de la suite calculée par N et à écrire le R(K)-ième », et ainsi de suite, de sorte qu’il serait impossible de jamais trouver ce R(K)-ième chiffre. I.e., N est cyclique, contrairement à la fois à ce que nous avons découvert dans le paragraphe précédent et au verdict « o ». Les deux verdicts étant contradictoires, nous concluons qu’il ne peut exister aucune machine D.

[248]

Nous pouvons en outre montrer qu’il ne peut exister de machine E qui, équipée de la D.S d’une machine M quelconque, décidera si cette machine M imprimera jamais un symbole donné (par exemple 0).

Nous montrerons d’abord que, si cette machine existe, il existe alors une procédure générale pour décider si une machine M donnée imprime une infinité de 0. Soit M1 une machine qui imprime la même suite que M, sauf qu’en lieu et place du premier 0 imprimé par M, M1 imprime <math>\stackrel{\acute }{0}</math>. De même M₂ doit avoir les deux premiers 0 de la suite initiale remplacés par des <math>\stackrel{\acute }{0}</math>, et ainsi de suite. S’il faut ainsi que M imprime

ABA01AAB0010AB …,

alors M1 imprimera

ABA<math>\stackrel{\acute }{0}</math>1AAB0010AB …,

et M₂ imprimera

ABA<math>\stackrel{\acute }{0}</math>1AAB<math>\stackrel{\acute }{0}</math>010AB … .

Soit alors une machine F qui, équipée de la D.S de M, inscrira successivement les D.S de M, de M1, de M₂, etc. (une telle machine existe effectivement). Nous combinons F et E pour obtenir une nouvelle machine G qui, au cours de son fonctionnement, utilise d’abord F pour inscrire la D.S de M, puis E pour la tester, et inscrit  :0 : si elle découvre que M n’imprime jamais 0 ; F inscrit ensuite la D.S de M1, qui est elle aussi testée,  :0 : étant imprimé si et seulement si M1 n’imprime jamais 0, et ainsi de suite. Testons maintenant G avec E. Si l’on découvre que G n’imprime jamais 0, alors M l’imprime une infinité de fois ; si G imprime au moins un 0, alors M ne l’imprime qu’un nombre fini de fois.

De la même manière, il existe une procédure générale pour décider si M imprime 1 infiniment souvent. En combinant ces deux procédures, nous en obtenons une autre pour décider si M imprime une infinité de chiffres, i.e. si M est acyclique. De ce fait, la machine E ne peut donc exister.

L’expression « il existe une procédure générale pour décider si… » a été utilisée tout au long de cette section de manière équivalente à « il existe une machine qui décidera si… ». Cet usage peut être légitimé si et seulement si nous pouvons justifier notre définition de la « calculabilité », car chacun de ces problèmes de « procédure générale » peut être énoncé comme un problème relatif à une procédure générale pour décider si un entier n donné possède une propriété G(n) (G(n) devrait signifier, par exemple, « n est satisfaisant » ou « n est le nombre de Gödel d’une formule démontrable »), et cela équivaut à calculer un nombre dont le n-ième chiffre est 1 si G(n) est vraie, et 0 si elle est fausse.

[249]

9. L’évaluation de la calculabilité des nombres.

Nous n’avons encore fait aucune tentative pour montrer que les nombres « calculables » comprennent tous les nombres que l’on devrait naturellement considérer comme calculables. Il est certain que tous les arguments qui peuvent être donnés doivent, par principe, faire appel à l’intuition et, pour cette raison, seront plutôt insatisfaisants du point de vue des mathématiques. La véritable question ici en jeu est : « Quelles sont les éventuelles procédures qui peuvent être mises en œuvre lorsque l’on calcule un nombre ? »

Mes arguments seront de trois types :

(a) Un appel direct à l’intuition.

(b) Une démonstration de l’équivalence de deux définitions (au cas où la nouvelle définition ait un sens intuitif plus fort).

(c) La présentation d’exemples de grandes familles de nombres calculables.

Une fois admis que les nombres calculables sont tous « calculables » selon ma définition, s’ensuivent d’autres propositions du même ordre. En particulier, s’il existe une procédure générale pour décider si un énoncé du calcul fonctionnel d’Hilbert est démontrable, alors cette procédure de décision peut être mise en œuvre par une machine.

I [Type (a)]. Cette discussion n’est qu’un développement des idées de § 1.

Généralement, on effectue un calcul en inscrivant certains symboles sur une feuille de papier, que nous pouvons supposer divisée en cases comme un manuel scolaire d’arithmétique. En arithmétique élémentaire, on tire parfois parti de la qualité bidimensionnelle du papier, mais il vaut mieux éviter un tel usage et je pense que l’on m’accordera que cette qualité n’a rien d’essentielle au calcul. Dès lors, je pars du principe que le calcul s’effectue sur du papier unidimensionnel, i.e. sur une bande divisée en une suite de cases. Je supposerai aussi que les symboles susceptibles d’être imprimés sont en nombre fini. Si nous devions admettre une infinité de symboles, il risquerait alors d’y avoir certains symboles, dont les différences seraient si arbitrairement ténues qu’on pourrait les confondre<ref name="ftn7"> Si nous considérons un symbole littéralement imprimé dans une case, en imaginant cette dernière selon un modèle algébrique cartésien de coordonnées x et y, tels que 0 ≤ x ≤ 1, 0 ≤ y ≤ 1, le symbole est défini comme un ensemble de points de cette case, c’est-à-dire l’ensemble des points noircis par l’encre imprimée. Si l’on se limite à des ensembles mesurables, nous pouvons définir la « distance » entre deux symboles comme le coût de la transformation de l’un en l’autre, si l’unité est le coût de déplacement d’une unité d’aire d’encre imprimée d’une distance unitaire, et s’il existe une source infinie d’encre en x = 2, y = 0. Dans cette topologie, les symboles forment sous condition un espace compact conditionnel.</ref>. Pour autant, l’effet de cette restriction n’est pas très important, puisque l’on peut toujours utiliser des suites de symboles au lieu des symboles uniques. Ainsi, un nombre écrit en chiffres arabes, tel que [250] 17 ou 999999999999999, est en général considéré comme un symbole en soi. De la même façon, dans les langues européennes, les mots sont traités comme des symboles simples (à la différence du chinois, qui tend à avoir une infinité dénombrable de symboles). De notre point de vue, les différences entre les symboles simples et les symboles composés, réside dans la longueur excessive de ces derniers, de sorte qu’ils ne peuvent être reconnus d’un coup d’œil, ce qui s’accorde avec l’expérience. Nous ne pouvons dire d’un coup d’œil si 9999999999999999 et 999999999999999 sont identiques<ref name="ftn8"> Georges Ifrah, Histoire universelle des chiffres, Bouquins, Robert Laffont, t. I, 1981, entre autres Première partie, chap. 1, L’ethnologie et la psychologie des nombres, explique en détail ce phénomène psycho-sensoriel : notre perception globale des nombres s’arrête à quatre. Au-delà, la vision n’est plus d’aucun secours et il est nécessaire de compter pour savoir. Dans les cultures restées à un stade dit premier, pour lesquelles le nombre est « senti » et « perçu », celui-ci est appréhendé non sous son aspect conceptuel et abstrait, mais d’une manière qualitative, et au-delà de quatre il ne reste souvent pour elles plus qu’une catégorie, celle de l’« innombrable ». Voir aussi les travaux de l’anthropologue Jack Goody, notamment Entre l’oralité et l’écriture, PUF, 1994 (Note du traducteur).</ref>.

À chaque instant, le comportement d’un calculateur humain est déterminé par les symboles qu’il observe et son « état mental » du moment. Nous pouvons supposer qu’il existe une limite au nombre maximal M de symboles ou de cases que ce calculateur peut observer simultanément. S’il souhaite en observer un plus grand nombre, il doit recourir à plusieurs observations successives. Nous supposerons en outre en nombre fini les états mentaux qu’il est nécessaire de prendre en compte, pour des raisons du même ordre que celles qui nous conduisent à limiter le nombre de symboles. Si, en effet, nous admettions une infinité de ces états, certains d’entre eux seraient « arbitrairement proches » au point d’être confondus. Là encore, cette restriction n’est pas de celles qui affectent sérieusement le calcul, puisque le recours à des états mentaux plus compliqués peut être évité en inscrivant plus de symboles sur la bande.

Imaginons maintenant que le travail du calculateur est divisé en « opérations élémentaires », si simples qu’il soit difficile d’envisager de les fragmenter encore plus. Toute opération de ce genre consiste à modifier le système physique constitué du calculateur et de sa bande, système dont nous connaissons l’état si nous connaissons la suite des symboles inscrits sur la bande, en particulier ceux (éventuellement ordonnés) observés par le calculateur, et l’état mental de ce dernier. Nous pouvons supposer que, dans une opération élémentaire, pas plus d’un symbole n’est modifié, tout autre changement pouvant se ramener à une suite de changements élémentaires de ce type. La situation vis-à-vis des cases, dont les symboles peuvent être ainsi modifiés, est la même qu’à l’égard des cases observées. Par conséquent, sans altération de la généralité, nous pouvons admettre que les cases modifiables sont toujours des cases « observées ».

Outre ces changements de symboles, les opérations élémentaires doivent comprendre des changements de distribution des cases observées. Le calculateur doit pouvoir immédiatement reconnaître les nouvelles cases observées, et je crois raisonnable de supposer que de telles cases ne peuvent être à plus d’une certaine distance donnée des cases les plus proches parmi celles qui viennent d’être observées. Disons que chacune des nouvelles cases observées est au plus à D-cases de distance de l’une des cases auparavant observées.

Concernant la notion de « reconnaissance immédiate », on peut penser qu’il devrait exister d’autres types de cases immédiatement reconnaissables, en particulier celles marquées par des symboles spéciaux. [251] Néanmoins, si ces cases ne sont marquées que de symboles simples, il ne peut en exister qu’un nombre fini, et les rajouter à l’ensemble des cases observées ne bouleverserait pas notre théorie. Si, en revanche, elles sont marquées par une suite de symboles, nous ne pouvons plus considérer le procédé de reconnaissance comme élémentaire. C’est un point si fondamental qu’il conviendrait de l’illustrer. Dans les articles de mathématiques, il est courant de numéroter les suites d’équations et de théorèmes. Ces nombres dépassent rarement, disons, le millier. On peut donc reconnaître d’un coup d’œil un théorème à son numéro. Mais, si un article est particulièrement long, nous pouvons en arriver au théorème 157767733443477 ; puis, plus loin, on pourrait lire « … en conséquence du théorème 157767733443477, nous obtenons donc… ». Pour être sûrs qu’il s’agit bien du bon théorème, il nous faudrait comparer ces deux nombres chiffre par chiffre, peut-être même en les cochant au crayon pour être surs de ne pas les compter deux fois. Et si, malgré tout, l’on pensait toujours qu’il existe d’autres cases « immédiatement reconnaissables », mon argumentation n’en serait pas affectée pour autant que ces cases puissent être trouvées par une procédure dont ma machine est capable. Cette idée est développée ci-dessous en III.

Les opérations élémentaires doivent ainsi comprendre :

(a) Les changements de symbole dans l’une des cases observées.

(b) Les changements de l’une des cases observées en une autre case à D-cases de distance au plus de l’une de celles précédemment observées.

Il est possible que quelques-uns de ces changements nécessitent aussi un changement d’état mental. L’opération élémentaire la plus générale doit donc prendre l’une des formes suivantes :

(A) Un changement éventuel (a) de symbole, conjointement avec un éventuel changement d’état mental.

(B) Un changement éventuel (b) de cases observées, conjointement avec un éventuel changement d’état mental.

Comme on l’a suggéré p. 250, l’opération véritablement réalisée est déterminée par l’état mental du calculateur et les symboles observés, en particulier, son nouvel état mental après l’exécution de cette opération.

Nous pouvons maintenant construire une machine pour réaliser le même travail que ce calculateur humain. À chacun des états mentaux du calculateur correspond une « m-configuration » de la machine. Celle-ci inspecte M cases correspondant aux M cases observées par le calculateur. À chaque instant, elle peut soit changer un symbole dans l’une des cases inspectées, soit inspecter une nouvelle case distante de moins de D-cases de l’une des autres cases [252] inspectées. Le mouvement effectué et la configuration suivante sont déterminés par le symbole inspecté et la m-configuration. Les machines que l’on vient de décrire ne sont pas foncièrement différentes des machines à calculer décrites en § 2 et, pour toute machine de ce type, il est possible de construire une machine pour calculer la même suite, c’est-à-dire la suite calculée par le calculateur humain.

II [Type (b)].

Si l’on modifie la notation du calcul fonctionnel d’Hilbert<ref name="ftn9"> L’expression « le calcul fonctionnel » est utilisée tout au long de l’article dans le sens de calcul fonctionnel restreint d’Hilbert.</ref> de façon à le rendre systématique, et pour qu’il n’utilise qu’un nombre fini de symboles, il devient possible de construire une machine automatique<ref name="ftn10"> Le plus naturel est de construire d’abord une machine à choix (cf. § 2) qui effectue cette tâche, mais il est facile d’en obtenir ensuite la machine automatique requise, car nous pouvons supposer que les choix sont toujours binaires entre 0 et 1. Chaque preuve sera alors déterminée par une série de choix i₁, i₂, …, i_n (valant chacun 0 ou 1), et donc le nombre 2ⁿ +i₁2^n-1 + i₂2^n-2 + … + i_n détermine complètement la preuve, et la machine automatique génère alors successivement la preuve 1, la preuve 2, la preuve 3, etc.</ref> K, qui trouvera toutes les formules démontrables de ce type de calcul<ref name="ftn11"> L’auteur a effectivement trouvé la description d’une telle machine.</ref>.

Soit maintenant une suite α, et notons G_α(x) la proposition « le x-ième chiffre de α est un 1 », <ref name="ftn12"> Le signe de la négation s’écrit devant une expression et non à la fin.</ref> - G_α (x) signifiant « Le x-ième chiffre de α est un 0 ». Supposons en outre que nous puissions trouver un ensemble de propriétés qui définissent la suite α et qui puisse être exprimé au moyen de G_α (x), des fonctions propositionnelles N(x) signifiant « x est un entier positif », et S(x, y) signifiant « y est le successeur de x » ou « y = x + 1 ». Par la conjonction de toutes les formules précédentes, nous obtiendrons une formule, disons U, qui définit α. Cette formule U doit comprendre les axiomes indispensables (i.e. les trois premiers) de Peano, notés sous la forme abrégée P, soit :

(<math>\exists </math>u) N(u) ˄ (<math>\forall </math>x) (N(x) → (<math>\exists </math>y) S(x, y) ˄ (S(x, y) → N(y)),

Notre expression « U définit α » signifie que – U n’est pas une formule démontrable, et aussi que, pour tout n, l’une des formules (A_n) ou (B_n) est démontrable.

U ˄ S⁽ⁿ⁾ → G_α(u⁽ⁿ⁾), (A_n)<ref name="ftn13"> ^(r) désigne une suite de nombres premiers r.</ref>

U ˄ S⁽ⁿ⁾ → (- G_α(u⁽ⁿ⁾)), (B_n),

où S⁽ⁿ⁾ est l’abréviation de S(u, u’) ˄ S(u’, u’’) ˄ … ˄ S(u^(n-1), u⁽ⁿ⁾).

[253]

J’affirme par déduction que α est alors une suite calculable : pour le montrer, une assez simple modification de K nous permet d’obtenir une machine K_α qui calcule α.

Nous décomposons le mouvement de K_α en phases. La phase n est destinée à calculer le n-ième chiffre de α. Dès que la phase n - 1 se termine, la machine imprime un symbole ‡ à la suite de tous les autres, et l’opération suivante s’effectue uniquement sur les cases à droite de ce symbole. La première étape consiste à écrire la lettre « A », suivie de la formule (A_n), puis la lettre « B » et la formule (B_n). La machine K_a effectue alors la même tâche que K, mais lorsqu’elle produit une formule démontrable, elle la compare à (A_n) et à (B_n). Si elle est égale à (A_n) (respectivement (B_n)), le chiffre « 1 » (respectivement « 0 ») s’imprime alors et, dans l’un ou l’autre cas, la phase n s’achève. Si elle n’est égale à aucune des deux formules, le travail de K reprend à partir du point auquel il avait été interrompu. Tôt ou tard, l’une des formules (A_n) ou (B_n) sera atteinte ; ceci découle de nos hypothèses sur α et U, et de ce que l’on sait de K. Dès lors, la phase n s’achèvera en un temps fini. K_α est donc acyclique et α calculable.

On peut aussi démontrer que les nombres tels que α ainsi définissables au moyen d’axiomes comprennent tous les nombres calculables, en décrivant les machines à calculer dans le formalisme du calcul fonctionnel.

Il faut se rappeler que nous avons donné un sens assez particulier à l’expression « U définit α ». Les nombres définissables (au sens usuel) ne sont pas forcément calculables. Soit la suite δ dont le nième chiffre est 1 ou 0 selon que n est ou n’est pas satisfaisant. Il découle immédiatement du théorème de § 8 que cette suite n’est pas calculable. Il est possible, pour autant que nous le sachions à présent, que n’importe quel nombre de chiffres d’une suite δ puisse être calculé, mais pas par une méthode uniforme. Lorsqu’un nombre suffisamment grand de chiffres de δ aura été calculé, il faudra une méthode fondamentalement nouvelle pour obtenir d’autres chiffres.

III. On peut considérer ce qui suit comme une modification du (I) ou un corollaire du II.

Nous supposons, comme en (I), que le calcul s’effectue sur une bande, mais nous éviterons d’utiliser ici la notion d’« état mental » en introduisant une analogie plus physique et mieux définie. Le calculateur humain peut toujours interrompre son travail, s’absenter, oublier tout ce qui s’y rapporte, revenir plus tard et le reprendre au point d’interruption. Pour ce faire, il doit laisser une note d’instructions (sous une forme normalisée quelconque) indiquant comment poursuivre le travail. Cette note est l’équivalent de l’« état mental ». Nous supposerons que le calculateur travaille d’une manière si décousue qu’il n’accomplit jamais plus d’une opération par séance. La note d’instructions doit donc lui permettre de réaliser une opération et de rédiger la note suivante. Ainsi l’état d’avancement du calcul est, à tout instant, entièrement déterminé par la note [254] d’instructions et les symboles sur la bande. Autrement dit, l’état du système peut être décrit par une seule expression (suite de symboles), que l’on peut appeler la « formule d’état », composée des symboles sur la bande suivis du symbole séparateur spécial Δ (qui, nous le supposons, n’apparaît nulle part ailleurs), puis de la note d’instructions. Nous savons qu’à toute étape donnée, la nouvelle formule d’état dépend uniquement de la précédente, et nous partons du principe que l’interdépendance de ces deux formules peut s’exprimer dans le formalisme du calcul fonctionnel. Pour le dire autrement, nous admettons qu’il existe un axiome U qui exprime les règles régissant la conduite du calculateur en fonction de la relation entre une formule d’état de n’importe quelle étape et celle de l’étape précédente. S’il en est ainsi, nous pouvons construire une machine qui inscrit les formules d’état successives, et à partir de là calcule le nombre cherché.

10. Exemples de grandes classes de nombres calculables.

Il sera d’abord utile de définir ce qu’est une fonction calculable d’une variable entière, calculable, etc. Il existe de nombreuses formulations équivalentes de la définition d’une fonction calculable d’une variable entière, la plus simple étant sans doute la suivante : si γ est une suite calculable où apparaît une infinité de 0<ref name="ftn14"> Si une machine M calcule γ, alors la question de savoir si M imprime 0 une infinité de fois est du même ordre que celle de savoir si M est acyclique.</ref>, et n un entier, la formule ξ(γ, n) est définie comme le nombre de 1 entre le n-ième et le (n + 1)-ième 0 de γ. On dit alors que ϕ(n) est calculable si et seulement si, pour tout n, la suite calculable γ est telle que ϕ(n) = ξ(γ, n). Voici une définition équivalente : soit H(x, y) la proposition ϕ(x) = y. On peut alors dire que ϕ est une fonction calculable si et seulement s’il existe un axiome non contradictoire U_ϕ, tel que

- U_ϕ → P,

- pour tout entier n, il existe un entier N tel que

U_ϕ ˄ S^(N) → H (u⁽ⁿ⁾, u^(ϕ(n))),

- pour tout m = ϕ(n), il existe alors un entier N’ tel que

U_ϕ ˄ S^(N’) → - H (u⁽ⁿ⁾, u^(m)),

Nous ne pouvons pas définir de manière générale des fonctions calculables d’une variable réelle, car il n’existe pas de méthode générale de description d’un nombre réel. En revanche, nous pouvons définir une fonction calculable d’une variable calculable. Si n est satisfaisant, notons γ_n le nombre calculé par M(n), et posons :

α_n = 0 si γ_n = 0 ou γ_n = 1,

[255]sinonα_n = tan(π (γ_n –<math>\frac{1}{2}</math>)).

Lorsque n décrit les nombres satisfaisants, α_n décrit l’ensemble des nombres calculables<ref name="ftn15"> On peut définir de nombreuses autres façons une fonction α_n pour décrire l’ensemble des nombres calculables.</ref>. Soit maintenant ϕ(n) une fonction calculable qui associe à tout nombre satisfaisant un nombre satisfaisant<ref name="ftn16"> Bien qu’il ne soit pas possible de trouver une procédure générale pour décider si un nombre donné est satisfaisant, il est souvent possible de démontrer que certaines classes de nombres sont globalement satisfaisantes.</ref>. On dira alors que la fonction f, définie par f(α_n) = α_ϕ(n), est une fonction calculable et, réciproquement, que toute fonction calculable d’une variable calculable peut s’exprimer de cette manière.

On peut donner des définitions semblables de fonctions calculables de plusieurs variables, ou des fonctions à valeur calculable d’une variable entière, etc.

J’énoncerai un certain nombre de théorèmes sur la calculabilité, mais je démontrerai seulement le théorème (ii) et une variante du théorème (iii).

(i) La composition de deux fonctions calculables d’une variable entière ou calculable est elle-même calculable.

(ii) Toute fonction d’une variable entière définie récursivement en termes de fonctions calculables est calculable. I.e. si ϕ(m, n) est une fonction calculable et r un nombre entier, la fonction η est alors calculable, là où η est définie par :

η(0) = r,

η(n) = ϕ(n, η(n - 1)) pour tout n > 0.

(iii) Si ϕ(m, n) est une fonction calculable de deux variables entières, alors ϕ(n, n) est une fonction calculable de la variable entière n.

(iv) Si ϕ(n) est une fonction calculable à valeurs dans {0, 1}, alors la suite dont le n-ième chiffre est ϕ(n) est calculable.

Le théorème de Dedekin devient faux dans sa formulation usuelle si nous remplaçons partout « réel » par « calculable », mais il reste vrai dans la version suivante :

(v) si G(a) est une fonction propositionnelle de nombres calculables et

(a)(<math>\exists </math>α) (<math>\exists </math>ß) (G(α) ˄ - G(ß)),

(b)G(α) ˄ (- G(ß)) → (α < ß),

et s’il existe une procédure générale permettant de déterminer la valeur de vérité de G(α), alors [256] il existe un nombre calculable ξ tel que :

G(α) → α ≤ ξ et - G(α) → α ≥ ξ.

Autrement dit, le théorème reste vrai pour toute coupure des nombres calculables pour laquelle il existe une procédure générale permettant de déterminer à quelle classe un nombre calculable donné appartient par rapport à cette coupure.

En raison de cette restriction du théorème de Dedekind, nous ne pouvons pas dire qu’un nombre calculable lié à une suite croissante de nombres calculables possède une limite calculable. On pourra peut-être le comprendre en considérant une suite telle que :

- 1, - <math>\frac{1}{2}</math>, - <math>\frac{1}{4}</math>, - <math>\frac{1}{8}</math>, - <math>\frac{1}{16}</math>, <math>\frac{1}{2}</math>, … .

Par contre, (v) nous permet de démontrer que :

(vi) Si ϕ est une fonction calculable croissante et continue, et α et ß des nombres calculables tels que α < ß et ϕ(α) < 0 < ϕ(ß), alors il existe un nombre calculable unique γ, répondant aux conditions α < γ < ß et ϕ(γ) = 0.

Convergence calculable.

Nous dirons qu’une suite ß_n de nombres calculables converge en calculabilité s’il existe une fonction calculable à valeur entière N(ε) de la variable calculable ε, telle que nous pouvons montrer que :

<math>\forall </math> ε > 0, <math>\forall </math> m > N(ε), <math>\forall </math> n > N(ε), alors | ß_n – ß_m |< ε.

Nous pouvons alors montrer les théorèmes suivants :

(vii) Une série potentielle dont les coefficients forment une suite calculable de nombres calculables est convergente en calculabilité en chaque point calculable à l’intérieur de son intervalle de convergence.

(viii) La limite d’une suite convergente en calculabilité est calculable.

Et avec la définition évidente de la « convergence uniforme en calculabilité » :

(ix) La limite d’une suite calculable uniformément convergente en calculabilité de fonctions calculables est une fonction calculable.

D’où :

(x) La somme d’une série potentielle dont les coefficients forment une suite calculable est une fonction calculable à l’intérieur de son intervalle de convergence.

Du théorème (viii) nous déduisons que π et e sont calculables, pour π = 4 (1 – <math>\frac{1}{3}</math> + <math>\frac{1}{5}</math> - …), et pour e = 1+ 1 + <math>\frac{1}{2!}</math> + <math>\frac{1}{3!}</math> + … .

[257]

Du théorème (vi) nous déduisons que tout nombre algébrique réel est calculable.

Des théorèmes (vi) et (x) que les zéros réels des fonctions de Bessel sont calculables.

Démonstration de (ii).

Soit H(x, y) la proposition « η(x) = y », et K(x, y, z) la proposition « ϕ(x, y) = z ». U_ϕ est l’axiome qui définit ϕ(x, y). Posons alors U_η :

U_ϕ ˄ P ˄ (S(x, y) → G(x, y)) ˄ (G(x, y) ˄ G(y, z) → G(x, z))

˄ (S^(r) → H(u, u^(r))) ˄ (S(v, w) ˄ H(v, x) et K(w, x, z) → H(w, z))

˄ [H(w, z) ˄ G(z, t) v G(t, z) → (- H(w, t)].

Je ne donnerai pas ici la démonstration de la consistance de U_η. Une telle démonstration peut être faite avec les méthodes utilisées dans Hilbert et Bernays (Grundlagen der Mathematik, Berlin, 1934, p. 209 sq.). La consistance de U_η est également évidente d’après sa signification.

Montrons d’abord que, quel que soit n, il existe N tel que

U_η ˄ S^(N) → H(u⁽ⁿ⁾, u^(η(n)))(ii. 1)

(1) On a directement

U_η ˄ S^(r) → H(u, u^(η(u)))

(2) Supposons que pour n, N donnés, on a

U_η ˄ S^(N) → H(u^(n-1), u^(η(n-1)))

Par calculabilité de ϕ, il existe M tel que

U_ϕ ˄ S^(M) → K(u⁽ⁿ⁾, u^(η(n-1)), u^(η(n)))

D’où

U_η ˄ S^(M) → S(u^(n-1), u⁽ⁿ⁾) ˄ H(u^(n-1), u^(η(n-1))) ˄ K(u⁽ⁿ⁾, u^(η(n-1)), u^(η(n)))

Or

U_η ˄ S^(M) → [S(u^(n-1), u⁽ⁿ⁾) ˄ H(u^(n-1), u^(η(n-1))) ˄ K(u⁽ⁿ⁾, u^(η(n-1)), u^(η(n))) → H(u⁽ⁿ⁾, u^(η(n)))]

On a donc

U_η ˄ S^(M) → H(u⁽ⁿ⁾, u^(η(n)))

Ce qui démontre (ii. 1) par récurrence.

D’autre part, si m ≠ η(n) et M’ ≥ Max(M, m), on a

U_η ˄ S^(M’) → G(u^η((n)), u^(m)) ˅ G(u^(m), u^(η(n)))

[258]

Or,

U_η ˄ S^(M’) → [(H(u⁽ⁿ⁾, u^(η(n))) ˄ G(u^η((n)), u^(m)) ˅ G(u^(m), u^(η(n))) → - H(u⁽ⁿ⁾, u^(m)))]

Ce qui prouve que

U_η ˄ S^(M’) → - H(u⁽ⁿ⁾, u^(m))(ii. 2)

Les deux conditions de notre seconde définition d’une fonction calculable sont donc satisfaites, et il en résulte que η est une fonction calculable.

Démonstration d’une version modifiée de (iii).

(iii’) Étant donnée une machine N qui calcule une suite γ_n d’après le nombre n d’une suite de symboles « S » dont la bande est initialement équipée, et ϕ_n(m) le m-ième chiffre de γ_n, alors la suite ζ dont le n-ième chiffre est ϕ_n(n) est calculable.

Considérons que la machine N est équipée d’une bande où sont inscrits les symboles əə suivis d’une suite d’un nombre quelconque n de symboles « S » sur les C-cases, et part de la m-configuration b. Nous supposons que le tableau pour N a été écrit de façon qu’il n’y ait qu’une seule instruction (colonne des opérations) par ligne (impression d’un symbole ou déplacement), et que les symboles Ξ, Θ, <math>\stackrel{\acute }{0}</math>, et <math>\stackrel{\acute }{1}</math> n’apparaissent pas dans le tableau. Nous remplaçons partout ə par Θ, 0 par <math>\stackrel{\acute }{0}</math>, et 1 par <math>\stackrel{\acute }{1}</math>. D’autres substitutions sont alors effectuées. Nous remplaçons toute ligne de la forme

UαI<math>\stackrel{\acute }{0}</math>B

par

UαI<math>\stackrel{\acute }{0}</math>re(B, u, h, k)

et toute ligne de la forme

UαI<math>\stackrel{\acute }{1}</math>B

par

UαI<math>\stackrel{\acute }{1}</math>re(B, v, h, k)

et nous rajoutons au tableau les lignes suivantes :

upe(u₁, 0)

u₁D, Ik, D, IΘ, D, IΘu₃

u₂re(u₃, u₃, b, k, h)

u3pe(u₂, F)

et exactement les mêmes lignes en substituant v à u et 1 à 0.

rajoutons enfin la ligne suivante

cD, IΘ, D, IΘ, D, IS b

Nous obtenons ainsi le tableau d’une machine N’ qui calcule ζ à partir de la m-configuration initiale c, et le symbole inspecté au départ étant le second ə.

[259]

11. Application au problème de la décision (Entscheidungsproblem).

Les résultats de § 8 ont d’importantes conséquences. En particulier, on peut les utiliser pour montrer que le problème de la décision de Hilbert (Entscheidungsproblem) peut ne pas avoir de solution. Je me contenterai ici de démontrer ce théorème particulier et, pour une formulation précise du problème en question, je renverrai le lecteur à Hilbert et Ackermann (Grundzüge der Theoretischen Logik, Berlin, 1931, chapitre 3).

Je me propose donc de démontrer qu’il ne peut pas exister de procédure générale qui permette de décider si une formule U du calcul fonctionnel K est démontrable, i.e. qu’il ne peut pas exister de machine qui, pour toute formule U, dira finalement si U est démontrable.

Il conviendrait peut-être de noter que la démonstration que je me propose de faire est assez différente des résultats bien connus de Gödel<ref name="ftn17"> Op. cit.</ref>. Ce dernier a en effet montré qu’il existe (dans le formalisme des Principia Mathematica<ref name="ftn18"> Somme en trois volumes, publiés en 1910-1913 par Alfred North Whitehead et son élève Bertrand Russell, qui se propose d’éclaircir les fondements de l’algèbre et les démonstrations qui en découlent à partir de la logique formelle dans une version réadaptée de la notation de Giuseppe Peano. Première formulation axiomatique, rigoureuse et cohérente des principes généraux des mathématiques, et à ce titre d’une grande importance historique, elle est d’un formalisme lourd, utilisant des dizaines de pages pour prouver des propositions qui peuvent paraître évidentes (Note du traducteur).</ref>) des propositions U telles que ni U, ni – U, ne sont démontrables, d’où il résulte que l’on ne peut donner aucune preuve de la consistance des Principia Mathematica (ou de K) à l’intérieur de ce formalisme. Pour ma part, je montrerai qu’il n’existe pas de méthode générale qui permette de dire si une formule donnée U est démontrable dans K, ou, ce qui revient au même, si le système composé de K et de l’axiome supplémentaire – U est consistant.

S’il avait été prouvé le contraire de ce que Gödel a démontré, i.e. si, pour chaque proposition U, soit U soit son contraire – U est démontrable, alors nous devrions avoir une solution immédiate du problème de la décision (Entscheidungsproblem). Nous pouvons en effet inventer une machine K permettant de démontrer l’une après l’autre toutes les formules démontrables. Tôt ou tard, elle va atteindre soit U soit – U. Si elle atteint U, alors nous saurons qu’U est démontrable, et si elle atteint - U, alors, puisque K est consistant (voir Hilbert et Ackermann, p. 65), nous saurons que U n’est pas démontrable.

En raison de l’absence d’entiers dans K, les démonstrations suivantes vont paraître un peu fastidieuses, mais les idées sous-jacentes sont tout à fait immédiates.

À toute machine à calculer M, nous associons une formule In(M) et nous montrons que, s’il existe une méthode générale permettant de dire si In(M) est démontrable, alors il en existe aussi une pour dire si M imprime au moins une fois 0.

Les interprétations des fonctions propositionnelles utilisées sont les suivantes :

R_Sj(x, y) : « dans la configuration complète x (de M) le symbole sur la case y est S_j ».

[260]

I(x, y) : « dans la configuration complète x, la case y est la case inspectée ».

K_qm(x) : « dans la configuration complète x, la m-configuration est q_m ».

S(x, y) : « y est le successeur immédiat de x ».

G(x, y) : « x précède y (mais n’est pas forcément son prédécesseur immédiat) ».

Et Inst{q_iS_jS_kGq_l} comme abréviation de

(<math>\forall </math>x, <math>\forall </math> y, <math>\forall </math> x’, <math>\forall </math> y’) { (R_Sj(x, y) ˄ I(x, y) ˄ K_qi(x) ˄ S(x, x’) ˄ S(y’, y))

→ (I(x’, y’) ˄ R_Sk(x’, y) ˄ K_ql(x’) ˄ S(y’, z)

˅ [ (R_S0(x, z) → R_S0(x’, z))

˄ (R_S1(x, z) → R_S1(x’, z)) ˄ … ˄ (R_SM(x, z) → R_SM(x’, z))])}.

et des abréviations construites de façon similaire pour Inst{q_iS_jS_kD_ql} et Inst{q_iS_jS_kN_ql}.

Présentons la description de M dans la première forme standard de § 6. Cette description se compose d’un certain nombre d’expressions telle que « q_iS_jS_kG_ql » (ou D ou N à la place de G). Formons toutes les expressions correspondantes telle que Inst{q_iS_jS_kG_ql} et considérons leur conjonction, que nous appelons Des(M).

Notons Q la formule qui définit les propriétés du successeur :

(<math>\forall </math>x) (<math>\exists </math>w) (<math>\forall </math>y) (<math>\forall </math>z)

{ (S(x, w) ˄ (S(x, y) → G(x, y)) ˄ (S(x, z) ˄ G(z, y) → G(x, y)) ˄ [G(z, x) ˅ (G(x, y) ˄ S(y, z)) ˅ (S(x, y) ˄ S(z, y)) → - S(x, z) ] }(Q)

Posons alors A(M) qui définit exactement la machine :

Q ˄ (<math>\forall </math>y) R_S0(u, y) ˄ I(u, u) ˄ K_q1(u) ˄ Des(M)(A(M))

Nous pouvons alors construire la formule In(M)

(<math>\exists </math>u) A(M) → (<math>\exists </math>s) (<math>\exists </math>t) R_s1(s, t)(In(M))

Si nous nous référons aux interprétations suggérées pp. 259-60, la formule In(M) se traduit ainsi : « il existe une configuration complète de M telle que S₁ (i.e. 0) soit présent sur la bande » ou « M imprime au moins une fois le symbole 0 ». En liaison avec ceci, je vais démontrer que les deux propositions suivantes sont équivalentes :

(a) « S₁ apparaît sur la bande dans une configuration complète de M ».

(b) « In(M) est démontrable ».

Parvenu à ce point, le reste de la démonstration du théorème est banal.

[261]

Lemme 1. Si S₁ apparaît sur la bande dans une configuration complète de M, alors In(M) est démontrable.

Nous devons préciser la démonstration d’In(M). Supposons que, dans la n-ième configuration complète, i(n) étant le numéro de la case inspectée, q_k(n) la m-configuration, et S_{1(n, k)} le symbole présent sur la k-ième case, la suite de symboles sur la bande est dès lors S_{1(n, 0)}, S_{1(n, 1)},…, S_r(n, n), suivie uniquement de blancs. Nous pouvons alors formuler la proposition :

R_Sr(n,0) (u⁽ⁿ⁾, u) ˄ R_Sr(n,1) (u⁽ⁿ⁾, u’) ˄… ˄ R_Sr(n,n) (u⁽ⁿ⁾, u⁽ⁿ⁾) ˄ I(u⁽ⁿ⁾, u⁽ⁱ⁽ⁿ⁾⁾) ˄ K_qk(n) ˄ (<math>\forall </math>y) S(y, u’) ˅ S(u, y) ˅ S(u’, y) ˅ … ˅ S(u^(n-1), y) ˅ R_S0(u⁽ⁿ⁾, y) (abrégée CC_n)

Je montrerai que, pour tout n,

A(M) ˄ F⁽ⁿ⁾ → CC_n (abrégée CF_n)

est démontrable. CF_n signifie « la n-ième configuration complète de M et ainsi de suite », où « ainsi de suite » correspond à la n-ième configuration complète réelle de M. L’on doit donc s’attendre à ce que CF_n puisse être démontrable.

CF₀ est certainement démontrable car, dans la configuration complète n°0 de M, la bande est entièrement vierge, la m-configuration est q₁, et la case inspectée la n° 0, soit u, i.e. CC₀ est

(<math>\forall </math>y) R_S0(u, y) ˄ I(u, u) ˄ K_q1(u).

Chacun de ces termes étant inclus dans A(M), la proposition A(M) → CC₀ est alors démontrable.

Nous montrons ensuite que pour tout n, CF_n → CF_n+1 est démontrable. Trois cas sont à considérer selon le mouvement de la machine entre la n-ième et la (n+1)-ième configuration : à gauche, à droite ou stationnaire. Supposons le premier cas, i.e. la machine se déplace à gauche. Les deux autres cas sont tout à fait similaires. Si r(n, i(n)) = b, r(n+1, i(n)) = d, k(n) = a, et k(n+1) = c, Inst{q_aS_bS_dG_qc} doit être l’un des termes compris dans Des(M), i.e.

Des(M) → Inst{q_aS_bS_dG_qc}

d’où

A(M) ˄ F⁽ⁿ⁺¹⁾ → Inst{q_aS_bS_dG_qc} ˄ F⁽ⁿ⁺¹⁾.

or

Inst{q_aS_bS_dG_qc} ˄ Q ˄ F⁽ⁿ⁺¹⁾ → (CC_n → CC_n+1)

est démontrable, et donc

A(M) ˄ F⁽ⁿ⁺¹⁾ → (CC_n → CC_n+1)

[262]

l’est aussi, et

(A(M) ˄ F⁽ⁿ⁾ → CC_n) → (A(M) ˄ F⁽ⁿ⁺¹⁾ → CC_n+1),

i.e. exactement CF_n → CF_n+1.

Ainsi, CF_n est démontrable quel que soit n. Et l’hypothèse de notre lemme est que S₁ apparaît dans l’une des configurations complètes, dans la suite des symboles imprimés de M, c’est-à-dire qu’il existe des entiers N, K, tels que R_S1(u^(N), u^(K)) est l’un des termes de CC_N, d’où CC_N → R_S1 (u^(N), u^(K)) est démontrable. Or A(M) ˄ F^(N) → CC^N. Nous avons aussi :

(<math>\exists </math>u) A(M) → (<math>\exists </math>u) (<math>\exists </math>u’) … (<math>\exists </math>u^(N’)) (A(M) ˄ F^(N)),

où N’ = Max(N, K). De là,

(<math>\exists </math>u) A(M) → (<math>\exists </math>u) (<math>\exists </math>u’) … (<math>\exists </math>u^(N’)) R_S1(u^(N), u^(K)),

(<math>\exists </math>u) A(M) → (<math>\exists </math>u^(N)) (<math>\exists </math>u^(K)) R_S1(u^(N), u^(K)),

(<math>\exists </math>u) A(M) → (<math>\exists </math>s) (<math>\exists </math>t) R_S1(s, t),

i.e. In(M) est démontrable, ce qui démontre le lemme 1.

Lemme 2. Si In(M) est démontrable, alors S₁ apparaît sur la bande dans l’une des configurations complètes de M.

En substituant des fonctions propositionnelles aux variables fonctionnelles dans une formule démontrable, nous obtenons une proposition vraie. En particulier, si nous remplaçons ces variables par leurs interprétations des tableaux pp. 259-260 dans In(M), nous obtenons une proposition vraie signifiant « S₁ apparaît quelque part sur la bande dans l’une des configurations complètes de M ».

Nous sommes maintenant à même de montrer que le problème de la décision (Entscheidungsproblem) ne peut pas avoir de solution. Supposons en effet le contraire. Il existe alors une procédure générale (mécanique) permettant de déterminer si In(M) est démontrable. Les lemmes 1 et 2 impliquent qu’il existe dès lors une procédure générale pour déterminer si M imprime au moins une fois 0, ce qui est impossible d’après les résultats de § 8. Il en résulte que le problème de la décision (Entscheidungsproblem) ne peut pas avoir de solution.

Au vu du grand nombre de solutions particulières du problème de la décision (Entscheidungsproblem) pour des formules à systèmes restreints de quantificateurs, [263] il est intéressant d’exprimer In(M) sous une forme restrictive où tous les quantificateurs sont au début. On peut ainsi exprimer In(M) sous la forme suivante :

(<math>\forall </math>u) (<math>\exists </math>x) (<math>\forall </math>w) (<math>\exists </math>u₁) … (<math>\exists </math>u₄) B,(I)

où la formule B est exempte de quantificateurs.

Appendice.

(28 août 1936)

Calculabilité et calculabilité effective

Nous présentons ci-dessous les grandes lignes de la démonstration du théorème de l’équivalence des suites effectivement calculables (λ-définissables) et des suites calculables. On suppose compris les termes « formule bien formée » (F.B.F.) et « conversion » utilisés par Church et Kleene. Dans la seconde partie de notre argumentation (tout nombre calculable est λ-définissable), on postule l’existence de plusieurs formules sans démonstration ; ces formules peuvent être directement créées à l’aide, par exemple, des résultats de Kleene (« A theory of positive integers in formal logic », American Journal of Math., 57, 935, pp. 153-173 et 219-244).

On notera N_n la F.B.F. représentant un entier n. Nous dirons que la suite γ dont le n-ième chiffre est ϕ_γ(n) est λ-définissable ou effectivement calculable si et seulement si 1 + ϕ_γ(n) est une fonction λ-définissable de n, i.e. s’il existe une F.B.F. M_γ telle que, pour tout entier n,

{M_γ} (N_n) conv N_{1 + ϕγ(n)},

i.e. si {M_γ} (N_n) est convertible en λxy.x(y) ou en λxy.x(x(y)) selon que le n-ième chiffre de γ est un 0 ou un 1.

Pour démontrer que toute suite γ λ-définissable est aussi calculable, il nous faut construire une machine qui permette de calculer γ. Pour utiliser les F.B.F. avec des machines, il est plus pratique d’effectuer une petite modification dans leur calcul de conversion. Ce changement consiste à renommer x, x’, x’’, etc., les variables a, b, c, etc. Puis, nous construisons une machine L qui, munie de la formule M_γ, inscrit la suite γ. La construction de L est assez similaire à celle de la machine K qui trouve toutes les formules démontrables du calcul fonctionnel. Nous construisons d’abord une machine à choix L₁ qui, munie d’une F.B.F., par exemple la formule initiale M, et bien utilisée, génère toute formule en laquelle cette formule est convertible. On peut alors modifier L₁ pour obtenir une machine automatique L₂ qui produit successivement toutes les formules [264] en lesquelles M est convertible (cf. la note p. 252 sur la transformation d’une c-machine en a-machine). La machine L₂ est une des composantes de L. Le mouvement de la machine L munie de la formule M_γ se décompose en phases, dont la phase n est destinée à trouver le n-ième chiffre de la suite γ, en inscrivant tout d’abord dans cette n-ième phase la F.B.F. {M_γ} (N_n), puis en fournissant cette formule à la machine L₂ pour que celle-ci la convertisse successivement en un certain nombre d’autres formules. Chaque formule ainsi générée, telle qu’on la rencontre, est finalement comparée avec les formes normales principales de N₁ et N₂, soit :

λ[λx’[ {x} (x’)]](N₁)

λx[λx’[ {x} ( {x} (x’))]] (N₂)

Si la formule est égale à N₁ (ou N₂), la machine imprime alors le chiffre 0 (ou 1) et la phase n s’achève. Si elle est différente des deux, alors L₂ reprend son travail pour générer une nouvelle formule. Par hypothèse, {M_γ} (N_n) est convertible en l’une des formules N₂ ou N₁ ; de ce fait, la phase n finira par s’achever, i.e. le nième chiffre de la suite γ finira par s’inscrire.

Pour démontrer que toute suite calculable γ est λ-définissable, nous devons montrer que l’on peut créer une F.B.F. M_γ telle que, pour tout entier n,

{M_γ} (N_n) conv N_1+ϕγ(n)(A₁)

Soit une machine M permettant de calculer la suite γ, et utilisons une description des configurations complètes de M au moyen de nombres, par exemple son N.D de configuration complète décrit en § 6. Soit ξ_M(n) le N.D de la n-ième configuration complète de M. Le tableau de la machine M nous donne, entre les nombres ξ_M(n) et ξ_M(n+1), une relation de la forme :

ξ_M(n+1) = ρ_M(ξ_M(n)),

où ρ_M est une fonction de forme très restreinte, même si, en général, elle n’est pas vraiment très simple : on l’obtient à partir du tableau de M, et elle est λ-définissable (mais je n’en donne pas ici de démonstration), i.e. il existe une F.B.F. A_M telle que, pour tout entier n,

{A_M} (N_ξM(n)) conv ξ_M(n+1).

Soit U_M substitué à :

λu[{{u} (A_M} (N_r)], où r = ξ_M (0)(U_M)

pour tout entier n, on a :

{U_M} (N_n) conv N_ξM(n).

[265]

On peut démontrer qu’il existe une formule V telle que :

N₁ si, la machine passant de la n-ième à la (n+1)-ième configuration complète, elle imprime entre les deux le chiffre 0.

{{V} (N_ξM(n+1))} (N_ξM(n)) conv ~N₂ si la machine imprime le chiffre 1.

N₃ sinon.

Soit W_M substitué à :

λu [{{V} ({A_M} ({U_M} (u)))} ({U_M } (u))](W_M)

de sorte que, pour tout entier n,

{{V} (N_ξM(n+1))} (N_ξM(n)) conv {W_M} (N_n),

et soit Q une formule telle que

{{Q} (W_M)} (N_s) conv N_r(s),

où r(s) est le s-ième entier q pour lequel {W_M} (N_q) est convertible soit en N₁ soit en N₂. Alors, si M_M est substitué à

λw [{W_M} ({{Q} (W_M)} (w))](M_M)

M_M aura la propriété (A₁) requise<ref name="ftn19"> Pour une démonstration complète de la λ-définissabilité de suites calculables, il vaudrait mieux modifier cette méthode en remplaçant la description numérique des configurations complètes par une description que l’on puisse traiter plus facilement avec nos outils du λ-calcul. Pour cela, choisissons certains entiers pour représenter les symboles et les m-configurations de la machine. Imaginons, dans une certaine configuration complète, que la suite de symboles sur la bande est représentée par les nombres s₁, s₂, … s_n, le symbole inspecté est le m-ième, et la m-configuration porte le nombre t ; nous pouvons alors représenter cette configuration complète par la formule

[[N_s1, N_s2, …, N_sm-1], [N_t, N_sm], [N_sm+1, …, N_sn]],

où [a, b] est l’abréviation de λu [{{u} (a)} (b)],

[a, b, c] est l’abréviation de λu [{{{u} (a)} (b)} (c)],

etc.</ref>.

Graduate College,

Princeton University,

New Jersey, U.S.A.

Correctif à la calculabilité des nombres et son application au problème de la décision (Entscheidungsproblem). (A. M. Turing)

Sources et version de l’article original en ligne :

Turing, Alan : « On Computable Numbers, with an Application to the Entscheidungsproblem. A correction », in Proc. London Math. Soc., 2^e série, vol. 43, 1938, pp. 544-546.

http://www.wolframscience.com/prizes/tm23/images/Turing2.pdf

Dans un article intitulé « On computable numbers, with an application to the Entscheidungsproblem »<ref name="ftn20"> Proc. London Math. Soc. (2), 42 (1936-7), 230-265.</ref>, l’auteur a donné une démonstration de l’insolubilité du problème de la décision (Entscheidungsproblem) du « calcul fonctionnel restreint » (« engere Funktionenkalkül »). Cette démonstration contenait des erreurs formelles<ref name="ftn21"> L’auteur est redevable à P. Bernays du signalement de ces erreurs.</ref> qui seront ici corrigées : il y a aussi quelques autres affirmations dans le même article qui devraient être modifiées, bien qu’en l’état elles ne soient pas véritablement fausses.

Il faut ainsi lire l’expression de Inst{q_iS_jS_kLq_l} à la p. 260 de l’article cité :

(<math>\forall </math>x, <math>\forall </math> y, <math>\forall </math> x’, <math>\forall </math> y’) { (R_Sj(x, y) ˄ I(x, y) ˄ K_qi(x) ˄ S(x, x’) ˄ S(y’, y))

→ (I(x’, y’) ˄ R_Sk(x’, y) ˄ K_ql(x’) ˄ S(y’, z)

˅ [ (R_S0(x, z) → R_S0(x’, z))

˄ (R_S1(x, z) → R_S1(x’, z)) ˄ … ˄ (R_SM(x, z) → R_SM(x’, z))])}.

S₀, S₁, …, S_M étant les symboles que M peut imprimer.

L’affirmation p. 261, ligne 33 : « Inst{q_aS_bS_dG_qc} ˄ F⁽ⁿ⁺¹⁾ → (CC_n → CC_n+1) est démontrable » est fausse (même avec la nouvelle expression de Inst{q_aS_bS_dL_qc}) ; nous ne pouvons pas par exemple déduire F⁽ⁿ⁺¹⁾ → (- F(u, u’’)), et donc nous ne pouvons utiliser dans Inst{q_aS_bS_dL_qc} le terme

F(y’, z) ˅ [(R_S0(x, z) → R_S0(x’, z)) ˄ … ˄ (R_SM(x, z) → R_SM(x’, z))]

[545]

Pour cette correction, nous introduisons une nouvelle variable fonctionnelle G [G(x, y) qui signifie « x précède y »]. Alors, si Q est une abréviation de :

(<math>\forall </math>x) (<math>\exists </math>w) (y, z) { F(x, w) ˄ (F(x, y) → G(x, y)) ˄ (F(x, z) ˄ G(z, y) → G(x, y))

˄ G(z, x) v (G(x, y) ˄ F(y, z)) v (F(x, y) ˄ F(z, y)) → (-F(x, z))]}

la formule correcte In(M) doit être

(<math>\exists </math>u) A(M) → (<math>\exists </math>s) (<math>\exists </math>t) R_s1(s, t),

où A(M) est une abréviation de

Q ˄ (y) R_s0(u, y) ˄ I (u, u) ˄ K_q1(u) & Des(M).

L’affirmation page 261 (ligne 33) doit alors se lire

Inst{q_aS_bS_dL_qc} ˄ Q ˄ F⁽ⁿ⁺¹⁾ → (CC_n → CC_n+1),

et la ligne 29 devrait se lire

r(n, i(n)) = b, r(n+1, i(n)) = d, k(n) = a, et k(n+1) = c.

À la place des mots « somme logique » p. 260, ligne 15, lire « conjonction ». Avec ces modifications, la démonstration est correcte. In(M) peut être mis sous la forme (I) (p. 263) avec n = 4.

Des difficultés surviennent du fait de la définition particulière que l’on a donnée du « nombre calculable » (p. 233). En effet, si les nombres calculables devaient satisfaire à des exigences intuitives, nous aurions :

Soient deux suites calculables de nombres rationnels a_n, b_n dans lesquelles ils sont associés deux par deux à un entier positif n, tels que, pour tout n, a_n ≤ a_n+1 < b_n+1 ≤ b_n, et b_n - a_n < 2^-n, alors il existe un nombre calculable α tel que, pour tout n, a_n ≤ α ≤ b_n.(A)

On peut en donner une démonstration, valable selon les standards mathématiques en vigueur, mais exigeant une application du principe du tiers exclu. En revanche, la proposition suivante est fausse :

Il existe une procédure qui permet d’obtenir le N.D d’une machine à calculer le nombre α à partir de la règle de formation des suites de nombres rationnels a_n, b_n dans (A).(B)

À condition d’adopter la convention selon laquelle les décimales de nombres de la forme m/2ⁿ se termineront par une infinité de zéros, le procédé suivant permet de voir que la proposition (B) est fausse : soit une machine N quelconque, c_n = <math>\frac{1}{2}</math> si N n’a encore imprimé aucun chiffre 0 lorsqu’elle atteint sa n-ième configuration complète, c_n = <math>\frac{1}{2}</math> - 2^-m-3 si N a imprimé 0 pour la première fois dans sa m-ième [546] configuration complète (m ≤ n), puis a_n = c_n – 2^-n-2 et b_n = c_n + 2^-n-2. Les inégalités de la proposition (A) sont alors satisfaites, et le premier chiffre de α (limite de c_n) est 0 si N imprime 0 au moins une fois, et 1 dans le cas contraire. Si la proposition (B) était vraie, nous aurions un moyen de connaître le premier chiffre de α étant donné le N.D de N : i.e. nous serions capables de déterminer si N imprime jamais 0, ce qui est contraire aux résultats de § 8 de l’article cité. Ainsi, bien que (A) montre qu’il doit exister des machines qui calculent, par exemple, la constante d’Euler, nous ne pouvons pas pour le moment décrire une telle machine, car nous ne savons pas encore si cette constante est de la forme m/2ⁿ.

Il est possible d’échapper à cette situation inconfortable en modifiant la manière dont les nombres calculables sont associés aux suites calculables, tout en préservant intégralement l’ensemble des nombres calculables. Il est possible de le faire de nombreuses manières<ref name="ftn22"> À l’origine, cette utilisation des intervalles d’imbrication pour la définition des nombres réels est due à Brouwer.</ref>, dont voici un exemple. Soit i le premier chiffre d’une suite calculable γ, suivi de n fois le chiffre 1, d’un 0, puis de la suite dont le r-ième chiffre est c_r ; on fait correspondre à la suite γ le nombre réel rγ :

rγ = (2i – 1) n + <math>\sum _{r=1}^{\infty }\left(2cr\endash 1\right)\left(\frac{2}{3}\right)r</math>.

Si l’on considère que la machine qui calcule la suite γ calcule aussi le nombre réel rγ, alors (B) est une proposition vraie. L’unicité de représentation des nombres réels par des suites de chiffres est brisée, mais ceci a peu d’importance théorique, puisque les N.D ne sont pas invariablement uniques.

Graduate College,

Princeton, N.J., U.S.A.

---

<references/>