Thèse de Church

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La thèse de Church – du nom du mathématicien Alonzo Church – est une thèse concernant la définition de la notion de calculabilité.

Dans une forme dite « physique »[1], elle affirme que la notion physique de la calculabilité, définie comme étant tout traitement systématique réalisable par un processus physique ou mécanique, peut être exprimée par un ensemble de règles de calcul, défini de plusieurs façons dont on a pu démontrer mathématiquement qu'elles sont équivalentes.

Dans sa forme dite « psychologique »[1] elle affirme que la notion intuitive de calculabilité, qui est liée à ce qu'un être humain considère comme effectivement calculable ou non, peut également être exprimée par ces mêmes ensembles de règles de calcul formelles.

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 également connue, sous le nom plus récent de thèse de Church-Turing, terminologie proposée par certains spécialistes[2] 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é)[3], c'est cependant 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.

Formulation de la thèse[modifier | modifier le code]

La thèse est formulée en disant que des règles formelles de calcul (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 de calcul doit satisfaire aux obligations suivantes :

  1. l'algorithme consiste en un ensemble fini d'instructions simples et précises qui sont décrites avec un nombre limité de symboles ;
  2. l'algorithme doit toujours produire le résultat en un nombre fini d'étapes ;
  3. l'algorithme peut en principe être suivi par un humain avec seulement du papier et un crayon ;
  4. l'exécution de l'algorithme ne requiert pas d'intelligence de l'humain sauf celle qui est nécessaire pour comprendre et exécuter les instructions.

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 entre divers formalismes. À ce stade, la thèse de Church affirme que les deux notions, intuitive de « méthode effective », et formelle (« règles de calcul », ou « algorithme »), concordent, apportant ainsi une définition rigoureuse du concept de calculabilité.

En effet, au 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 machines 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.

Thèse de Church et calcul quantique[modifier | modifier le code]

Les différents modèles de calcul, purement mathématiques, élaborés pour modéliser la calculabilité sont a priori indépendants de la physique, et des processus physiques. Aussi, il n'est pas évident a priori que la version « physique » de la thèse de Church soit vérifiée avec des modèles abstraits. De plus, le modèle le plus proche d'un mécanisme physique (les machines de Turing) contient des hypothèses implicites qui sont inspirées par la physique classique (comme un bit ne peut être que '0' ou bien '1').

En 1982, le physicien Richard Feynman s'est posé la question de savoir si les modèles de calcul pouvaient calculer l'évolution de processus quantiques. Il est parvenu à démontrer que cela était possible, mais de manière inefficace, inapplicable en pratique. Or, la nature est visiblement capable de « calculer » cette évolution de manière efficace. La question se pose donc inévitablement de savoir si les processus quantiques sont en relation avec une autre forme de calculabilité et s'ils remettent en cause la forme physique de la thèse de Church.

Pour explorer cette question, il est nécessaire d'élaborer un modèle de calcul prenant en compte les particularités de la mécanique quantique, et capable de calculer les processus quantiques efficacement. Muni de ce modèle mathématique, on peut alors étudier ses relations avec les modèles classiques de calcul, sur le plan de la calculabilité (ce que les modèles sont capables de calculer ou non), l'universalité (si une machine peut simuler toutes les autres efficacement), et de la complexité (dans quels ordres de temps et de mémoire les problèmes peuvent-ils être calculés).

Les premières tentatives de créer des modèles de calcul quantiques ont eu lieu au début des années 1980 par Paul Benioff[4]. C'était un modèle de machine de Turing réversible, prenant en compte une des particularité majeure de la mécanique quantique : l'unitarité qui implique que les calculs quantiques doivent être réversibles (contrairement aux calculs classiques). C'est-à-dire que, connaissant un résultat et la série d'opération y ayant mené, un calcul quantique peut toujours être déroulé en arrière jusqu'à retrouver les données initiales[5]. Mais il manquait encore des ingrédients pour aboutir à un véritable modèle de calcul quantique : même si les calculs utilisaient la superposition quantique, les états des bits à chaque étape de calcul étaient dans un état classique '0' ou bien '1'.

En 1985, David Deutsch propose un véritable modèle de calcul quantique[6], reconnu comme étant le premier véritable modèle de machine de Turing quantique[7]. Dans cet article, Deutsch remarque que les calculateurs quantiques sont capables de produire un résultat que les machines de Turing classiques ne peuvent produire : générer un nombre purement aléatoire. Mais cela ne remet pas en cause la thèse de Church, car la génération d'un nombre aléatoire ne fait pas partie de ce qui est considéré comme un « calcul ».

Ce modèle de calcul a permis d'établir que les machines de Turing quantiques ne permettent pas de calculer davantage de problèmes que les machines de Turing classiques. Elles sont même, d'un certain point de vue, moins complètes que les machines de Turing classiques car, si on désire utiliser le parallélisme quantique pour calculer plus rapidement certaines propriétés conjointes entre m valeurs binaires, alors il a été démontré en 1991 par Richard Jozsa[8] que seules 2^{2^m} - 2^{m+1} propriétés parmi les 2^{2^m} propriétés conjointes possibles étaient calculables de cette manière, alors qu'elles les sont toutes avec une machine de Turing classique[9].

Histoire[modifier | modifier le code]

Dans 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 » :

« Ce fait heuristique [les fonctions récursives générales sont effectivement calculables]… a conduit Church à énoncer la thèse suivante »

— [note 22 de Kleene], La même thèse est implicite dans la description des machines de Turing [note 23 de Kleene].

« THÈSE I. Chaque fonction effectivement calculable (chaque prédicat effectivement décidable) est récursive générale [les italiques sont de Kleene] »

« Puisque nous recherchions une définition mathématique précise de l'expression effectivement calculable (effectivement décidable), nous prendrons cette thèse comme sa définition ... »

— 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

« … la thèse n'est qu'une hypothèse -- une constatation déjà soulignée par Post et par Church »

— [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 :

« Une suite calculable γ est déterminée par une description d'une machine qui calcule γ ... et, en fait, n'importe quelle suite calculable est susceptible d'être décrite en termes d'une table [c'est-à-dire d'une machine de Turing]. »

—  , 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 la 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 1937[λdef 1] il montre l'équivalence des trois modèles : fonctions λ-définissables, machines de Turing[10] et fonctions générales récursives au sens de Herbrand et Gödel. Rosser[11] résume les sentiments des protagonistes : « Une fois l'équivalence de la récursivité générale et de la λ-définissabilité établie, Church, Kleene et moi nous attendions à ce que Gödel nous rejoignent pour supporter la thèse de Church. Gödel avait cependant encore des réserves et ça n'est qu'au moins deux ou trois ans plus tard, après les travaux de Turing, que Gödel devint finalement un adepte (comme le devint aussi Turing). »

Turing écrit[λdef 2] en 1937 : « L'identification des fonctions 'effectivement calculables' avec les fonctions calculables [c-à-d. définies par une machine de Turing] est peut-être plus convaincante que l'identification avec les fonctions λ-définissables ou récursives générales. Pour ceux qui adoptent ce point de vue, la démonstration formelle de l'équivalence fournit une justification du calcul de Church et permet de remplacer les 'machines' qui engendrent des fonctions calculables par les λ-définitions qui sont plus commodes. »

Des fonctions et nombres non calculables[modifier | modifier le code]

On 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.

Autres modèles de calcul[modifier | modifier le code]

On ne connaît pas de modèle de calcul plus puissant que les machines de Turing, c'est-à-dire qui serait en mesure de calculer des fonctions non-calculables par une machine de Turing, ou même de calculer plus rapidement les fonctions calculables (voir Théorie de la complexité des algorithmes). La thèse de Church physique pourrait être remise en cause par l'hypercalcul, mais les processus physiques utilisés par l'hypercalcul sont extrêmement spéculatifs et probablement à jamais impossibles à mettre en œuvre en pratique.

Inversement, il existe des modèles de calcul plus faibles que les machines de Turing. Tout système de calcul généraliste ne permet pas d'atteindre la notion de calculabilité de Church et Turing. Par exemple, en affaiblissant un peu la définition des fonctions récursives (en les limitant à des définitions récursives reposant sur les successeurs d'un seul paramètre, voir Fonction récursive primitive pour en savoir plus), on obtient un système de calcul qui semble aussi généraliste et qui effectivement permet de définir bon nombre de fonctions usuelles, mais où certaines fonctions ne sont plus calculables alors qu'elles le sont avec des machines de Turing ou en Lambda-calcul. Le système en question n'est donc pas équivalent aux machines de Turing.

Un exemple de fonction non calculable dans ce système (Fonction récursive primitive) alors qu'elle est calculable par une machine de Turing, est donné par la célèbre fonction très croissante connue sous le nom de Fonction d'Ackermann et définie récursivement comme suit :

fonction d’Ackerman
A(0, n) = n+1\,
A(m+1, 0) = A(m, 1)\,
A(m+1, n+1) = A(m, A(m+1, n))\,

Cette fonction croît très rapidement. Par exemple A(4,2) est un nombre de 19729 chiffres.

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. pp.  153-163. ; voir aussi Collected Works of A.M. Turing, tome Mathematical Logic.
  2. dans cet article

Références[modifier | modifier le code]

  1. a et b Gilles Dowek, Les Métamorphoses du calcul : Une étonnante histoire des mathématiques, Le Pommier,‎ 2007 (ISBN 978-2746503243)
  2. voir Robert I. Soare, article cité.
  3. Attesté pas une lettre de Church à Gödel de 1934, voir Soare, article cité.
  4. P. Benioff The Computer as a Physical System : A Microscopic Quantum Mechanical Hamiltonian Model of Computers as Represented by Turing Machines Journal of Statistical Physics, Volume 22 (1980) pp 563-591
  5. Ce qui est impossible avec un calcul classique : connaissant un résultat « 10 » par exemple, et l'opération y ayant mené, l'addition, on est incapable de savoir si les données initiales étaient « 5 » et « 5 » ou « 9 » et « 1 » par exemple
  6. D. Deutsch Quantum Therory, the Church-Turing Principle, and the Universal Quantum Computer Proc. R. Soc. Lond. A, Volume 400 (1985) pp. 97-117
  7. Colin. P. Williams Explorations in Quantum Computing Springer. 2d édition 2011
  8. R. Jozsa Characterizing Classes of Functions Computable by Quantum Parallelism Proc. R. Soc. Lond. A, Volume 435 (1991) pp. 563-574
  9. Mais, évidemment, une machine de Turing quantique pouvant simuler une machine de Turing classique, une machine de Turing quantique est capable de calculer toutes les propriétés conjointes, mais sans utiliser ses propriétés propres
  10. La terminologie est due à Church.
  11. In Highlights of the History of the Lambda-Calculus, Annals of the History of Computing vol. 6, n°4, oct 1984.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Sources[modifier | modifier le code]

Articles originaux[modifier | modifier le code]

  • (en) Alonzo Church, « An Unsolvable Problem of Elementary Number Theory (abstract) », Bull. Amer. Math. Soc., vol. 41,‎ 1935, p. 332-333 (abstract), Bull. Amer. Math. Soc. 41 (1935), p. 332-333.
  • (en) Alonzo Church, « An Unsolvable Problem of Elementary Number Theory », American Journal of Mathematics, vol. 58,‎ 1936, p. 245–63
  • (en) Alonzo Church, « A Note on the Entscheidungsproblem », Journal of Symbolic Logic, vol. 1,‎ 1936, p. 40-41, correction p. 101-102.
  • Notes de cours de Kleene et Rosser. Rééditée dans (en) Kurt Gödel, « On Undecidable Propositions of Formal Mathematical Systems », The Undecidable, Davis, M. (New York: Raven Press),‎ 1934, rééditées en 1965
  • Jacques Herbrand, « Sur la non-contradiction de l'arithmétique », Journal fur die reine und angewandte Mathematik, vol. 166,‎ 1931, p. 1-8 (lire en ligne)
  • (en) Stephen Cole Kleene, « Lambda-Definability and Recursiveness », Duke Mathematical Journal, vol. 2,‎ 1936, p. 340-353.
  • (en) Stephen Cole Kleene, « Recursive predicates and quantifiers », Trans. A.M.S., vol. 53,‎ 1943, p. 41-73
  • (en) Alan Turing, « On Computable Numbers, with an Application to the Entscheidungsproblem », Proc. London Math. Soc., 2e série, vol. 42,‎ 1937, p. 230-265 (DOI 10.1112/plms/s2-42.1.230) et « [idem] : A Correction », Proc. London Math. Soc., 2e série, vol. 43,‎ 1938, p. 544-546 (DOI 10.1112/plms/s2-43.6.544, lire en ligne)
  • (en) Alan Turing, « Computability and λ-definability », J. Symbolic Logic, vol. 2,‎ 1937, p. 153-163

Autres (en anglais)[modifier | modifier le code]

  • Martin Davis editor, The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions, Raven Press, New York, 1965. Les articles originaux dont ceux de Gödel, Church, Turing, Rosser, Kleene, and Post. Préfaces de Davis.
  • Stephen Cole Kleene, 1952, Introduction to Metamathematics, Van Nostrand, New York.
  • Stephen Cole Kleene, Origins of Recursive Function Theory in Annals of the History of Computing, Vol. 3 No. 1, janvier 1981.
  • Barkley Rosser Highlights of the History of the Lambda-Calculus, Annals of the History of Computing 6,4 [1984], 337-349
  • Robert Soare, (1995-6), Computability and Recursion, Bulletin of Symbolic Logic 2 (1996), 284--321, version en ligne, article sur l'historique de la calculabilité, qui milite pour un certain nombre de changements terminologiques, écrit par un spécialiste du domaine.
  • Wilfried Sieg Step by recursive step: Church's analysis of effective calculability. Bulletin of Symbolic Logic 3(2): 154-180 (1997).
  • Collected Works of A. M. Turing vol. Mathematical Logic, eds. R. O. Gandy and C. E. M. Yates, (ISBN 0-444-50423-0).

Autres (en français)[modifier | modifier le code]