eBabylone
.com

Un article de Wikipedia.y-project.com.

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.

Sommaire 1 Formes équivalentes de la thèse 2 Succès de la thèse 3 Implications philosophiques 4 Voir aussi

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

1. l'algorithme consiste dans un ensemble fini d'instructions simples et précises qui sont décrite avec un nombre limité de symboles ;
2. l'algorithme doit toujours produire le résultat dans un nombre fini d'étapes ;
3. l'algorithme peut en principe être suivie 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.

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.

[] 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.

[] 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 effectifs en théorie des nombreslt:Tiuringo tez?

DernierMirror  

Réagissez

Commentez l'encyclopédie:
Attention! tous les commentaites inaproprié seront supprimés

Titre:
Video YouTube ou google:	(doit être en rapport avec le sujet)
Votre mail:	(ne sera pas affiché sur le site)
Un pseudo:
Votre site:
Commentaire	(le html n'est pas autorisé, nombre de caractère maximum = 400)
	(Comment eBabylone 1.0 beta)

Le Texte ci-dessus est disponible sous GNU Free Documentation License.
La source est wikipedia http://fr.wikipedia.org/wiki/ thèse de Church-Turing