Navigation – Plan du site
Alan Turing

Cleland on Churchs Thesis and the Limits of Computation

Clayton Peterson et François Lepage
p. 69-85

Résumés

Cet article se veut une critique de la thèse défendue par [Cleland 1993], laquelle soutient que la thèse de Church doit être rejetée puisque les limites du calcul dépendent de la structure physique du monde. Dans un premier temps, nous offrons un (très) bref aperçu de la thèse de Church puis nous présentons l argument de Cleland. Par la suite, nous proposons une analyse critique de son argument, ce qui nous amènera à faire quelques distinctions conceptuelles par rapport aux notions qui concernent la calculabilité. Finalement, nous montrons que les limites du calcul ne sont pas physiques mais bien logiques. En résumé, notre argument est que les limites du calcul sont déterminées en partie par le fait qu’une procédure effective doit pouvoir être décrite de manière finie.

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

1. Church’s thesis and Turing machines
2. Cleland’s argument
3. Critical analysis
3.1 The third argument
3.2 The computability of i(x)
3.3 The argument against Church’s thesis
3.4 The limits of computation
4. Conclusion

Aperçu du début du texte

1. Church’s thesis and Turing machines

Church s thesis emerged in reaction to the work done by various mathematicians in the 1930 s. In trying to develop a reliable method to solve mathematical problems, individuals such as Church, Gôdel, Kleene and Turing, which respectively proposed the lambda calculus, the Recursive functions, the Formal systems and the Turing machines, proposed decidable methods to compute functions [Immerman 2008, 1]. A function f : X Y is an abstract relation between two sets X and Y (where X is the domain and Y the image of f) which associates at most one member of Y to a member of X. Put differently, a function f is a set of ordered pairs < xi,yj >, with Xi X and yj e Y, and can be represented as such: f = {< xi,yj >: xi X yj Y}. A function can be total, meaning that each member of f s domain will be paired with a member of its image, or it can be partial, meaning that only members of a proper subset of f s domain will be associated with a member of...

Haut de page

Pour citer cet article

Référence électronique

Clayton Peterson et François Lepage, « Cleland on Churchs Thesis and the Limits of Computation », Philosophia Scientiæ [En ligne], 16-3 | 2012, mis en ligne le 01 novembre 2015, consulté le 21 septembre 2014. URL : http://philosophiascientiae.revues.org/772 ; DOI : 10.4000/philosophiascientiae.772

Haut de page

Auteurs

Clayton Peterson

Université de Montréal (Canada)

François Lepage

Université de Montréal (Canada)

Haut de page

Droits d’auteur

Tous droits réservés

Haut de page