eBabylone
.com
|
{revue}
La thèse de Church - du nom du mathématicien Alonzo Church - est le principe de base de la calculabilité. Dans sa forme la plus ordinaire, elle affirme que tout traitement réalisable mécaniquement peut être accompli par un ordinateur (plus précisément dans sa forme idéalisée qu'est une machine de Turing). Dans une forme plus élaborée, elle affirme qu'un concept intuitif, la calculabilité effective, coïncide avec un concept formel et mathématique, la calculabilité, défini de plusieurs façons dont on a pu démontrer mathématiquement qu'elles sont équivalentes. Stephen Kleene a appelé le premier « thèse de Church » (en 1943 et 1952) ce que ce dernier présentait comme une définition de la calculabilité effective. Elle est connue plus récemment sous le nom de thèse de Church-Turing terminologie proposée par certains spécialistes1 dans les années 1990, bien que Church soit sans nul doute le premier, au début des années 1930, à avoir pensé pouvoir définir formellement la calculabilité intuitive (par la λ-définissabilité)2. Cependant c'est l'article d'Alan Turing de 1936 et son modèle mécanique de calculabilité, qui ont définitivement emporté l'adhésion, selon Gödel, Kleene et Church lui-même.
Formes équivalentes de la thèseLa thèse est formulée en disant que les machines de Turing (les fonctions λ-définissables, les fonctions récursives) formalisent correctement la notion de méthode effective de calcul. On considère généralement qu'une méthode effective doit satisfaire aux obligations suivantes :
Un exemple d'une telle méthode est l'algorithme d'Euclide pour déterminer le plus grand commun diviseur d'entiers naturels ou celui qui détermine pour un entier n la longueur de la suite de Goodstein qui commence en n. Il s'agit là d'une définition intuitive assez claire, mais pas d'une définition formelle, faute d'avoir précisé ce qu'on entend par « instruction simple et précise » ou par « l'intelligence requise pour exécuter les instructions ». On peut en revanche définir formellement ce qu'est un algorithme et pour cela on a le choix de divers formalismes. À ce stade, la thèse de Church affirme que les deux notions, intuitive « méthode effective » et formelle « algorithme », concordent. Succès de la thèseAu début du XXe siècle, les mathématiciens utilisaient des expressions informelles comme effectivement réalisable, il était donc important de trouver une formalisation rigoureuse de ce concept. Depuis les années 1940, les mathématiciens utilisent grâce à la thèse de Church une notion bien définie, celle de fonction calculable. La thèse a d'abord été formulée pour le lambda-calcul, mais d'autres formalismes ont été proposés pour modéliser les fonctions calculables, par exemple les fonctions récursives, les machine de Turing, les machines de Post et les machines à compteurs. La plus surprenante est probablement celle proposée par Yuri Matiyasevich en résolvant le dixième problème de Hilbert. On peut montrer que toutes ces définitions, bien que fondées sur des idées assez différentes, décrivent exactement le même ensemble de fonctions. Ces systèmes, qui ont le même pouvoir d'expression que l'une quelconque de ces définitions équivalentes, sont dits Turing-équivalents ou Turing-complets. Le fait que toutes ces tentatives pour formaliser le concept d'algorithme aient conduit à des résultats équivalents est l'argument qui rend la thèse de Church incontournable. HistoireDans son article de 1943 Prédicats et quantificateurs récursifs (titre original Recursive Predicates and Quantifiers) Stephen Kleene (repris dans L'Indécidable, titre original The Undecidable) a proposé pour le premier énoncé de la thèse de Church qu'il appelle « THÈSE I » :
— [note 22 de Kleene], La même thèse est implicite dans la description des machines de Turing [note 23 de Kleene].
— Kleene, dans l'indécidable, p. 274 La note 22 de Kleene fait référence à l'article de Church tandis que sa note 23 fait référence à l'article d'Alan Turing. Il continue en notant que
— [sa note 24, dans L'indécidable, P. 274], Il fait référence à l'article de Post (1936) et aux définitions formelles de l'article de Church Formal definitions in the theory of ordinal numbers, Fund. Math. vol. 28 (1936) pp.11-21 (voir réf. 2, P. 286, de l'indécidable). Dans son article de 1936 « sur des nombres calculables, avec une application à l'Entscheidungsproblem » (titre original « On Computable Numbers, with an Application to the Entscheidungsproblem ») Turing a formalisé la notion d'algorithme (alors appelée « calculabilité effective »), en introduisant les machines dites maintenant de Turing. Dans cet article il écrit en particulier à la page 239 :
— , ce qui est la version de Turing de la thèse de Church, qu'il ne connaissait pas à l'époque. Church avait démontré lui aussi quelques mois plus tôt l'insolvabilité du problème de la décision dans « une note sur l'Entscheidungsproblem » pour cela il avait utilisé les fonctions récursives et les fonctions λ-définissables pour décrire formellement le calculabilité effective. Les fonctions λ-définissables avait été introduites par Alonzo Church et Stephen Kleene (Church 1932, 1936a, 1941, Kleene 1935) et les fonctions récursives avaient été introduites par Kurt Gödel et Jacques Herbrand (Gödel 1934, Herbrand 1932). Ces deux formalismes décrivent le même ensemble de fonctions, comme cela a été démontré dans le cas des fonctions sur les entiers positifs par Church et Kleene (Church 1936a, Kleene 1936). Après avoir entendu parler de la proposition de Church, Turing a pu rapidement esquisser une démonstration que ses machines de Turing décrivent en fait le même ensemble de fonctions (Turing 1936, 263 et suivantes). Dans un article paru en 19373 il montre l'équivalence des trois modèles: fonctions λ-définissables, machines de Turing4 et fonctions générales récursives au sens de Herbrand et Gödel. Rosser5 résume les sentiments des protagonistes :
Des fonctions et nombres non calculablesOn peut définir très formellement des fonctions (par exemple sur les entiers naturels) qui ne sont pas calculables. Elles prennent en général des valeurs tellement grandes que l'on ne peut pas les calculer et par conséquent on ne peut même pas « exprimer » les valeurs qu'elles prennent, car c'est leur définition qui le dit. La plus connue est celle dite du castor affairé. Pour simplifier, il s'agit de la taille du plus grand travail que peut faire une machine de Turing quand on lui donne une ressource limitée par n. Comme sa définition est obtenue comme une limite de ce que pourraient faire les machines de Turing, le nombre qu'elle produit ne peut pas être calculé, ni même sa valeur exacte exprimée, tout au plus les chercheurs arrivent-ils à donner des nombres qui lui sont inférieurs pour les plus petites valeurs de n (2, 3, 4, 5, péniblement 6). Le nombre Oméga de Chaitin est un nombre réel parfaitement défini qui n'est pas calculable, précisément parce que sa construction dépend des réponses au problème semi-décidable de l'arrêt des machines de Turing. Voir aussiRéférences
Articles connexesSourcesArticles originaux
Autres (en anglais)
Autres (en français)
Le Texte ci-dessus est disponible sous GNU Free Documentation License. La source est wikipedia http://fr.wikipedia.org/wiki/{title} |
Server 2.0