Book contents
- Frontmatter
- Contents
- Preface to the Fifth Edition
- COMPUTABILITY THEORY
- 1 Enumerability
- 2 Diagonalization
- 3 Turing Computability
- 4 Uncomputability
- 5 Abacus Computability
- 6 Recursive Functions
- 7 Recursive Sets and Relations
- 8 Equivalent Definitions of Computability
- BASIC METALOGIC
- FURTHER TOPICS
- Annotated Bibliography
- Index
3 - Turing Computability
Published online by Cambridge University Press: 05 June 2012
- Frontmatter
- Contents
- Preface to the Fifth Edition
- COMPUTABILITY THEORY
- 1 Enumerability
- 2 Diagonalization
- 3 Turing Computability
- 4 Uncomputability
- 5 Abacus Computability
- 6 Recursive Functions
- 7 Recursive Sets and Relations
- 8 Equivalent Definitions of Computability
- BASIC METALOGIC
- FURTHER TOPICS
- Annotated Bibliography
- Index
Summary
A function is effectively computable if there are definite, explicit rules by following which one could in principle compute its value for any given arguments. This notion will be further explained below, but even after further explanation it remains an intuitive notion. In this chapter we pursue the analysis of computability by introducing a rigorously defined notion of a Turing-computable function. It will be obvious from the definition that Turing-computable functions are effectively computable. The hypothesis that, conversely, every effectively computable function is Turing computable is known as Turing's thesis. This thesis is not obvious, nor can it be rigorously proved (since the notion of effective computability is an intuitive and not a rigorously defined one), but an enormous amount of evidence has been accumulated for it. A small part of that evidence will be presented in this chapter, with more in chapters to come. We first introduce the notion of Turing machine, give examples, and then present the official definition of what it is for a function to be computable by a Turing machine, or Turing computable.
A superhuman being, like Zeus of the preceding chapter, could perhaps write out the whole table of values of a one-place function on positive integers, by writing each entry twice as fast as the one before; but for a human being, completing an infinite process of this kind is impossible in principle.
- Type
- Chapter
- Information
- Computability and Logic , pp. 23 - 34Publisher: Cambridge University PressPrint publication year: 2007