L'information, la Machine et le Programme | Peut-on tout programmer ? | La diagonale de Cantor

La démonstration qui permet d'établir que l'ensemble des fonctions de N dans N est un infini non dénombrable est à la fois simple, élégante et délicate. Dans l'esprit, elle est due à Georg Cantor mais nous allons en donner la version due à S.C.Kleene [1] dans son livre Mathematical Logic publié en France sous le titre Logique Mathématique.

Supposons que l'ensemble des fonctions de N dans N est un infini dénombrable, et soit f_i(n) la ième fonction de cet ensemble. Nous pouvons établir la liste de toutes ces fonctions sous la forme du tableau :

Une fois ce tableau établi, nous constatons qu'il est toujours possible d'y ajouter une nouvelle fonction construite à partir de tous les éléments de la diagonale de ce tableau et qui est différente de toutes les fonctions que ce tableau contient. Et, bien sûr, cette fonction ne peut pas être numérotée puisque tous les numéros sont déjà utilisés.

[1] Stephen Cole Kleene (pronounced "KLAY-nee") was born on January 5, 1909 in Hartford, Connecticut. He received a Bachelor of Arts degree from Amherst College in 1930, and a Ph.D. from Princeton University in 1934 under the tutelage of Alonzo Church. He joined the Wisconsin faculty in 1935 as an Instructor and in 1937 was promoted to assistant professor. During the next several years he spent time at the Institute for Advanced Study in Princeton, taught at Amherst College, and served in the U.S. Navy, earning the rank of lieutenant commander during World War II. He returned to Madison in 1946, was promoted to full professor in 1948, and remained on the faculty for the remainder of his career. He became the Cyrus Colton MacDuffee Professor of Mathematics in 1964 and retired from that position and the University of Wisconsin - Madison in 1979. He was professor emeritus until his death on January 25, 1994.

Kleene's best known books are Introduction to Metamathematics (1952) and Mathematical Logic (1967).