Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Thèse de Church-Turing

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 effectivement réalisable (tout algorithme, si l'on appelle algorithme la description d'un calcul 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.

Formes équivalente de la thèse

La thèse peut être reformulée en disant que les machines de Turing formalisent correctement la notion de procédé de calcul effectif ou (ci-dessous) méthode efficace. On considère généralement qu'une méthode efficace doit satisfaire aux obligations suivantes :

1. La méthode consiste dans un ensemble fini d'instructions simples et précises qui sont décrite avec un nombre limité de symboles.
2. La méthode doit toujours produire le résultat dans un nombre fini d'étapes.
3. La méthode peut en principe être suivie par un humain avec seulement du papier et un crayon.
4. L'exécution de la méthode 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 euclidien 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éfinition, intuitive et formelle, concordent.

Origines de la thèse

En 1936 Alonzo Church publia « Une note sur le Problème de la décision » et Alan Turing quelques mois plus tard « Sur les Nombres traitables, avec une application au problème de la décision ».

Succès de la thèse

Depuis cette époque d'autres formalismes pour décrire un traitement efficace ont été proposés comme « Machine à registres », Systèmes d'Emil Post, Combinatoire définisable, et Algorithme de Markov. Tous ces systèmes ont démontré traiter essentiellement les mêmes fonctions que les machines de Turing ; les systèmes comme ceux-là sont appellés Turing-complet. Parce que tous ces essais différents à formaliser le concept d'algorithme ont conduit à des résultats équivalents, il est désormais accepté que la thèse Church-Turing est exacte. Cependant, la thèse n'a pas le status d'un théorème et ne peut pas être prouvée ; Elle peut être réfutée si une méthode peut être montrée qui est acceptée universalement comme étant un algorithme effectif mais lequel ne peut pas être effectué par une machine de Turing.

Au début du 20^e siècle, les mathématiciens utilisaient souvent l'expression informelle traitable avec efficacité, aussi il était important de trouver une bonne formalisation du concept. Les mathématiciens modernes au contraire utilisent le terme bien défini traitable à la Turing (ou traitable en raccourci). Depuis que la terminologie non définie n'est plus utilisée, la question de comment définir est maintenant moins importante.

implications philosophiques

Cette thèse a eu quelques implications profondes pour la philosophie de l'esprit. Il y a aussi certaines questions importantes ouvertes qui couvrent la relation entre cette thèse et la physiologie, et la possibilité d'hypercomputation. Quand appliqué à la physiologie, la thèse a plusieurs signification possible :

1. L'univers est une machine de Turing (et donc, les fonctions de traitement non récursif sont physiquement impossible). Cela a été intitulé la thèse forte Church-Turing.
2. L'univers n'est pas une machine de Turing (c.-à-d., les lois de la physique ne sont pas traitables à la Turing), mais des évènements physiques ne sont pas « harnachable » pour la construction d'hypertraitement. Par exemple, un univers dans lequel la physique implique des Nombres réels, par opposition aux nombres traitables, pourrait tomber dans cette catégorie.
3. L'univers est un hypertraitement, et il est possible de contruire des objets réels pour harnacher cette propriété et calculer des fonctions non récursives. Par exemple, il y a une question ouverte si tous les évènements en mécanique quantique sont traitables à la Turing, bien qu'il ait été prouvé que n'importe quel système construit des Qubits est (au mieux) complètement Turing. John Lucas (et bien connu, Roger Penrose) ont suggéré que l'esprit humain pourrait être le résultat d'un hypertraitement quantique.

Il y a actuellement de nombreuses possibilités techniques qui tombent en dehors ou entre ces trois catégories, mais elles devraient servir à illustrer le concept.

Voir aussi

• Résultats efficaces dans la théorie des nombres