Church's Thesis and the Conceptual Analysis of Computability
Citations Over TimeTop 16% of 2007 papers
Abstract
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.
Related Papers
- → The Psychological Limits of Neural Computation(1998)1 cited
- → Computable Diagonalizations and Turing’s Cardinality Paradox(2014)1 cited
- → Turing Machines and Effective Computability(1997)
- → Turing Machines and Language Theory(1988)
- Об асимптотике сложности машин Тьюринга, вычисляющих некоторые бесконечные семейства функций(2008)