RÉCURSIVITÉ, logique mathématique
Énumération universelle (principe du fonctionnement des ordinateurs)
Revenons à la définition informatique des fonctions récursives. L'alphabet que l'on utilise pour écrire des instructions, donc des programmes, est le suivant :
Comme A possède dix éléments, convenons d'utiliser les chiffres 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 au lieu des symboles A, D, E, T, q, ;, /, (,), * respectivement. Le programme précédent s'écrit alors :
Ainsi, si l'on convient d'utiliser la représentation décimale des nombres, un programme apparaît comme un nombre. Soit P ⊂ N l'ensemble des nombres dont l'écriture décimale correspond à l'écriture d'un programme. On peut vérifier que P est récursif. L'algorithme permettant de décider si x ∈ P ou x ∉ P consiste à faire l'analyse syntaxique de la représentation décimale de x, c'est-à-dire savoir si la suite correspondante de symboles est bien formée au sens de la grammaire de notre langage miniature de programmation.
Soit alors ϕ : N → *FR(p) l'application définie de la façon suivante :
– si x ∈ P, ϕ(x) est la semi-application définie par le programme de numéro x (les arguments x1, ..., xp étant placés dans les registres 2 à p + 1 et le résultat pris dans le registre 1) ;
– si x ∉ P, alors ϕ(x) = u(p).
Soit maintenant ϕ̄(x, x1, ..., xp) = ϕ(x)(x1, ..., xp). On se demande si ϕ̄ appartient à *FR(p+1) . En d'autres termes, existe-t-il un algorithme permettant de calculer ϕ(x)(x1, ..., xp) pour tout x, x1, ..., xp ? Un tel algorithme correspond au principe de fonctionnement des ordinateurs qui consiste à appliquer un programme quelconque x (enregistré en mémoire dans le registre 1) sur des arguments x1, ..., xp (enregistrés en mémoire dans les registres 2 à p + 1). Si on fait appel à la thèse de Church, on peut donc admettre que ϕ̄ ∈ *FR(p+1) . Signalons au passage que l'existence d'une énumération universelle récursive avait été trouvée par le logicien A. Turing avant la construction des ordinateurs.
L'application ϕ possède de nombreuses propriétés et D. Lacombe en a fait une théorie générale abstraite. Mentionnons seulement deux propriétés élémentaires ayant des applications immédiates.
Existence d'une machine capable de se reproduire
Propriété a. Pour toute application ψ : N → *FR(p) telle que ψ ∈ *FR(p+1) , il existe a ∈ N tel que ψ(a) = ϕ(a).
Ainsi, par exemple, pour p = 1, si on prend ψ = pr12 définie par ψ(x, y) = x pour tout x et tout y, il existe a ∈ N tel que, pour tout y ∈ N, on ait ϕ(a, y) = ψ(a, y) = a. Donc a est le numéro d'un programme qui, de par la définition même de ϕ, donnera a lorsqu'on l'applique sur un argument y quelconque. Donc a est le programme d'une machine qui se reproduit.
Indécidabilité de propriétés classiques
Propriété b. Pour tout ensemble non vide A ⊂ FR(p) , l'ensemble ϕ−1(A) est non récursif.
Ainsi, si on considère une propriété des fonctions calculables définissant un ensemble non vide A ⊂ *FR(p) , l'ensemble ϕ−1(A) des programmes permettant de calculer (ou qui définissent) ces fonctions n'est pas récursif. Par exemple, pour p = 1, si :
ϕ−1(A) est l'ensemble des programmes qui s'arrêtent lorsqu'on les applique sur 0, et dire que ϕ−1(A) est non récursif signifie qu'il n'existe pas d'algorithme général permettant de décider si un programme quelconque va s'arrêter lorsqu'on l'applique sur 0.
Le lecteur pourra, en choisissant des ensembles[...]
La suite de cet article est accessible aux abonnés
- Des contenus variés, complets et fiables
- Accessible sur tous les écrans
- Pas de publicité
Déjà abonné ? Se connecter
Écrit par
- Kenneth Mc ALOON : maître de recherche au C.N.R.S.
- Bernard JAULIN : membre de l'Académie des sciences
- Jean-Pierre RESSAYRE : chargé de recherche au C.N.R.S.
Classification
Autres références
-
CHURCH ALONZO (1903-1995)
- Écrit par Françoise ARMENGAUD
- 616 mots
Mathématicien et logicien, philosophe et historien de la logique, Alonzo Church est né le 14 juin 1903 à Washington et mort le 11 août 1995 à Hudson (Ohio). Professeur de mathématiques à l'université de Princeton, directeur du Journal of Symbolic Logic, il est selon Kneale «...
-
DÉMONSTRATION THÉORIE DE LA
- Écrit par Jean-Yves GIRARD
- 6 140 mots
- 1 média
...fini, détermine uniquement (par unicité du prolongement par limites directes) la famille (Pα). Il devient alors possible de parler de B-démonstration récursive, autrement dit nous avons un concept syntaxique. (Mais l'ensemble des indices de B-démonstrations est Π12 .) Et Girard a pu établir en... -
KLEENE STEPHEN COLE (1909-1994)
- Écrit par Pierre GOUJON
- 371 mots
Mathématicien américain né à Hartford (Connecticut). Diplômé de l'Amherst College, Stephen C. Kleene entre, en 1930, à l'université de Princeton. Il est docteur de la même université en 1934. Dès cette époque, il partage son temps entre l'enseignement (université du Wisconsin) et la recherche....
-
POST EMIL LEON (1897-1954)
- Écrit par Bernard JAULIN
- 622 mots
Mathématicien américain né à Augustów (Pologne) et mort à New York. Arrivé aux États-Unis en 1904, Emil Post obtint son Ph.D. à l'université Columbia de New York en 1920. Il était membre de l'American Mathematical Society depuis 1918 et de l'Association for Symbolic Logic dès sa fondation...
