Journal of Symbolic Logic 48 (3):797-803 (1983)

The modern theory of computability is based on the works of Church, Markov and Turing who, starting from quite different models of computation, arrived at the same class of computable functions. The purpose of this paper is the show how the main results of the Church-Markov-Turing theory of computable functions may quickly be derived and understood without recourse to the largely irrelevant theories of recursive functions, Markov algorithms, or Turing machines. We do this by ignoring the problem of what constitutes a computable function and concentrating on the central feature of the Church-Markov-Turing theory: that the set of computable partial functions can be effectively enumerated. In this manner we are led directly to the heart of the theory of computability without having to fuss about what a computable function is.The spirit of this approach is similar to that of [RGRS]. A major difference is that we operate in the context of constructive mathematics in the sense of Bishop [BSH1], so all functions are computable by definition, and the phrase “you can find” implies “by a finite calculation.” In particular ifPis some property, then the statement “for eachmthere isnsuch thatP” means that we can construct a functionθsuch thatP)for allm. Church's thesis has a different flavor in an environment like this where the notion of a computable function is primitive.One point of such a treatment of Church's thesis is to make available to Bishopstyle constructivists the Markovian counterexamples of Russian constructivism and recursive function theory. The lack of serious candidates for computable functions other than recursive functions makes it quite implausible that a Bishopstyle constructivist could refute Church's thesis, or any consequence of Church's thesis. Hence counterexamples such as Specker's bounded increasing sequence of rational numbers that is eventually bounded away from any given real number [SPEC] may be used, as Brouwerian counterexamples are, as evidence of the unprovability of certain assertions.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2273473
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 53,548
Through your library

References found in this work BETA

Computable Analysis.Oliver Aberth - 1984 - Journal of Symbolic Logic 49 (3):988-989.
An Introduction to the General Theory of Algorithms.Michael Machtey & Paul Young - 1981 - Journal of Symbolic Logic 46 (4):877-878.
Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.

Add more references

Citations of this work BETA

Metric Spaces in Synthetic Topology.Andrej Bauer & Davorin Lešnik - 2012 - Annals of Pure and Applied Logic 163 (2):87-100.
Diagonalisation and Church's Thesis: Kleene's Homework.Enrique Alonso & Maria Manzano - 2005 - History and Philosophy of Logic 26 (2):93-113.
On Local Non‐Compactness in Recursive Mathematics.Jakob G. Simonsen - 2006 - Mathematical Logic Quarterly 52 (4):323-330.

Add more citations

Similar books and articles

Why, Tears! Is It? Tears.Howard Fulweiler - 1990 - Thought: Fordham University Quarterly 65 (4):486-493.
The Church-Turing Thesis.B. Jack Copeland - 2008 - In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab, Stanford University.
The Church-Turing Thesis: A Last Vestige of a Failed Mathematical Program.Carol Cleland - 2006 - In A. Olszewski, J. Wole'nski & R. Janusz (eds.), Church's Thesis After Seventy Years. Ontos Verlag. pp. 119-146.
SAD Computers and Two Versions of the Church–Turing Thesis.Tim Button - 2009 - British Journal for the Philosophy of Science 60 (4):765-792.
Proving Church's Thesis.Robert Black - 2000 - Philosophia Mathematica 8 (3):244--58.


Added to PP index

Total views
46 ( #208,482 of 2,348,447 )

Recent downloads (6 months)
1 ( #511,012 of 2,348,447 )

How can I increase my downloads?


My notes