Résumés
La thèse de Church-Turing stipule que toute fonction calculable est calculable par une machine de Turing. En distinguant, à la suite de nombreux auteurs, une forme algorithmique de la thèse de Church-Turing portant sur les fonctions calculables par un algorithme d’une forme empirique de cette même thèse, portant sur les fonctions calculables par une machine, il devient possible de poser une nouvelle question : les limites empiriques du calcul sont-elles identiques aux limites des algorithmes ? Ou existe-t-il un moyen empirique d’effectuer un calcul qu’aucun algorithme ne permet d’effectuer ? Je montrerai ici la pertinence philosophique de cette question. Elle interroge la capacité de processus symboliques comme les calculs à simuler certains processus empiriques. Elle permet également d’étudier le statut épistémologique des calculs réalisés par des machines. S’il existait une fonction calculable par une machine sans être calculable par un algorithme, il existerait un problème mathématique qui serait soluble par un dispositif empirique, sans être soluble par aucune méthode mathématique a priori.
Church-Turing’s thesis states that every computable function is computable by a Turing machine. By distinguishing, like many authors in the recent literature, between an algorithmic form of Church-Turing’s thesis on the functions computable by an algorithm, and an empirical form of the same on the functions computable by a machine, it becomes possible to ask a new question: Are the limits of empirical calculation identical to the limits of the algorithms? Or is there a way to empirically perform a calculation no algorithm can perform? I will show the philosophical relevance of this question. It questions the ability of symbolic processes as calculations to simulate certain empirical processes. It is also essential to the epistemological status of calculations performed by machines. If there were a function computable by a machine without being computable by an algorithm, there would be a mathematical problem, which would be solvable by an empirical device, but would be unsolvable by any a priori mathematical method.
Haut de page
Accès au texte / extrait

Texte intégral disponible via abonnement/accès payant sur le portail Cairn. Le texte intégral en libre accès sera disponible à cette adresse en janvier 2016.
Consulter cet article
Plan
Introduction
1, Les deux formes de la thèse de Church-Turing
1.1 Énoncés
1.2 Machines et algorithmes : justification de la distinction
1.2.1 Les machines
1.2.2 Les algorithmes
2. La thèse A et sa pertinence philosophique
2.1 Énoncé de la thèse A
2.2 Langages formels et description de la nature
3. Remarques sur l’épistémologie du calcul
3.1 Les critères de correction du calcul
3.2 Relations de simulabilité entre ces différents modèles
4. La thèse A et le statut a priori du calcul
4.1 Le calcul papier-crayon comme connaissance a priori
4.2 Le calcul sur machines et la notion d’a priori
4.3 La thèse A et la connaissance a priori
Conclusion
Aperçu du début du texte
Selon une opinion presque universellement partagée dans la communauté informatique, la thèse de Church-Turing, selon laquelle toute fonction calculable est calculable par une machine de Turing, énonce les justes limites de la calculabilité. De nombreux auteurs, tels que R. Gandy [Gandy 1980], J. Copeland [Copeland 2003], W. Sieg [Sieg 2008], D. Deutsch [Deutsch 1985], [Deutsch 1997], Peter Smith [Smith 2007], G. Dowek [Dowek 2007] ou G. Piccinini [Piccinini 2011] ont néanmoins insisté sur la nécessité de distinguer deux formes de cette thèse de Church-Turing. La première forme, ou forme algorithmique, affirme que toute fonction calculable par un algorithme est calculable par une machine de Turing. La seconde, ou forme empirique, affirme que toute fonction calculable par une machine est calculable par une machine de Turing. Or, si la première forme est relativement consensuelle, la seconde est plus difficile à définir, et la question de sa démonstration au sein des théori...
Haut de page
Pour citer cet article
Référence électronique
Maël Pégny, « Les deux formes de la thèse de Church-Turing et l’épistémologie du calcul », Philosophia Scientiæ [En ligne], 16-3 | 2012, mis en ligne le 01 novembre 2015, consulté le 25 mai 2013. URL : http://philosophiascientiae.revues.org/769 ; DOI : 10.4000/philosophiascientiae.769
Haut de page