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
5 - Abacus 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
Showing that a function is Turing computable directly, by giving a table or flow chart for a Turing machine computing the function, is rather laborious, and in the preceding chapters we did not get beyond showing that addition and multiplication and a few other functions are Turing computable. In this chapter we provide a less direct way of showing functions to be Turing computable. In section 5.1 we introduce an ostensibly more flexible kind of idealized machine, an abacus machine, or simply an abacus. In section 5.2 we show that despite the ostensible greater flexibility of these machines, in fact anything that can be computed on an abacus can be computed on a Turing machine. In section 5.3 we use the flexibility of these machines to show that a large class of functions, including not only addition and multiplication, but exponentiation and many other functions, are computable on a abacus. In the next chapter functions of this class will be called recursive, so what will have been proved by the end of this chapter is that all recursive functions are Turing computable.
Abacus Machines
We have shown addition and multiplication to be Turing-computable functions, but not much beyond that. Actually, the situation is even a bit worse. It seemed appropriate, when considering Turing machines, to define Turing computability for functions on positive integers (excluding zero), but in fact it is customary in work on other approaches to computability to consider functions on natural numbers (including zero).
- Type
- Chapter
- Information
- Computability and Logic , pp. 45 - 62Publisher: Cambridge University PressPrint publication year: 2007