human
Veuillez expliquer ce qu'est la "thèse de Church-Turing"
gpt
Dans la théorie de la calculabilité , la thèse de Church-Turing (également connue sous le nom de thèse de calculabilité , la thèse de Turing-Church , la conjecture de Church-Turing , la thèse de Church , la conjecture de Church et la thèse de Turing ) est une thèse sur la nature des fonctions calculables . Il stipule qu'une fonction sur les nombres naturels peut être calculée par une méthode efficace si et seulement si elle est calculable par une machine de Turing. La thèse porte le nom du mathématicien américain Alonzo Church et du mathématicien britannique Alan Turing. Avant la définition précise de la fonction calculable, les mathématiciens utilisaient souvent le terme informel effectivement calculable pour décrire les fonctions qui sont calculables par des méthodes papier-crayon. Dans les années 1930, plusieurs tentatives indépendantes ont été faites pour formaliser la notion de calculabilité :
Church, Kleene et Turing[11] ont prouvé que ces trois classes formellement définies de fonctions calculables coïncident : une fonction est λ-calculable si et seulement si elle est calculable de Turing, et si et seulement si elle est récursive générale. Cela a conduit les mathématiciens et les informaticiens à croire que le concept de calculabilité est précisément caractérisé par ces trois processus équivalents. D'autres tentatives formelles pour caractériser la calculabilité ont par la suite renforcé cette croyance (voir ci-dessous).
D'autre part, la thèse de Church-Turing déclare que les trois classes de fonctions calculables formellement définies ci-dessus coïncident avec la notion informelle d'une fonction effectivement calculable. Bien que la thèse ait une acceptation quasi universelle, elle ne peut pas être formellement prouvée, car le concept de calculabilité effective n'est défini que de manière informelle.
Depuis sa création, des variations sur la thèse originale ont surgi, y compris des déclarations sur ce qui peut être physiquement réalisé par un ordinateur dans notre univers (thèse physique de Church-Turing) et ce qui peut être calculé efficacement (thèse de Church-Turing (théorie de la complexité)). Ces variations ne sont pas dues à Church ou Turing, mais résultent de travaux ultérieurs en théorie de la complexité et en physique numérique. La thèse a également des implications pour la philosophie de l'esprit (voir ci-dessous).