Church (thèse de)

Cet article est extrait de l'ouvrage Larousse « Dictionnaire de la philosophie ».

Logique

Affirmation selon laquelle toutes les fonctions effectivement calculables sont « récursives », et qui revient donc à identifier la notion informelle de calculabilité par algorithme à la notion formellement définie de récursivité, ou à l'une des notions équivalentes à cette dernière, comme la « lambda-définissabilité » ou la calculabilité par une « machine de Turing ».

La thèse de Church⁽¹⁾ n'est pas un théorème susceptible de démonstration (puisque l'un des termes de l'identification n'est, justement, pas formellement défini), mais une assertion en faveur de laquelle une batterie d'arguments extrêmement convaincants peuvent être avancés, au nombre desquels (1) le fait que toute fonction reconnue comme effectivement calculable s'est à ce jour avérée récursive, (2) la convergence des définitions d'allure fort dissemblables qui ont pu être proposées pour caractériser formellement la notion calculabilité par algorithme.

L'année même (1936) où la thèse de Church était avancée par son auteur, Turing⁽²⁾, de manière indépendante et guidée par des considérations sensiblement différentes, proposait quant à lui d'identifier les fonctions effectivement calculables aux fonctions capables d'être calculées par une « machine de Turing ». Compte tenu de l'identité, postérieurement établie, entre les fonctions calculables au sens de Turing et les fonctions que Church avait en vue, la « thèse de Turing » équivaut à la thèse de Church, et les deux sont souvent désignées sous le nom de « thèse de Church-Turing ».

Jacques Dubucs

→ calculabilité, diagonal (argument), effectivité, machine (logique, de Turing)