CALCULABILITÉ

Ce sujet est traité dans les articles suivants :

1.  CALCUL, mathématique

Écrit par : Philippe FLAJOLET

Dans le chapitre "Calculabilité et algorithmique"  : … *Dans les années 1930 s'élabore, sous l'impulsion notamment du logicien Alan Turing, une théorie abstraite de la calculabilité, ce avant même l'avènement de l'ordinateur. Tout n'est pas calculable en mathématique et, par exemple, il ne saurait exister de procédé systématique permettant de distinguer par calcul, parmi l'infini des assertions… Lire la suite

2.  COMPLEXITÉ, mathématique

Écrit par : Jean-Paul DELAHAYE

… *Au cœur de l'informatique théorique, la théorie du calcul – ou théorie de la calculabilité – née dans la décennie 1930 des travaux de Kurt Gödel (1906-1978), Alan Turing (1912-1954) et Alonzo Church (1903-1995), répond à des questions sur ce qui est faisable dans l'absolu par le calcul avec un ordinateur. Elle énonce des résultats négatifs du type… Lire la suite

3.  GÖDEL KURT (1906-1978)

Écrit par : Daniel ANDLER

Dans le chapitre "L'œuvre"  : … de fonction récursive, par Herbrand et Gödel, et à l'élucidation par Turing de la notion de *calculabilité, qui permettait de dégager la véritable généralité des théorèmes de Gödel. C'est en théorie des ensembles, à l'axiomatisation de laquelle il contribua, que Gödel fit sa troisième grande découverte, en apportant à une célèbre… Lire la suite

4.  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"  : … vraie : tout ensemble récursivement énumérable est diophantien. D'autre part, un ensemble d'entiers*est dit calculable s'il existe un algorithme permettant de déterminer en un nombre fini d'étapes si un nombre lui appartient ou non. D'après la théorie des algorithmes, on connaît l'existence d'un ensemble récursivement énumérable qui ne… Lire la suite

5.  TURING MACHINE DE

Écrit par : Bernard PIRE

  *Dans l'article « On computable numbers, with an application to the Entscheidungsproblem », publié en 1936 dans les Proceedings of the Mathematical Society, Alan Mathison Turing (1912-1954) montre qu'il existe des nombres définissables qui ne sont pas calculables. Cela implique qu'il n'existe pas de solution au… Lire la suite

6.  PENSÉE

Écrit par : Pascal ENGEL

Dans le chapitre "Pensée, machines et fonctionnalisme"  : … de la machine par divers états. Une machine de Turing est la réalisation de la notion logique de *calculabilité : si une fonction est calculable, elle l'est par une telle machine. Or, selon la « thèse de Church », il n'y a pas d'algorithme pour la calculabilité : la notion de « procédure effective » n'est pas démontrable. Il s'ensuit qu'on ne… Lire la suite

7.  RÉCURSIVITÉ, logique mathématique

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

Dans le chapitre "Définitions des fonctions récursives"  : … récursives. Définition. Une fonction f ∈ *F^(p) est dite *calculable par programme, et on note f ∈ *FP^(p) s'il existe un programme écrit à l'aide des quatre instructions ci-dessus et de l'instruction « arrêt » tel… Lire la suite

8.  TURING ALAN MATHISON (1912-1954)

Écrit par : B. Jack COPELAND

Dans le chapitre "Jeunesse et études universitaires "  : … que certains systèmes purement logiques, bien moins solides que l'arithmétique, sont indécidables.) *Un important argument de Turing et Church est que la classe des fonctions lambda-définissables (fonctions des entiers naturels dont la valeur peut être calculée par un processus de substitution répétée) coïncide avec la classe des fonctions… Lire la suite