Fonctions calculables et la thèse de Church-Turing

Les fonctions calculables sont celles qu'une procédure mécanique peut évaluer, et la thèse de Church-Turing identifie cette notion informelle avec plusieurs modèles mathématiques précis qui définissent tous la même classe.

Definition

Une fonction est calculable si une machine de Turing, ou de manière équivalente une définition récursive partielle, produit son résultat pour chaque entrée où elle est définie ; la thèse de Church-Turing affirme que cette classe mathématiquement précise coïncide avec la classe intuitive des fonctions effectivement calculables.

Scope

Ce sujet couvre les machines de Turing, les fonctions récursives partielles construites à partir de fonctions de base par composition, récursion primitive et minimisation, le calcul lambda et les machines à registres, les preuves de l'équivalence de ces modèles, les machines universelles, et la thèse de Church-Turing selon laquelle ils englobent toute la computation effective.

Core questions

• Qu'est-ce qu'une machine de Turing et comment définit-elle une computation ?
• Comment les fonctions récursives partielles sont-elles générées à partir d'opérations de base ?
• Pourquoi tous les modèles de computation raisonnables définissent-ils les mêmes fonctions ?
• Quel est le statut et la signification de la thèse de Church-Turing ?

Key theories

Modèle de la machine de Turing

Une machine de Turing est un dispositif à états finis opérant sur une bande illimitée, et les fonctions qu'elle calcule formalisent la notion d'algorithme en termes de manipulation élémentaire de symboles.

Équivalence des modèles

Les machines de Turing, les fonctions récursives partielles, le calcul lambda et les machines à registres calculent tous exactement la même classe de fonctions, démontrant la robustesse de la notion de calculabilité.

Machine universelle et énumération

Il existe une machine de Turing universelle qui simule n'importe quelle machine étant donné son code, de sorte que les fonctions calculables peuvent être effectivement énumérées et traitées comme des données, ce qui constitue la base des résultats d'autoréférence.

Clinical relevance

La notion de fonction calculable est le fondement de l'informatique théorique : la machine universelle préfigure l'ordinateur à programme enregistré, l'équivalence des modèles justifie une définition unique et robuste de l'algorithme, et le cadre fournit le contexte précis dans lequel l'indécidabilité et la complexité sont étudiées.

History

En 1936, Church a défini la calculabilité effective via le calcul lambda et Turing via ses machines, et les deux notions ont rapidement été prouvées équivalentes aux fonctions récursives de Kleene. La thèse de Church-Turing qui en a résulté est devenue la définition acceptée de l'algorithme, et la machine universelle de Turing est devenue un ancêtre conceptuel de l'ordinateur à usage général.

Key figures

• Alan Turing
• Alonzo Church
• Stephen Cole Kleene
• Emil Post

Seminal works

• cutland1980
• turing1936
• sipser2013

Frequently asked questions

Certaines fonctions ne sont-elles pas calculables ?

Oui. Étant donné que les programmes peuvent être énumérés mais pas les fonctions, un argument de dénombrement montre que la plupart des fonctions ne sont pas calculables, et des exemples spécifiques tels que la fonction d'arrêt sont prouvés incalculables. La calculabilité est une véritable restriction sur les fonctions que les algorithmes peuvent évaluer.

La thèse de Church-Turing limite-t-elle ce que les ordinateurs peuvent faire ?

Elle stipule qu'aucun modèle de computation effective n'étend la classe des fonctions calculables au-delà des machines de Turing. Un matériel plus rapide ou des architectures différentes modifient l'efficacité, mais pas la limite de ce qui est calculable en principe ; la thèse établit donc une limite absolue à la résolvabilité algorithmique.