Church's Thesis and the Conceptual Analysis of Computability
Rescorla, Michael
Notre Dame J. Formal Logic, Tome 48 (2007) no. 1, p. 253-280 / Harvested from Project Euclid
Church's thesis asserts that a number-theoretic function is intuitively computable if and only if it is recursive. A related thesis asserts that Turing's work yields a conceptual analysis of the intuitive notion of numerical computability. I endorse Church's thesis, but I argue against the related thesis. I argue that purported conceptual analyses based upon Turing's work involve a subtle but persistent circularity. Turing machines manipulate syntactic entities. To specify which number-theoretic function a Turing machine computes, we must correlate these syntactic entities with numbers. I argue that, in providing this correlation, we must demand that the correlation itself be computable. Otherwise, the Turing machine will compute uncomputable functions. But if we presuppose the intuitive notion of a computable relation between syntactic entities and numbers, then our analysis of computability is circular.
Publié le : 2007-04-14
Classification:  Church's thesis,  computation,  acceptable notation,  Turing machines,  00A30,  03A05,  03D10
@article{1179323267,
     author = {Rescorla, Michael},
     title = {Church's Thesis and the Conceptual Analysis of Computability},
     journal = {Notre Dame J. Formal Logic},
     volume = {48},
     number = {1},
     year = {2007},
     pages = { 253-280},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1179323267}
}
Rescorla, Michael. Church's Thesis and the Conceptual Analysis of Computability. Notre Dame J. Formal Logic, Tome 48 (2007) no. 1, pp.  253-280. http://gdmltest.u-ga.fr/item/1179323267/