RÉCURSIVITÉ, logique mathématique

Carte mentale

Élargissez votre recherche dans Universalis

É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 :

si l'on convient d'écrire le nombre r avec r barres / et de séparer deux instructions par un astérisque. Par exemple, le programme :
sera écrit :
dans cet alphabet.

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 ∈ P ou ∉ 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 ϕ : → *FR(p) l'application définie de la façon suivante :

– si ∈ 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 ∉ P, alors ϕ(x) = u(p).

Soit maintenant ϕ̄(xx1, ..., 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' [...]

1 2 3 4 5

pour nos abonnés,
l’article se compose de 14 pages




Écrit par :

Classification


Autres références

«  RÉCURSIVITÉ, logique mathématique  » est également traité dans :

CHURCH ALONZO (1903-1995)

  • Écrit par 
  • Françoise ARMENGAUD
  •  • 611 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 « le plus fidèle des disciples de Frege ». Réputé « platonisant », il défend une conception délibérémen […] Lire la suite☛ http://www.universalis.fr/encyclopedie/alonzo-church/#i_82872

DÉMONSTRATION THÉORIE DE LA

  • Écrit par 
  • Jean-Yves GIRARD
  •  • 6 260 mots
  •  • 1 média

Dans le chapitre « La logique Π12 »  : […] L'extension des résultats obtenus par Takeuti, Pohlers, Buchholz... pour le schéma de compréhension Π 1 1 à des systèmes plus forts nécessite de remplacer la ω-logique par des logiques correspondant à de plus grandes complexités logiques, Π 2 1 et plus généralement Π 1 n . Le problème de la […] Lire la suite☛ http://www.universalis.fr/encyclopedie/theorie-de-la-demonstration/#i_82872

KLEENE STEPHEN COLE (1909-1994)

  • Écrit par 
  • Pierre GOUJON
  •  • 370 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. Il est successivement membre du Conseil national de la recherche scientifique (1957), puis président de l […] Lire la suite☛ http://www.universalis.fr/encyclopedie/stephen-cole-kleene/#i_82872

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 en 1935. Sa thèse de doctorat, publiée en 1921, porte sur le calcul propositionnel de A. N. Whitehead et B. Ru […] Lire la suite☛ http://www.universalis.fr/encyclopedie/emil-leon-post/#i_82872

Voir aussi

Pour citer l’article

Jean-Pierre RESSAYRE, Kenneth Mc ALOON, Bernard JAULIN, « RÉCURSIVITÉ, logique mathématique », Encyclopædia Universalis [en ligne], consulté le 24 juillet 2019. URL : http://www.universalis.fr/encyclopedie/recursivite-logique-mathematique/