Navigation – Plan du site
Alan Turing

Les deux formes de la thèse de Church-Turing et l’épistémologie du calcul

Maël Pégny
p. 39-67

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.

Haut de page

Accès au texte / extrait

Cairn

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

Introduction

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 30 septembre 2014. URL : http://philosophiascientiae.revues.org/769 ; DOI : 10.4000/philosophiascientiae.769

Haut de page

Auteur

Maël Pégny

Université de Paris 1 (France)

Haut de page

Droits d’auteur

Tous droits réservés

Haut de page