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

Maël Pégny

pp. 39-67

in: Joseph Vidal-Rosset (ed), Alan Turing, Philosophia Scientiae 16 (3), 2012.

Abstract

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.

Cited authors

Turing Alan