Thèse de Church-Turing

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

La thèse de Church-Turing, ou simplement thèse de Church, des noms des mathématiciens Alonzo Church et Alan Turing, est une idée qui se rattache au domaine de l'informatique. Dans sa forme la plus ordinaire, elle affirme que tout traitement réalisable mécaniquement peut être accompli par une machine de Turing. Tout programme d'ordinateur peut donc être traduit en une machine de Turing.

D'autre part, certaines machines de Turing, dites universelles, peuvent effectuer tous les traitements possibles avec une machine de Turing quelconque. La plupart des langages de programmation usuels ont (plus exactement, auraient sur un ordinateur disposant d'une mémoire infinie) les possibilités de calcul d'une machine de Turing universelle, de sorte que toutes les machines de Turing peuvent être simulées par un programme écrit dans l'un de ces langages. La thèse de Church-Turing affirme donc que n'importe quel langage de programmation (Turing-complet) permet d'exprimer tous les algorithmes.

La thèse de Church-Turing est généralement considérée comme vraie. Mais ce n'est pas un énoncé mathématique : chercher à la démontrer n'a pas de sens. Elle serait en revanche réfutée si un calcul que l'on s'accorde à considérer comme réalisable mécaniquement s'avérait hors de portée des machines de Turing.

[modifier] Formes équivalentes de la thèse

La thèse peut être reformulée en disant que les machines de Turing 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 :

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.

Un exemple d'une telle méthode est l'algorithme d'Euclide pour déterminer le plus grand commun diviseur d'entiers naturels.

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 les algorithmes comme les procédés qui peuvent être accomplis par une machine de Turing universelle. À ce stade, la thèse de Church-Turing affirme que les deux définitions, intuitive et formelle, concordent.

[modifier] Succès de la thèse

D'autres formalismes ont été proposés pour modéliser les fonctions calculables mécaniquement, notamment le lambda-calcul, les fonctions récursives et les machines à registres. On peut montrer que toutes ces définitions, bien que fondées sur des idées assez différentes, décrivent (à la traduction des notations près) exactement le même ensemble de fonctions que les machines de Turing. Ces systèmes, qui ont le même pouvoir d'expression que les machines de Turing, 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 un argument important à l'appui de la thèse de Church-Turing.

D'autre part, au début du XX^e siècle, les mathématiciens utilisaient souvent des expressions informelles comme effectivement réalisable, aussi il était important de trouver une bonne formalisation du concept. Les mathématiciens modernes au contraire utilisent la notion bien définie de fonction calculable. Depuis que la terminologie non définie n'est plus utilisée, la question de comment définir est moins importante.

[modifier] Implications philosophiques

Certains pensent que la thèse de Church-Turing a d'importantes conséquences en philosophie de l'esprit. Certaines questions importantes concernant la relation entre cette thèse et la physique restent également ouvertes. La thèse peut alors être interprétée de différentes manières :

L'univers est une machine de Turing - calculer des fonctions non-récursives est donc physiquement impossible. Cette interprétation est aussi appelée thèse de Church-Turing forte et constitue un fondement de la physique numérique.
L'univers n'est pas une machine de Turing (c.-à-d que les lois de la physique ne sont pas Turing-calculables), mais les évènements physiques ne sont pas « domesticables » pour la construction d'un hypercalcul. Par exemple, un univers dans lequel les nombres réels seraient une conséquence de la physique, par opposition aux nombres réels calculables, pourrait entrer dans cette catégorie.
L'univers est un hypercalculateur, et il est possible de construire des objets réels pour domestiquer cette propriété et calculer des fonctions non récursives. Par exemple, la question de savoir si tous les évènements de la mécanique quantique sont Turing-calculables est ouverte, bien que l'on sache que des modèles formels tels que les machines de Turing quantiques sont équivalents aux machines de Turing déterministes. John Lucas (et plus notoirement Roger Penrose) ont suggéré que l'esprit humain pourrait être le résultat d'un hypercalcul quantique. Cependant il n'existe aucune preuve scientifique de cette proposition.

De nombreuses autres possibilités techniques n'entrent pas dans ces trois catégories, qui sont exposées ici à titre d'exemple.