[Cet article a été publié pour la première fois par Scott Aaronson sous le nom Who Can Name The Bigger Number ? sur son propre site et est traduit et publié ici avec l'aimable autorisation de l'auteur.]
Commencons par une vieille plaisanterie : deux nobles se mettent au défi de donner un nombre plus grand que l'autre. Le premier, après avoir réfléchi pendant des heures annonce triomphalement "Quatre-vingt-trois". L'autre, très impressionné, répond "Vous avez gagné".
Un concours du nombre le plus grand est manifestement sans intérêt si l'on joue l'un après l'autre. Mais et si l'on demandait aux deux joueurs d'écrire leur nombre simultanément, sans qu'aucun ne sache ce que l'autre a écrit ? J'invite donc deux volontaires à se prêter à un jeu dont voici la règle :
Vous avez exactement quinze secondes pour écrire un nombre entier (non infini) en utilisant des notations mathématiques, des mots ou les deux sur une ardoise vierge. Soyez suffisament précis pour qu'un mathématicien moderne et raisonnable puisse déterminer exactement quel est le nombre que vous avez désigné en consultant votre ardoise uniquement et, si nécessaire, la littérature académique.
Les participants ne peuvent donc pas invoquer "le nombre de grain de sables dans le Sahara" parce que le sable se balade continuellement entre le Sahara et l'extérieur. Et ils ne peuvent pas non plus dire "Le nombre de mon adversaire plus un" ou "le plus grand nombre auquel quelqu'un ait jamais pensé plus un" puisqu'ils sont mal définis du point de vue de notre mathématicien et de ce qu'il a à sa disposition. Les règles étant respectées, c'est celui qui donne le nombre le plus grand qui remporte la partie.
A vos marques. Prêt ? Partez !
Les résultats des participants ne correspondent jamais à ce que j'en attends. Une fois, un garcon de cinquième a rempli son ardoise avec une file de 9. Comme bien souvent chez les débutants de ce jeu des Grands Nombres, il a cherché à maximiser son résultat en mettant des 9 partout où il pouvait. S'il avait choisi d'y mettre des 1, plus faciles à écrire que la boucle du 9, son nombre aurait pu être des millions de fois plus grand. Mais il se serait de toute manière fait ratatiner par celui de sa conccurente, qui avait écrit la même suite de 9 suivi de l'exposant 999. Ah Ah ! Une exponentiation : un nombre multiplié par lui-même 999 fois. Etant donné cette innovation, je déclarais la jeune fille gagnante sans même me préoccuper de compter les 9 sur les ardoises.
Et pourtant le nombre de la jeune fille aurait pu être beaucoup plus grand si elle avait empilé les puissants exposants les uns sur les autres. Prenez par exemple. Ce mastodonte, égal à 9387,420,489 possède 369,693,100 chiffres. A titre de comparaison, le nombre de particules élémentaires de notre univers possède à peine 85 chiffres. Trois 9, quand on les empile en exponentielle nous emmène bien au-delà de tout ce que nous pouvons imaginer un jour voir (et d'un facteur d'environ 10369,693,015). Et je ne parle même pas de
ou de
.
Les chiffres, les exposants ou les exposants empilés peuvent tous exprimer des nombres plus grands les uns que les autres, ce qui rend ces méthodes toutes plus ou moins équivalentes. Mais elles diffèrent en cela que certaines sont plus concises que d'autres. C'est pour cela que les règles imposent une limite de quinze secondes. On prend le même temps pour écrire 9999, 9999 ou et pourtant le premier est un nombre de tous les jours, le second est astronomique et le dernier hyper-mega astronomique. La clé vers la victoire du concours du nombre le plus grand ne revient donc pas à celui qui écrira le plus vite, mais à celui qui trouvera un modèle suffisament puissant pour capturer ces nombres gargantuesques le plus concisément possible.
Ce genre de modèles sont rares dans l'Histoire. On en trouve des tas dans l'Antiquité, des tas au XXe Siècle et pas grand chose entre les deux. Mais quand une nouvelle manière d'exprimer facilement de grands nombres, c'est toujours parce qu'une révolution scientifique majeure l'a engendrée : systématisation des mathématiques, logique formalisée, informatique. Et comme tout Kuhnien vous le dira, les révolutions de ce genre ne peuvent se déclencher que si le climat sociel s'y prête. L'histoire des grands nombres est donc l'histoire du progrès humain.
Et pour faire le parallèle avec une autre histoire mathématique, dans son livre Une histoire de , Peter Beckmann avance que le rapport de la circonférence sur le diamètre est "le parfait miroir de l'histoire de l'homme". Dans les rares sociétés où la science et la raison ont trouvé refuge, l'Athènes d'Anaxagores et d'Hippias, l'Alexandrie d'Eratosthenes et d'Euclide ou encore l'Angleteree du XVIIe de Newton et Wallis, les mathématiciens se sont toujours échinés à calculer
. A Rome et pendant le Moyen-âge, par contre, la connaissance de
n'a pas avancé. On se contentait alors des approximations des Babyloniens (25/8) voire de la Bible (3).
Le même genre de constatation est vrai également pour les grands nombres. La curiosité et l'ouverture d'esprit amènent à une fascination pour les grands nombres et à la prise de conscience que rien, pas même le nombre d'étoiles dans la galaxie n'est assez grand pour que l'esprit ne puisse les énumérer. A l'inverse, l'ignorance et l'irrationalité amène systématiquement à un fatalisme vis-à-vis des grands nombres. La Bible, par exemple, nous répète par ving-et-une fois que les grains de sables ne peuvent être comptés. "Et toi, tu as dit: Je te ferai du bien, et je rendrai ta postérité comme le sable de la mer, si abondant qu'on ne saurait le compter." (Genèse 32:12) ou encore "C'est pourquoi d'un seul homme, déjà usé de corps, naquit une postérité nombreuse comme les étoiles du ciel, comme le sable qui est sur le bord de la mer et qu'on ne peut compter."(Hébreux 11:12). Cette pensée que la multitude de grains de sable pourrait tout aussi bien être infinie et qu'elle est plus à même d'être un objet de stupide stupéfaction plutôt que de quantification est une pensée ancienne. L'historien Ilan Vardi cite à ce propos l'ancient grec "psammkosioi", littéralement sable-centaine que l'on traduit par zillions et un passage de l'Ode à Olympe de Pindar déclarant que "le sable échappe à tout comptage".
Mais le sable n'échappe pas au comptage comme le reconnaît Archimède trois siècles avant J-C. Ainsi commence L'Arénaire, une sorte d'article de vulgarisation destiné au Roi de Syracuse :
Il est des personnes, ô roi Gélon, qui pensent que le nombre des grains de sable est infini.[...] Quelques-uns croient que le nombre des grains de sable n'est pas infini, mais qu'il est impossible d'assigner un nombre plus grand.[...] Quant à moi, je vais faire voir par des démonstrations géométriques auxquelles tu ne pourras refuser ton assentiment,[..] qu'il est [des nombres] qui excèdent le nombre des grains d'un volume de sable égal non seulement à la grandeur de la terre, mais encore à celui de l'univers entier. [1]
Archimède s'éxécute ensuite, essentiellement en utilisant le mot grec myriad qui signifie dix mille, en tant que base de ses exponentiations. En partant d'un postulat cosmologique établi par Aristarchus, dans lequel la "Sphère des étoiles" est immensément plus grande que celle dans laquelle la Terre se déplace, Archimède parvient à majorer le nombre de grains de sable nécessaires pour remplir l'univers par 1063. (En anglais, 1063 est le plus grand nombre à posséder un nom standard (vingintillion, Decilliard en francais) surpassé seulement par l'eccentrique Googol valant 10100 et le googolplex, un 1 suivi de googol zéros, ). Mais aussi grand soit-il, notre 1063 n'était pas destiné à devenir Le Plus Nombre De Tous Les Temps... Six siècles plus tard, Diophantes développait une nouvelle notation pour les exponentielles, lui permettant de dépasser
. Puis, au Moyen-Âge, l'avènement des chiffres arabes et de la numération de position permirent de monter encore plus haut. Mais le manière d'Archimèdes pour exprimer les grands nombres ne fut pas surpassé avant le XXe siècle. Et aujourd'hui encore, les exponentiations remportent la palme populaire.
Prenons par exemple la légende bien connue du Grand Vizir de Perse qui inventa le jeu d'échec. Le Roi, nous dit la légende, était si content de ce nouveau jeu qu'il invita le Grand Vizir pour lui offrir la récompense de son choix. Le Vizir répondit qu'étant un homme humble, il désirait peu de chose : un grain de blé pour la première case, deux pour la seconde, quatre pour la troisième et ainsi de suite, tel que sur chacun des cases suivantes, il y ait exactement deux fois plus de grain que sur la précédente. Le Roi, illétré, accepta, sans réaliser que le nombre de grains de blé à placer sur les 64 cases serait de 264-1, soit environ 18,6 trillions de grains, l'équivalent de la production mondiale actuelle pendant 150 ans.
C'est cette même croissance exponentielle qui rend le jeu d'échec si difficile. Le nombre de mouvements autorisés à chaque instant est d'au maximum 35, mais tous ces choix se combinent jusqu'à produire 1050 positions possibles, bien trop pour que même un ordinateur puisse les passer toutes en revue une à une. C'est pour cela qu'il a fallu attendre 1997 et Deep Blue pour que la machine batte enfin le champion du monde humain. Et pour le Go avec son plateau de 19x19, les combinaisons possibles sont de 10150 et même un amateur peut battre haut la main les meilleurs programmes disponibles. La croissance exponentielle est le fléau des ordinateurs de bien d'autres manières. Le Problème du Commis Voyageur consiste à trouver le chemin le plus court passant par toutes les villes d'un secteur, connaissant les distances des routes possibles entre chaque ville. Le problème, c'est que le nombre de route croit exponentiellement avec le nombre de villes. Quand il y a, disons, cent villes, on peut trouver 10158 chemins différents et, bien que des raccourcis soient possibles, aucun algorithme connu ne sait faire mieux que regarder chacun des chemins un par un. Le Problème du Commis Voyageur appartient à une classe de problèmes que l'on appelle NP-Complet, dans laquelle se trouvent également des centaines d'autres problèmes d'intérêt pratique. NP sont les initiales du terme technique "Nondeterministic Polynomial-Time" (Temps Polynomial Non-déterministe). On sait que si l'on trouve un algorithme efficace pour n'importe lequel de ces problèmes NP-Complet, alors on saura en trouver un chacun d'entre eux. Quand je dis "efficace", cela signifie que le temps nécessaire à la résolution doit être au pire proportionnel à une puissance fixée de la taille du problème, par exemple le cube du nombre de villes. Il y a une conjecture cependant, qui affirme qu'il n'existe aucun algorithme efficace capable de résoudre les problèmes NP-Complet. Prouver cette conjecture, , est l'un des plus grands problèmes non-résolus de l'Informatique théorique depuis plus de 30 ans.
Mais même si les ordinateurs ne pourront probablement jamais résoudre les problèmes NP-Complet, tout espoir n'est pas perdu pour un autre Graal de l'informatique : copier l'intelligence humaine. Le cerveau humain possède une centaine de milliards de neurones connectés par environ mille fois plus de connections synaptiques. Et bien que l'on ne connaisse que partiellement le fonctionnement des neurones individuels, on pense que chaque neurone renvoie des impulsions électrique en se basant sur quelques règles très simples environ un millier de fois par seconde. Nous sommes donc devant un ordinateur super-connecté capable d'environ 1014 opérations par seconde ; à titre de comparaison l'ordinateur le plus puissant du monde, Blue Gene/L d'IBM possède une capacité à peut près équivalente, mais occupe tout un étage d'un batiment du Ministère Américain à la Sécurité Nucléaire, en Californie [à l'époque de rédaction de l'article, le plus puissant ordinateur était capable de 1012 opérations. NdT]. Contrairement à la croyance populaire, la matière grise n'est pas seulement concue pour l'intelligence, elle surpasse également le silicium en puissance de calcul. Mais cela risque de ne pas durer très longtemps. La raison de ce fait est la Loi de Moore, telle qu'énoncée en 1990 et qui affirme que la quantité d'information stockable sur une puce électronique double tous les deux ans environ. La Loi de Moore devrait finalement s'éffondrer lorsque la taille des composants atteindront la taille atomique et que les techniques de gravure atteindront leur limite. Mais de toutes nouvelles technologies comme les ordinateurs optiques, à ADN voire les ordinateurs quantiques pourraient potentiellement détrôner le silicon. La croissance exponentielle de la puissance de calcul ne peut pas continuer à jamais, mais il est fort possible qu'elle continue suffisament longtemps pour que les ordinateurs surpassent les humains, ne serait-ce qu'en terme de puissance de calcul.
Pour les prophêtes de l'Intelligence Artificielle, la Loi de Moore est la glorieuse bannière de la croissance exponentielle. Mais les exponentielles ont aussi leur mauvais côté. La population humaine a dépassé six milliards il y a peu et double tous les quarante ans anviron. A ce rythme, si on considère qu'une personne pèse en moyenne soixante-dix kilos, eh bien en 3750 la Terre entière devrait être composée de chaire humaine. Mais avant de courrir investir dans les déodorants, réfléchissez une seconde : la population aura cessé d'augmenter bien avant ca, à cause de famines, d'épidémie, du réchauffement climatique, de l'extinction des espèces, de l'irrespirabilité de l'air ou, dans le champs des spéculations, de la limitation des naissances. Il n'est pas dur de deviner pourquoi le physicien Albert Bartlett a déclaré que "la plus grosse erreur de la race humaine" a toujours été "notre incapacité à comprendre la fonction exponentielle". Ou pourquoi Carl Sagan nous recommandait de ne "jamais sous-estimer une exponentielle". Dans son livre Billions & Billions, Sagan nous donne d'autres conséquences tout aussi déprimantes de la croissance exponentielle. Avec un taux d'inflation de cinq pourcent par an, un dollar ne vaut plus que trente-sept cents après 20 ans. Si un noyau d'uranium émet deux neutrons, ces deux là iront frapper deux autres noyaux, entrainant ceux-là à en émettre deux nouveaux et ainsi de suite... hmm, je crois que j'ai oublié "holocauste nucléaire" dans la liste des causes susceptibles d'arrêter l'accroissement de la population...
Les exponentielles sont familières, intégrées intimement dans le monde physique, rattachées aux peurs et aux espoirs de l'homme. En utilisant quelques systèmes de notation que j'expose plus bas, on peut cependant écrire de manière concise des nombres qui rendent les exponentiels complètement ridicule en comparaison, qui représentent philosophiquement des choses qui sont à ce que ce dernier est à 9. Mais ces notations peuvent sembler bien plus absconses que les exponentiels. Dans son essai "On Number Numbness" (Sur l'Indifférence des Nombres), Douglas Hofstadter emmène ses lecteurs jusqu'au bord du précipise puis recule en déclarant :
S'il fallait continuer cette discussion pendant encore une zilliseconde, nous nous retrouverions dans le marécage de la théorie des fonctions récursives et de la complexité algorithmique, et tout cela serait trop abstrait. Donc arrêtons-nous là.
Mais s'arrêter là, c'est s'avouer vaincu, non seulement dans notre concours du Plus Grand Nombre, mais c'est également abandonner tout espoir de jamais comprendre comment des modèles plus puissants nous amène à des nombres encore plus grands. Et nous voilà arrivé au tout début du XXe siècle, lorsqu'une nouvelle école de mathématiciens que l'on appelle les formalistes décidèrent de replacer toutes les mathématiques sur des bases axiomatiques solides. Une question fondamentale des formalistes était de trouver une bonne définition pour le mot "calculable". C'est-à-dire, comment peut-on dire si une séquence de nombres peut-être décrite par un procédé mécanique ? Certains mathématiciens pensaient que "calculable" coïncidait avec une autre notion : "primitive recursive". Mais en 1928, Wilhelm Ackermann leur prouva le contraire en exhibant une séquence de nombres clairement calculable mais qui en même temps grandit beaucoup trop vite pour être primitive recursive.
L'idée d'Ackermann fut de créer une suite sans fin d'opérations arithmétiques, chacune plus puissante que la précédente. En premier, l'addition. Puis en second, la multiplication, qui peut être vue comme une addition à répétition, signifie 5 additionné à lui-même 3 fois : 5+5+5=15. En troisième, on a l'exponentiation, qui est une succession de multiplications répétées. Et en quatrième... quoi donc ? Eh bien nous devons inventer une nouvelle opération bizarre, une succession répétée d'exponentiation. Le mathématicien Rudy Rucker appelle cela une "tétration" [J'appelle ca une "tour d'exponentielle". NdT]. Par exemple, "5 tétraté par 3" signifie "5 exponentié par lui même trois fois" :
, un nombre à 2,185 chiffres. Et on peut continuer. Pour la cinquième étape, on effectue des tétrations répétées (une "pentation" ??). Puis pour la sixième, des pentations répétées (une "hexation" ?). Et ainsi de suite infiniement, chaque étape reposant sur son prédécesseur pour monter encore plus haut dans le firmament des grands nombres.
Si chaque opération était une saveur de bonbon, alors la séquence d'Ackermann serait un paquet d'échantillon, mélangeant un nombre pour chaque goût. Le premier de notre suite est 1+1 qui est égal à (suspense insoutenable) 2. Le deuxième est . Et le troisième, 3 à la puissance 3, ce qui nous donne 27. Hé ! Mais ces nombres sont tout petits !
La Lala lalala La La
Le quatrième est 4 tétraté par 4, et possède 10154 chiffres. Si vous avez l'intention d'écrire ce nombre, je vous recommande de commencer tout de suite. Le cinquième, c'est 5 pentaté par 5,
avec "5 pentaté par 4" dans la pile. Ce nombre est bien trop colossal pour être décrit en termes ordinaires. Et les nombres deviennent encore plus gros après ca.
En dégaînant la Suite d'Ackermann, nous sommes sûr d'anihiler n'importe quel adversaire inéduqué dans notre concours. Mais nous devons faire attention, parce qu'il existe de nombreuses définitions différentes de la Suite d'Ackermann. Avec notre limite imposée de quinze secondes, voilà ce que j'écrirais pour éviter toute ambiguité :
A(111) — Ackermann seq — A(1) = 1+1 ; A(2)= ; A(3) = 33 ; etc...
Aussi obscure puisse-t-elle sembler, la Suite d'Ackermann a en fait quelques application. Il existe une branche des mathématiques appelée la Théorie de Ramsey, dans laquelle l'un des problèmes consiste à trouver la dimension minimale pour qu'un hypercube satisfasse une certaine propriété. On pense que la véritable solution est 6, mais la plus petite dimension pour laquelle on ait jusqu'à présent réussi à le prouver est si énorme que seul "l'arithmétique bizarroïde"de la Suite d'Ackermann peut la qualifier.Le Guinness Book des Records l'a même listé comme étant le plus grand nombre jamais utilisé dans une preuve mathématique. Un conccurent à ce titre fut le Nombre de Skewes, valant à peu près qui apparaît dans l'étude de la manière dont les nombres premiers sont distribués. Le mathématicien célèbre G.H.Hardy l'avait alors qualifié de "plus grand nombre servant réellement à quelquechose en mathématiques". Qui plus est, la Suite d'Ackermann fait même une brêve incursion dans le monde de l'informatique théorique. Dans l'analyse d'une structure de donnée que l'on appelle "Union-Find", on se retrouve à manipuler l'inverse de la Suite d'Ackermann, c'est à dire, pour chaque nombre X, le plus petit N tel que A(N) soit plus grand que X. Cet inverse grandit aussi lentement que la Suite elle-même grandit vite. En pratique, on ne dépasse jamais 4.
Les nombres d'Ackermann sont relativement grands, mais pas encore assez. La quête pour des nombres encore plus gros nous ramène une fois de plus aux formaliste. Après qu'Ackermann ait démontré que "primitive récursif" ne correspond pas à "calculable", la question restait entière : Qu'est-ce qu'on entend par "calculable" ? En 1936, Alonzo Church et Alan Turing répondirent indépendament à cette question. D'un côté, Church inventa le lambda-calcul, un formalisme logique et de l'autre inventa une machine à calculer idéale (la Machine de Turing) qui, en essence, est équivalente à n'importe quel Compaq, Dell, Macintosh ou Cray de notre monde moderne. L'article de Turing dans lequel il décrit sa machine "On Computable Numbers" ("Sur les Nombres Calculables") est unanimement reconnu comme le document fondant l'informatique.
"Calculer," dit Turing,
se fait normalement en écrivant certains symboles sur une feuille de papier. On peut supposer que ce papier est divisé en petits carrés comme un cahier d'enfant. En arithmétique élémentaire, le caractère bidimensionnel de la feuille est parfois utilisé. Mais ces usages peuvent toujours être éviter et je pense qu'il sera admis que ce caractère bidimensionnel n'est pas essentiel au calcul. Je pars donc du principe que notre calcul est fait sur une feuille unidimensionnelle, une bande divisée en petit carrés.
Turing continue ensuite à exposer sa machine en utilisant des raisonnement ingénieux à partir des principes premiers. La bande, dit Turing, s'étend infiniement dans les deux directions, une machine théorique ne devant pas être limitée par des ressources physiques. De plus, dans chaque case de notre bande est écrit un symbole, un peu comme les 1 et les 0 dans les mémoires de nos ordinateurs modernes. Comment ces symboles sont-ils manipulés ? Eh bien, la machine est munie d'une "tête de lecture" qui se déplace le long de la bande, examinant un carré à la fois, écrivant et effacant des symboles en suivant des règles définies. Ces règles sont le programme de la tête de lecture : en les changeant, on change le comportement de la tête de lecture.
L'idée géniale de Turing fut de dire que l'on peut programmer la tête de lecture pour qu'elle puisse accomplir n'importe quel calcul. Les Machines de Turing peuvent additionner, multiplier, extraire les racines cubiques, classer, chercher, vérifier l'orthographe, traiter des données, jouer au Morpion ou donner la Suite d'Ackermann. En imaginant des symboles pour l'entrée au clavier, la sortie écran et tout le reste, on pourrait même faire tourner Windows sur une Machine de Turing. Mais il y a un problème. Posez une tête de lecture sur une séquence de symboles et peut-être s'arrêtera-t-elle, ou peut-être continuera-t-elle perpétuellement, comme dans l'histoire du programmeur bloqué sous la douche parce que la notice de sa bouteille de shampooing indique "Appliquer, Rincer, Recommencer". Si la machine a prévu de tourner pendant un temps infini, ce serait sympathique qu'on puisse nous prévenir à l'avance, que nous n'attendions pas jusqu'à la fin de l'éternité qu'elle s'arrête finalement. Mais comment déterminer, en un temps fini, si quelquechose est susceptible de se produire perpétuellement ? Si vous pariez avec un ami que votre montre ne s'arrêtera jamais de battre, quand pourrez-vous décider de la victoire ? A moins qu'il n'existe un programme ingénieux quelquepart qui puisse examiner des programmes et nous dire, sans jamais se tromper, si ils vont jamais s'arrêter. Un auquel nous n'aurions pas pensé jusqu'à maintenant...
Bah non. Turing a démontré que ce probleme, que l'on appelle le Problème de l'Arrêt, ne peut pas être résolu par des Machines de Turing. La preuve est un très bel exemple d'auto-référence. Elle formalise un vieil argument disant qu'il est impossible d'avoir une introspection parfaite : parce que si vous pouviez, alors vous pourriez déterminer ce que vous aller faire dix secondes plus tard, et ensuite, faire autre chose. Turing imagine l'existence d'une Machine spéciale qui pourrait résoudre le Problème de l'Arrêt. Ensuite, il montre que cette Machine devrait pouvoir s'analyser elle-même de telle manière qu'elle s'arrête si elle tourne indéfiniment, et continue à tourner si elle s'arrête. Comme un chien poursuit sa queue et entreprend de se dévorer lui-même, la mythique machine se dissout dans une tornade de contradiction. (C'est le genre de chose que l'on ne peut pas écrire dans un article de recherche.)
"Très bien" vous dîtes-vous (ou peut-être "Pas bien du tout"). "Mais qu'est-ce que ca a à voir avec les grands nombres tout ca ?" Aha ! La connection ne fut publiée qu'en mai 1962. Alors, dans le Bell System technical Journal, perdu entre quelques articles fort pragmatiques sur les "Strutures Multiport" et les "Portes Pressurisées à Guide d'Onde" se cachait un article modestement titré "On Non-Computable Functions" ("Sur les fonctions non-calculables") par Tibor Rado. Dans cet article Rado nous présente les plus grands nombres jamais imaginés.
Son idée était simple. De la même manière que l'on peut classer les mots en fonction du nombre de lettres qu'ils contiennent, alors il est possible de classer les Machines de Turing en fonction du nombre de règles contenues dans la tête de lecture. Il y a des machines avec une seule règle, d'autres avec deux, trois et ainsi de suite. Mais pour chaque nombre entier N, de la même manière qu'il n'y a qu'un nombre fini de mots avec N lettres, il y a un nombre fini de machines à N règles. Parmi ces machines, certaines s'arrêtent, d'autres tournent indéfiniment si on les place sur un bande vierge. Parmi celles qui s'arrêtent, demande Rado, quel est le nombre maximal de pas que cette machine peut faire avant de s'arrêter ? (En fait, Rado demandait le nombre maximal de symbole qu'une machine pourrait écrire avant de s'arrêter. Mais le nombre maximal de pas, que Rado appelait S(n) a les mêmes propriétés et est plus facile à manipuler.)
Rado appelle ce maximum le Nème "Castor Affairé" ["Busy Beaver"] (eh oui, le début des années 1960 était un âge plein d'innocence). Il imagine chaque Machine de Turing comme un castor occupé à papilloner le long de la bande, écrivant et effacant des symboles. Le challenge est alors de trouver le castor le plus affairé parmi ceux qui suivent N règles. En évitant ceux qui sont occupés indéfiniment. On peut comprendre ce challenge comme une tentative de trouver le programme le "plus compliqué" de N bits : un programme qui fera le maximum de chose, tant que cela se termine un jour.
Maintenant, supposons que nous connaissions le Nème Castor Affairé, que nous appelerons BB(N) [pour BusyBeaver. NdT]. Alors nous pourrions savoir à coup sûr si une Machine de Turing à N instructions s'arrête ou non si on lui fournit une bande vierge. Il suffit alors de faire tourner la machine : si elle s'arrête, alors on a notre réponse; mais si elle ne s'arrête pas une fois passé la borne BB(N) alors on sait qu'elle ne s'arrêtera jamais, puisque BB(N) est le nombre maximum d'étape qu'un programme puisse faire avant de s'arrêter. De la même manière, si vous pouviez affirmer que tous les mortels meurent avant l'âge de 200 ans alors si Coralie a vécu plus de 200 ans, alors nécessairement Coralie est immortelle. Donc aucune Machine de Turing ne peut donner la liste des Castors Affairés. Puisque si c'était possible, alors on pourrait résoudre le Problème de l'Arrêt, et nous avons déjà prouvé que c'était impossible.
Mais voilà un fait curieux. Supposons que nous puissions nommer un nombre plus grand que le Nème Castor Affairé BB(N). Appelons le D comme digue [D pour Dam (barrage) en anglais. NdT], puisque, comme les digues que construisent les castors, elles sont un toit pour tous les Castors Affairés en-dessous. Avec D en poche, calculer BB(N) devient facile : il suffit alors de simuler toutes les Machines de Turing à N règles. Toutes celles qui ne se sont pas arrêtés après D étapes (celles qui ont percé le toit de notre digue) ne s'arrêteront jamais. Alors nous pourrons lister exactement toutes les machines qui s'arrêtent, et pour celles-là, regarder quel est le nombre maximum d'étapes accomplies avant de s'arrêter : le plus grand est BB(N).
Conclusion ? La suite des Castors Affairés, BB(1), BB(2) etc... croit plus vite que n'importe quelle suite calculable. Plus vite que les exponentielles, que les tours d'exponentielle, la Suite d'Ackerman, ce que vous voulez. Puisque si une Machine de Turing était capable de calculer une séquence croissant plus vite que les Castors Affairés, alors elle pourrait utiliser cette séquence pour obtenir les D, nos digues. Et avec ces D, elle pourrait donner la liste BB(N) des Castors Affairés ! Ce qui (vous avez pris l'habitude ?) nous le savons est impossible ! La suite des Castors Affairés croit de manière stupéfiquement rapide, trop rapidement pour qu'aucun ordinateur ne puisse la rattraper, même en théorie.
Ce qui signifie qu'il n'existe aucun programme qui puisse lister tous les Castors Affairés un à un. Cela ne veut pas dire pour autant que les Castors Affairés particuliers doivent rester inconnus à jamais. Et même, les trouver à été un passe-temps des informaticiens théoriques depuis que Rado a publié son article. Il est facile de voir que BB(1), le premier Castor Affairé, est 1. Puisqu'avec une machine de Turing à une seule règle, si la Machine ne s'arrête pas après la première (et seule) instruction, alors elle continuera de bouger le long de la bande indéfiniment. On ne peut rien imaginer de plus complexe avec si peu d'instructions. Avec deux instructions, on peut faire plus et un peu de travail nous montre que BB(2) vaut 6. 6 étapes. Et le Troisième Castor Affairé ? En 1965, Rado et Shen Lin ont prouvé que BB(3) vaut 21. La tâche fut ardue, demandant une analyse humaine de nombreuses machines pour prouver qu'elles ne s'arrêtaient pas (puisque, rappelez-vous, il n'existe aucun algorithme pour faire ce travail à votre place). Puis en 1983, Allan Brady démontra que BB(4) vaut 107. Sceptique ? Eh bien, comme avec la Suite d'Ackermann, ne vous laissez pas avoir par les premiers nombres.
En 1984, A.K. Dewdney écrivait un dossier complet pour Scientific American sur les Castors Affairés qui inspira le mathématicien amateur George Uhing dans la conception d'un engin spécial simulant des Machines de Turing. Cet appareil, qui coûta à Uhing un peu moins de $100, trouva une machine à cinq règles capable de tourner sur 2,133,492 itérations avant de s'arrêter, montrant que BB(5) doit nécessairement être plus grand que ca. Puis, en 1989, Heiner Marxen et Jürgen Buntrock découvrirent que BB(5) était plus grand que 47,176,870. A ce jour BB(5) n'a toujours pas été trouvé exactement et pourrait très bien s'avérer être beaucoup plus grand [D'après la Wikipédia, c'est le record de Marxen et Buntrock qui tient toujours. NdT]. Quant à BB(6), les mêmes prouvèrent un nouveau record en 1997 en montrant que BB(7) était forcément plus grand que 8,690,333,381,690,951. Un formidable accomplissement et pourtant Marxen, Buntrock et les autres chasseurs de Castors Affairés pataugent seulement sur les côtes de l'inconnaissable. L'humanité ne connaîtra peut-être jamais la valeur de BB(6) assurément, sans parler de BB(7) ou de n'importe quel autre dans la suite.
En effet, nous sommes déjà surpassés par les Castors à cinq et six instructions : nous ne pouvons même pas expliquer comment ils "fonctionnent" en termes humains. Si la créativité est responsable de leur design, ce n'est certainement pas parce que les humains les ont mis là. Une manière de comprendre ceci tient dans le fait que même des Machines de Turing très petites peuvent encoder des problèmes mathématiques très profonds. Prenez la Conjecture de Goldbach par exemple, qui dit que tout nombre pair supérieur ou égal à 4 est la somme de deux nombres premier : 10=7+3, 18=13+5. Cette conjecture résiste à toutes les tentatives de démonstration depuis 1742. Et pourtant, nous pouvons créer une Machine de Turing à 100 instructions qui teste chaque nombre pair pour voir si il est somme de deux premiers, et s'arrête si elle trouve un contre-exemple à la conjecture. En connaissant BB(100), il serait alors possible de faire tourner la machine pendant BB(100) itérations, voir si elle s'arrête et ainsi résoudre la conjecture de Goldbach. Pas besoin d'aller bien loin dans cette suite pour pénétrer dans l'Antre des Basiliques.
Mais, comme insiste Rado, même si nous ne pouvons pas les donner tous, les Castors Affairés sont parfaitement définis mathématiquement. Si un jour vous jouez avec un ami au Jeu du Plus Grand Nombre, je vous suggère d'écrire quelquechose du genre :
BB(11111) - Busy Beaver shift - 1,6,21 etc...
Si votre ami ne sait rien à propos des Machines de Turing mais connait seulement, par exemple, les nombres d'Ackermann, alors vous êtes sûr de gagner. Vous gagnerez même en laissant à votre adversaire un léger handicap en lui laissant tout le temps nécessaire jusqu'à la mort de l'Univers pour écrire son nombre. La clé pour obtenir le plus grand nombre tient dans notre puissant modèle, et la théorie de la calculabilité de Turing est pour le moins puissante.
Mais que faire si votre ami sait la même chose que vous à propos des machines de Turing ? Existe-t-il un système de notation encore plus puissant que les Castors Affairés ?
Supposons que nous puissions invoquer une Machine de Turing avec la pouvoir magique de résoudre le Problème de l'Arrêt. Qu'est-ce que nous obtiendrons ? Eh bien, une "Super Machine de Turing" : une machine dotée de pouvoirs que n'ont pas les machines ordinaires. Et maintenant, est-ce si difficile de décider de l'arrêt d'une super machine ? Hmmm. Eh bien il se trouve que même les super machine ne peuvent résoudre le "Super Problème de l'Arrêt", pour la même raison que les machines ordinaires ne peuvent décider l'Arrêt des machines ordinaires. Pour résoudre le Problème de l'Arrêt des Super Machines, il faudrait une Extra Super Machine de Turing. Et pour résoudre le Problème de l'Arrêt des Extra Super Machines, il faudrait une Choupa Extra Super Machine et ainsi de suite jusqu'à ce que mort s'ensuive. Cette hierarchy infinie de machines plus puissantes fut formalisée par le logicien Stephen Kleene en 1943 (sans utiliser le terme "Choupa Extra Super").
Imaginez un roman, inclu dans un roman plus long, lui même inclu dans un roman encore plus long etc jusqu'à l'infini. Dans chaque roman, les personnages peuvent débattre des mérites littéraire de n'importe lesquels des sous-romans. Mais, par analogy avec les classes de machines qui ne peuvent s'analyser elles-mêmes, les personnages ne peuvent jamais critiquer le roman dans lequel ils se trouvent eux-même. (Ce qui correspond, je pense, aux romans dont nous avons l'habitude). Pour comprendre pleinement une réalité, il faut pouvoir sortir de cette réalité. C'est l'essence de la hiérarchie de Kleene : le seul moyen de résoudre le Problème de l'Arrêt pour une classe de machine donnée est de faire appel à une classe de machines plus puissantes.
Et il n'y a pas d'échappatoire. Supposons qu'une Machine de Turing ait le pouvoir magique de résoudre le Problème de l'Arrêt et le Super Problème de l'Arrêt et l'Extra Super Problème de l'Arrêt et le Choupa Extra Super Problème de l'Arrêt et ainsi de suite. Cette machine serait certainement la Reine des Machines de Turing. Pas vraiment : en effet, dès qu'il s'agira de décider du Royal Problème de l'Arrêt, alors il nous faudra une Impératrice des Machines de Turing. Et la hiérarchie de Kleene se poursuit.
Quel donc est le rapport avec les grands nombres ? Eh bien, pour chaque niveau de la hiérarchie de Kleene nous avons des Castor encore plus Affairés à chaque fois par rapport au niveau inférieur. En effet, les suites correspondant à chaque niveau croissent si vite qu'elles ne peuvent être calculées que par des machines d'un niveau supérieur. Définissons par exemple BB2(N) le nombre maximum d'étapes qu'une Super Machine à N instructions peut effectuer avant de s'arrêter. Si cette suite était calculable par une Super Machine, alors ces machines pourraient résoudre le Problème de l'Arrêt, ce qui, nous le savons, est impossible. Donc les Castors Super Affairés croissent trop rapidement pour être calculés, même si l'on pouvait calculer les Castors Affairés Ordinaires.
Vous pensez probablement maintenant que pour battre un adversaire qui connait les Castors Affairés il vous suffit d'écrire quelquechose du genre :
BB2(11111).
Mais pas vraiment. Le problème est que je n'ai jamais vu ces Castors Hautement Affairés définis nulle part, probablement parce que pour les gens qui s'y connaissent en théorie de la calculabilité, ils sont une extension triviale des Castors Affairés Ordinaires. Donc notre mathématicien moderne ne saura pas quel nombre vous avez nommé. Si vous voulez utiliser ces Castors Hautement Affairés dans votre concours, voici une solution : D'abord, publiez un article formalisant ce concept dans quelque obscure revue de peu de prestige, puis, au moment du jeu, citez l'article sur votre ardoise.
Pour aller au-delà des Castors Affairés, il nous faudrait un modèle de calcul surpassant celui des Machines de Turing. Je n'ai pas la moindre idée de ce à quoi un tel modèle pourrait ressembler. Et pourtant, je doute que l'histoire des systèmes de notation pour les grands nombres est terminée. Un jour peut-être, des humains seront capable de nommer des nombres qui rendront en comparaison notre 100ème Castor Affairé aussi ridiculement puéril que le quatre-vingt-trois de notre noble. Et si nous n'y arrivons pas, alors peut-être une autre civilisation le fera. Pourquoi pas un Concours du Nombre Le Plus Grand Intergalactique ?
Vous vous demandez surement pourquoi on ne pourrait pas transcender tous ces modèles et donner des nombres en suivant un système qui comprendrait et les surpasserait tous. Supposons que que sur votre ardoise vous écriviez au moment du Jeu :
Le plus grand nombre entier désignable par un texte de 1000 caractères.
A coup sûr, ce nombre existe. En utilisant 1000 caractères, il n'est possible que de nommer un nombre fini de nombres, et parmi ceux-là, il y en a forcément un qui est le plus grand. Et pourtant nous n'avons fait aucune mention de la facon dont ce nombre est désigné. Le texte peut tout aussi bien évoquer les nombres d'Ackermann, les Castors Affairés ou Hautement Affairés voire de nouveaux concepts détonnants auxquels personne n'a jamais pensé jusqu'à maintenant... Donc à moins que votre adversaire n'utilise la même technique, vous l'avez certainement ratatiné. Quelle brillante idée ! C'est à se demander pourquoi on n'y a pas pensé avant.
Malheureusement, ca ne marche pas comme ca. On aurait tout aussi bien pu écrire :
Un plus le plus grand nombre entier désignable par un texte de 1000 caractères.
Il faut donc au moins 1001 caractères pour le désigner. Et... nous venons de le faire avec 78 caractères ! Et notre superbe nombre comme le serpent qui se mord la queue, de dissoudre dans un tumultes de contradiction. Pas très chouette.
Le paradoxe évoqué au-dessus fut publié pour la première fois par Bertrand Russell, qui l'attribua à un bibliothécaire du nom de G.G. Berry. Le Paradoxe de Berry ne provient pas des mathématiques mais de l'ambiguité intrinsèque du langage (anglais, francais etc...). Il n'y a aucune manière certaine de convertir une phrase anglaise en le nombre qu'elle désigne (voire même de savoir si elle désigne un nombre ou non) et c'est la raison pour laquelle je fais appel à un "mathématicien moderne et raisonnable" dans les règles du jeu. Pour contourner le Paradoxe de Berry, nous devons utiliser un système de notation précis, comme celui des Machines de Turing. C'est d'ailleurs exactement ce que nous avons fait pour exhiber les Castors Affairés. Il n'y a donc aucun raccourci du langage pour surpasser Archimèdes, Ackermann, Turing ou Rado sur l'autoroute des grands nombres.
Vous vous demandez également surement pourquoi nous ne pourrions pas utiliser l'infini dans notre jeu ? Pour la même raison que l'on ne peux pas participer à une course cycliste avec un bolide à réaction. L'infini est certes élégant et fascinant, mais ce n'est pas un nombre entier. Infini moins 17 est toujours infini, et infini moins infini est indéfini : cela peut être 0, 47 voire toujours l'infini. En fait, je devrais dire les infinis, au pluriel. Car au dix-neuvième siècle, Georg Cantor démontra qu'il y avait différents niveaux d'infini : par exemple le nombre de point sur une ligne est plus grand que l'infini des nombres entier. Et en plus, de la même manière qu'il n'y a pas de plus grand nombre entier, il n'y a pas non plus de plus grand infini. Mais la quête des grands infinis est un peu moins compréhensible. Et on n'y fait pas appel à une succession de modèles, seulement à un seul : celui de Cantor.
Donc nous y voilà, à la frontière de la connaissance des grands nombres. Comme l'étudiant d'Euclide, vous vous demandez "Mais à quoi peut bien servir tout ca ?". Nous avons vu que les progrès dans les systèmes de notation sont le reflet de progrès dans des domaines plus large : les mathématiques, la logique ou l'informatique. Et pourtant, si un mirroir reflète la réalité, il ne l'influence pas pour autant. Même dans les mathématiques, les grands nombres sont bien souvent considérés comme des trivialités, leur étude un amusement de désoeuvré sans grandes implications. Je veux me poser en contradicteur, et déclarer que comprendre le grands nombres, c'est en somme comprendre notre monde.
Imaginez que vous essayiez d'expliquer ce qu'est une machine de Turing à Archimèdes. Le génie de Syracuse vous écoute patiemment tandis que vous décrivez une bande de papyrus infiniment longue dans les deux directions, les étapes, les états de la tête de lecture, les séquences d'entrée et de sortie... Puis finalement il ne peut se retenir.
"Balivernes !", s'écrie-t-il (ou l'équivalent en Grec ancien). "Tout ce que vous me donnez est une définition certes élaborée mais qui n'a aucun intérêt en dehors d'elle même."
Que répondre ? Archimèdes n'a jamais entendu parlé d'ordinateurs, ces appareils insupportables qui, vingt-trois siècles plus tard gèreront les affaires du monde. Impossible donc d'évoquer des applications pratiques. Pas plus que vous ne pouvez mentionner Hilbert et les formalistes, puisqu'Archimèdes n'en a pas non plus entendu parler... Puis vous pensez à la Suite des Castors Affairés. Vous définissez la Suite pour Archimèdes, lui prouvez que BB(1000) vaut bien plus que ses 1063 grains de sable nécessaires pour remplir l'univers, bien plus même que 1063 élevé à sa propre puissance 1063. Et vous le défiez de pouvoir vous donner un nombre plus grand sans faire appel à une Machine de Turing ou un équivalent. Et tandis qu'il réfléchit à ce petit pari, la puissance des Machines de Turing lui apparaît enfin. Son intuition ne pourra probablement jamais appréhender les nombres de la Suite des Castors Affairés mais sa raison lui fera reconnaître leur immensité. Les grands nombres sont un moyen d'inclure des notions abstraites dans la réalité.
En effet, on pourrait définir la science comme une tentative de la raison de combler notre incapacité à percevoir les grands nombres. Si nous pouvions courrir à 280'000'000 mètres par seconde, il n'aurait jamais été nécessaire de développer une théorie spéciale pour la relativité : ce serait évident pour tout le monde que plus l'on va vite, plus l'on devient lourd et disproportionné et plus le temps s'écoule rapidement par rapport au reste du monde. Si nous pouvions vivre 70'000'000 ans, plus besoin de Théorie de l'Evolution, et très certainement aucun créationniste : nous aurions vu l'apparition des espèces et leurs adaptations de nos propres yeux, au lieu d'avoir à reconstituer laborieusement les évènements passés en se basant sur des fossiles et de l'ADN. Si l'on pouvait faire cuire du pain à 20'000'000 degrés Kelvin, alors la fusion nucléaire ne serait pas un domaine si ésotérique destinés aux physiciens, mais accessible à n'importe quelle ménagère. Mais toutes ces choses nous sont impossibles, donc nous avons la science pour comprendre ces géants que nous ne pourrons jamais sentir à l'aide de nos ridicules facultés. Si les gens craignent les grands nombres, aucune surprise à qu'ils craignent la science et se tournent vers la petitesse confortable du mysticisme.
Mais les gens ont-ils vraiment peur des grands nombres ? Bien sûr ! J'ai rencontré des tas de gens qui ne font pas la différence entre un million et un milliard et ne se posent pas plus de question. Nous jouons à une lotterie à "six chances de gagner" sans prêter attention aux vingt millions de chance de perdre. Nous baillons devant six milliards de tonnes de dioxyde de carbone rejeté dans l'atmosphère chaque année tout en parlant de "développement durable" au milieu d'une croissance exponentielle de la population. Ce genre de choses, me semble-t-il, va bien au-delà de la simple ignorance arithmétique et reflète une absence manifeste de volonté de se confonter au grand.
D'où vient cette lâcheté face aux grands nombres ? A-t-elle une origine biologique ? En 1999, un groupe emmené par le neuropsychologue Stanislas Dehaene écrivait dans Science qu'il avait trouvé des preuves que deux systèmes cérébraux indépendants conduisait au raisonnement mathématique. Ce groupe fit s'entraîner des bilingues russe-anglais à résoudre un groupe de problèmes, dont des addition à deux chiffres, des additions en base huit, des racines cubiques et des logarithmes. Certains suivait l'entraînement en anglais, d'autres en russe. Lorsque l'on demanda aux sujets de résoudre les problèmes de manière approximative (en choisissant parmi deux estimations par exemple), les résultats furent aussi bon dans chacun des langages. Lorsqu'on leur demanda de résoudre les problèmes de manière exacte, les résultats furent meilleurs lorsque les raisonnements se faisaient dans la langue d'apprentissage. De plus, l'imagerie cérébrale a montré que les lobes pariétaux des sujets, qui servent au raisonnement spatial, étaient plus actif pendant la résolution approximative ; alors que ce sont les lobes frontaux inférieurs, qui servent au raisonnement verbal, qui étaient les plus actifs dans la résolution exacte des problèmes. Des études de patiens avec des lésions au cerveau confirment ces vues : ceux avec des lésions pariétales ont souvent du mal à savoir si 9 est plus proche de 5 ou de 10, mais se souviennent de leurs tables de multiplication, là où ceux possédant des lésions de l'hémisphère gauche sont incapables de dire si 2+2 vaut 3 ou 4, mais affirment à coup sûr que le résultat est plus proche de 3 que de 9. Dehaene et son équipe conjecture que l'être humain se représente les nombres de deux manières différentes. Pour les approximations nous utilisons une "échelle mentale" qui est apparue il y a bien longtemps et que nous partageons probablement avec les animaux. Et pour les calculs exacts, nous utilisons des symboles numériques, apparus il y a peu de temps et, étant dépendant du langage, sont réservés aux humains. Cette hypothèse explique simplement les résultats de cette étude : la raison pour laquelle les sujets de l'expérience se débrouillaient mieux dans le langage de l'apprentissage des problèmes pour les calculs exacts mais pas pour les calculs approximatifs est simplement que les premiers font appel au centre du langage, tandis que les seconds font appel aux centres du repérage spatial.
Si l'hypothèse de Dehaene et son équipe est correcte, alors quelle est la représentation utilisée pour les grands nombres ? Surement la forme symbolique puisque l'échelle mentale humaine n'est certainement pas assez long pour même faire apparaître , 5 pentaté par 5 ou BB(1000). Et c'est là, je pense, qu'est le problème. Lorsque nous pensons à 3, 4 ou 7, c'est notre intuition spatiale qui nous guide, habitué depuis des millions d'années à voir 3 gazelles, 4 amis et 7 membres d'une tribu hostile. Mais lorsqu'il s'agit d'imaginer BB(1000) nous n'avons que le langage, cette nouveauté de l'évolution, pour nous guider. Les voies du cerveau pour représenter ces nombres nous conduise à des impasses. Et c'est peut-être pour cette raison que les gens ont peur des grands nombres.
Notre phobie des nombres pourrait-elle être contrecarré en s'y prenant plus tôt ? Que se passerait-il si les instituteurs de CE1 prenait une heure loin des techniques calculatoires et demandaient à leurs élèves "Comment faire pour désigner les très très grands nombres ?" Et ensuite leur parler des exponentielles, des tétrations, de la Suite d'Ackermann ou même des Castors Affairés : une jungle de nombres plus grands les uns que les autres, plus grands que n'importe quel nombre jamais concus, plus vaste que les idées aux limites de leur imagination.
Qui aura le plus grand nombre ? Celui qui aura la meilleure idée, la plus puissante, la plus profonde. Prêt ? Partez !
Références
Petr Beckmann, A History of Pi, Golem Press, 1971.
Allan H. Brady, "The Determination of the Value of Rado’s Noncomputable Function Sigma(k) for Four-State Turing Machines," Mathematics of Computation, vol. 40, no. 162, April 1983, pp 647- 665.
Gregory J. Chaitin, "The Berry Paradox," Complexity, vol. 1, no. 1, 1995, pp. 26- 30. At http://www.umcs.maine.edu/~chaitin/unm2.html.
A.K. Dewdney, The New Turing Omnibus: 66 Excursions in Computer Science, W.H. Freeman, 1993.
S. Dehaene and E. Spelke and P. Pinel and R. Stanescu and S. Tsivkin, "Sources of Mathematical Thinking: Behavioral and Brain-Imaging Evidence," Science, vol. 284, no. 5416, May 7, 1999, pp. 970- 974.
Douglas Hofstadter, Metamagical Themas: Questing for the Essence of Mind and Pattern, Basic Books, 1985. Chapter 6, "On Number Numbness," pp. 115- 135.
Robert Kanigel, The Man Who Knew Infinity: A Life of the Genius Ramanujan, Washington Square Press, 1991.
Stephen C. Kleene, "Recursive predicates and quantifiers," Transactions of the American Mathematical Society, vol. 53, 1943, pp. 41- 74.
Donald E. Knuth, Selected Papers on Computer Science, CSLI Publications, 1996. Chapter 2, "Mathematics and Computer Science: Coping with Finiteness," pp. 31- 57.
Dexter C. Kozen, Automata and Computability, Springer-Verlag, 1997.
———, The Design and Analysis of Algorithms, Springer-Verlag, 1991.
Shen Lin and Tibor Rado, "Computer studies of Turing machine problems," Journal of the Association for Computing Machinery, vol. 12, no. 2, April 1965, pp. 196- 212.
Heiner Marxen, Busy Beaver, at http://www.drb.insel.de/~heiner/BB/.
——— and Jürgen Buntrock, "Attacking the Busy Beaver 5," Bulletin of the European Association for Theoretical Computer Science, no. 40, February 1990, pp. 247- 251.
Tibor Rado, "On Non-Computable Functions," Bell System Technical Journal, vol. XLI, no. 2, May 1962, pp. 877- 884.
Rudy Rucker, Infinity and the Mind, Princeton University Press, 1995.
Carl Sagan, Billions & Billions, Random House, 1997.
Michael Somos, "Busy Beaver Turing Machine." At http://grail.cba.csuohio.edu/~somos/bb.html.
Alan Turing, "On computable numbers, with an application to the Entscheidungsproblem," Proceedings of the London Mathematical Society, Series 2, vol. 42, pp. 230- 265, 1936. Reprinted in Martin Davis (ed.), The Undecidable, Raven, 1965.
Ilan Vardi, "Archimedes, the Sand Reckoner," at http://www.ihes.fr/~ilan/sand_reckoner.ps.
Eric W. Weisstein, CRC Concise Encyclopedia of Mathematics, CRC Press, 1999. Entry on "Large Number" at http://www.treasure-troves.com/math/LargeNumber.html.