Thèse de Church

La thèse de Church est une thèse concernant la définition de la notion de calculabilité. Dans une forme dite « physique », 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 », 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 fut le premier à nommer « 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 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é), ce sont 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. 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, ou de calculabilité. On considère généralement que la notion intuitive de méthode effective de calcul correspond aux caractéristiques suivantes : l'algorithme consiste en un ensemble fini d'instructions simples et précises qui sont décrites avec un nombre limité de symboles ; l'algorithme doit toujours produire le résultat en un nombre fini d'étapes ; l'algorithme peut en principe être suivi par un humain avec seulement du papier et un crayon ; 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.