...les infinis se valent-ils tous ?

Ce thème va montrer qu'il est possible de dire des choses très générales concernant les machines et les programmes sans même dire comment elles sont faites ni comment ils sont écrits.

Question : Pourquoi, l'alphabet est-il nécessairement fini ?

En fait, tous les raisonnements qui vont suivre sont fondés sur les seules hypothèses suivantes :

• les données sont représentées par les mots d'un langage fondé sur un alphabet fini de symboles.
• les programmes sont représentés par des phrases constituées des mots d'un langage fondé sur un alphabet fini de symboles.
• les machines sont capables d'exécuter un programme tel que ceux définis ci-dessus manipulant des données telles que celles définies ci-dessus.

On peut se demander s'il est utile de tenter d'utiliser une approche mathématique pour décrire les objets et les processus de l'informatique. Si on considère l'histoire des sciences et des techniques, on constate qu'une technique est d'autant plus efficace qu'elle s'appuie sur un support théorique fondé sur des mathématiques. On ne voit donc pas comment l'informatique pourrait échapper à cette tendance.

Combien peut-on représenter de données ?

Si on considère qu'une donnée est représentée par l'association (un système de numération définit les règles d'association utilisées pour représenter les nombres) d'un nombre fini, inférieur à M, de symboles prélevés dans un alphabet de taille N. On ne pourra pas représenter plus de N^M données. C'est un grand (très grand) nombre, mais c'est un nombre fini.

Évitons de nous limiter plus qu'il n'est nécessaire

Question : Comment peut-on numéroter les données ?

Comme nous ne voulons pas limiter a priori les capacités de la machine utilisée, nous allons autoriser une donnée à être représentée en associant un nombre éventuellement infini de symboles. Dans ces conditions, on peut montrer que l'ensemble des données représentables est infini dénombrable. Cela signifie que chaque donnée peut être numérotée et donc représentée par un nombre entier (naturel).

Toutes les données représentables, dans ces conditions, appartiennent à N.

Qu'est-ce alors qu'un programme ?

Un programme est donc une fonction de N dans N car l'ensemble des données qu'on lui fournit est représentable par un entier et l'ensemble des résultats qu'il produit est représentable par un entier.

Combien peut-on définir de programmes ?

L'ensemble des programmes qu'il est possible de définir est l'ensemble des fonction de N dans N qu'on peut définir. On a pu montrer que cet ensemble est infini non dénombrable. La méthode de démonstration utilisée pour établir cette propriété s'appelle : la diagonale de Cantor.

Combien peut-on écrire de programmes ?

Si on considère qu'un programme est écrit en associant (c'est le langage de programmation utilisé qui définit les règles d'association) un nombre fini, inférieur à M, de symboles prélevés dans un alphabet de taille N. On ne pourra pas écrire plus de N^M programmes. C'est un grand (très grand) nombre, mais c'est un nombre fini.

Evitons de nous limiter plus qu'il n'est nécessaire

Comme nous ne voulons pas limiter a priori les capacités de la machine utilisée, nous allons autoriser un programme à être écrit en utilisant un nombre éventuellement infini de symboles. Dans ces conditions, on peut montrer que l'ensemble des programmes qu'on peut écrire est infini dénombrable. Cela signifie que chaque programme peut être numéroté et donc représenté par un nombre entier (naturel).

Tous les programmes qu'on peut écrire, dans ces conditions, appartiennent à N.

Peut-on tout programmer ?

Non, puisqu'on peut définir un ensemble infini non dénombrable de fonctions de N dans N alors qu'on ne peut écrire qu'un ensemble fini dénombrable de programmes. Cette restriction a amené les théoriciens à introduire la notion de fonction calculable. Deux définitions pour les fonctions calculables ont été proposées :

• définition de Turing [2] elle repose sur l'existence de la Machine de Turing. Est considérée comme calculable toute fonction dont la valeur peut être évaluée en utilisant une Machine de Turing.
• définition de Church [3] elle repose sur la définition d'un langage de représentation des fonctions, le lambda-calcul. Est considérée comme calculable toute fonction dont la définition peut être écrite en utilisant le lambda-calcul.

Cette façon de poser une définition semble assez curieuse. C'est pourtant souvent la seule solution pour définir des notions difficiles. Comment, par exemple, définir le temps autrement que par l'expression ce que mesure une horloge ?

On n'a jamais pu montrer que ces deux définitions sont équivalentes ; il n'a jamais été possible, non plus, de constater qu'une fonction calculable au sens de Turing ne l'était pas au sens de Church et réciproquement. L'affirmation de l'identité de ces 2 définitions constitue la conjecture de Church-Turing.

En fait, que peut-on programmer ?

Tout ce qui peut se dire précisément (se spécifier) peut se programmer. Mais, tout peut-il se dire ?

Question : Comment peut-on justifier cette interrogation ?

Pouvoir expressif de l'infini non dénombrable

Les éléments d'un ensemble infini non dénombrable ont un pouvoir expressif théorique extraordinaire bien que peu utilisable pratiquement. Pour illustrer cette remarque on peut raconter l'histoire suivante :

Notes

1. (retour) Georg Cantor (1845-1918) : German mathematician who built a hierarchy of infinite sets according to their cardinal number. By one-to-one pairing, he showed that the set of real numbers has a higher cardinal number than does the set of rational fractions. However, he found every class of algebraic numbers has the same cardinal number as the integers. Such considerations led to his Mengenlehre (theory of assemblages) and Manningfaltigkeitslehre (theory of manifolds). He also invented the Cantor set. His highly original views were vigorously opposed by his contemporaries, especially Kronecker. The attacks contributed to the nervous breakdowns he suffered throughout the final 33 years of his life. Cantor died in a mental institution.
   
   Additional biographies: MacTutor
2. (retour) Alan Turing? founder of computer science, mathematician, philosopher, codebreaker, strange visionary and a gay man before his time:
   • 1912 (23 June): Birth, Paddington, London
   • 1926-31: Sherborne School
   • 1930: Death of friend Christopher Morcom
   • 1931-34: Undergraduate at King's College, Cambridge University
   • 1932-35: Studies quantum mechanics, probability, logic
   • 1935: Elected fellow of King's College, Cambridge
   • 1936: The Turing machine: On Computable Numbers... submitted
   • 1936-38: At Princeton University. Ph.D. Papers in logic, algebra, number theory
   • 1938-39: Return to Cambridge. Introduced to German Enigma cipher problem
   • 1939-40: Devises the Bombe, machine for Enigma decryption
   • 1939-42: Breaking of U-boat Enigma cipher, saving battle of the Atlantic
   • 1943-45: Chief Anglo-American consultant. Introduced to electronics
   • 1945: National Physical Laboratory, London
   • 1946: Computer design, leading the world, formally accepted
   • 1947-48: Papers on programming, neural nets, and prospects for artificial intelligence
   • 1948: Manchester University
   • 1949: Work on programming and world's first serious use of a computer
   • 1950: Philosophical paper on machine intelligence: the Turing Test
   • 1951: Elected FRS. Paper on non-linear morphogenesis theory
   • 1952: Arrested and tried as a homosexual, loss of security clearance
   • 1953-54: Unfinished work in biology and physics
   • 1954 (7 June): Death by cyanide poisoning, Wilmslow, Cheshire.
3. (retour) Alonzo Church was born on June 14, 1903 in Washington, D.C. and died Friday, August 11, 1995 in Hudson, Ohio at the age of 92. He was buried in Princeton Cemetery. Church was professor of mathematics at Princeton University from 1929 to 1967 when he became professor of mathematics and philosophy at UCLA. His work has been greatly influential in the fields of mathematical logic, recursion theory, and theoretical computer science. At the time of his death, Church was widely regarded as the greatest living logician in the world. His most well-remembered contributions are the following: Church's Theorem (1936), showing that arithmetic is undecidable. Church's Thesis, conjecturing that effective computation is equivalent to the notion of a "recursive" function.