Over the past fifty years there have been many proposals for a precise mathematical characterisation of the intuitive idea of effective computability. The URM approach is one of the more recent of these. In this chapter we pause in our investigation of URM-computability itself to consider two related questions.
How do the many different approaches to the characterisation of computability compare with each other, and in particular with URM-computability?
How well do these approaches (particularly the URM approach) characterise the informal idea of effective computability?
The first question will be discussed in §§ 1-6; the second will be taken up in § 7. The reader interested only in the technical development of the theory in this book may omit §§ 3-6; none of the development in later chapters depends on these sections.
Other approaches to computability
The following are some of the alternative characterisations that have been proposed:
(a) Gödel-Herbrand-Kleene (1936). General recursive functions defined by means of an equation calculus. (Kleene [1952], Mendelson [1964].)
(b) Church (1936). λ-definable functions. (Church [1936] or [1941].)
(c) Gödel-Kleene (1936). μrecursive functions and partial recursive functions (§ 2 of this chapter.).
(d) Turing (1936). Functions computable by finite machines known as Turing machines. (Turing [1936]; § 4 of this chapter.)
(e) Post (1943). Functions defined from canonical deduction systems. (Post [1943], Minsky [1967]; § 5 of this chapter.)
(f) Markov (1951). Functions given by certain algorithms over a finite alphabet. (Markov [1954], Mendelson [1964]; § 5 of this chapter.)
(g) Shepherdson-Sturgis (1963). URM-computable functions. (Shepherdson & Sturgis [1963].)
There is great diversity among these various approaches; each has its own rationale for being considered a plausible characterisation of computability. The remarkable result of investigation by many researchers is the following:
The Fundamental result
Each of the above proposals for a characterisation of the notion of effective computability gives rise to the same class of functions, the class that we have denoted ℘.
Review the options below to login to check your access.
Log in with your Cambridge Aspire website account to check access.
If you believe you should have access to this content, please contact your institutional librarian or consult our FAQ page for further information about accessing our content.