Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Thèse de Church
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Proximité ontologique
Concepts associés (15)
Computability
Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem. The most widely studied models of computability are the Turing-computable and μ-recursive functions, and the lambda calculus, all of which have computationally equivalent power.
Effective method
In logic, mathematics and computer science, especially metalogic and computability theory, an effective method or effective procedure is a procedure for solving a problem by any intuitively 'effective' means from a specific class. An effective method is sometimes also called a mechanical method or procedure. The definition of an effective method involves more than the method itself. In order for a method to be called effective, it must be considered with respect to a class of problems.
Fonction (mathématiques)
vignette|Diagramme de calcul pour la fonction En mathématiques, une fonction permet de définir un résultat (le plus souvent numérique) pour chaque valeur d’un ensemble appelé domaine. Ce résultat peut être obtenu par une suite de calculs arithmétiques ou par une liste de valeurs, notamment dans le cas de relevé de mesures physiques, ou encore par d’autres procédés comme les résolutions d’équations ou les passages à la limite. Le calcul effectif du résultat ou son approximation repose éventuellement sur l’élaboration de fonction informatique.