RÉCURSIVES FONCTIONS

Ce sujet est traité dans les articles suivants :

1.  HILBERT DAVID (1862-1943)

Écrit par : Rüdiger INHETVEEN, Jean-Michel KANTOR, Christian THIEL

Dans le chapitre "Problème 10 : résolubilité des équations diophantiennes"  : … d'opérations si une équation diophantienne a des solutions (entières). La théorie des fonctions *récursives et des algorithmes, qui s'est développée depuis les années 1930 (parallèlement à « l'explosion informatique »), a permis de formuler précisément le problème posé par Hilbert, et de le résoudre, par la négative ! (I. Matijasevič, 1970).… Lire la suite

2.  KLEENE STEPHEN COLE (1909-1994)

Écrit par : Pierre GOUJON

… *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… Lire la suite

3.  LOGIQUE MATHÉMATIQUE

Écrit par : Daniel ANDLER, Roger MARTIN

Dans le chapitre "La classe des fonctions récursives"  : … satisfaisante parce qu'indépendante de tout formalisme particulier : elle a créé la notion de *fonction récursive, et s'est fondée sur la remarquable stabilité de cette notion pour la proposer comme équivalent mathématique de la notion intuitive de fonction calculable. En effet, à partir de 1931, toute une série de logiciens (Gödel,… Lire la suite

4.  POST EMIL LEON (1897-1954)

Écrit par : Bernard JAULIN

… *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… Lire la suite

5.  RÉCURSIVITÉ, logique mathématique

Écrit par : Kenneth Mc ALOON, Bernard JAULIN, Jean-Pierre RESSAYRE

Dans le chapitre "Complexité"  : … ^(p)  (x) qui est de l'ordre de : Il est donc clair qu'une *fonction récursive f qui n'appartient pas à E3 n'est pas calculable pratiquement. En effet, si l'on admet que le temps minimal d'une étape de calcul est le temps mis par la lumière, à la vitesse de 300 … Lire la suite

6.  ROBINSON JULIA (1919-1985)

Écrit par : Gabriel SABBAGH

… que l'on peut prendre n = 2. Le troisième domaine de prédilection de Julia Robinson fut la théorie des *fonctions récursives. Son travail le plus accompli dans ce domaine est sans doute celui qui fut publié en 1968 dans les Proceedings of the American Mathematical Society (« Recursive Fonctions of one variable ») où elle donne une… Lire la suite