Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-18T09:17:42.835Z Has data issue: false hasContentIssue false
  • English
  • Français

How to Program an Infinite Abacus

Published online by Cambridge University Press:  20 November 2018

Joachim Lambek
Joachim Lambek*
Affiliation:
McGill University
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

This is an expository note to show how an “infinite abacus” (to be defined presently) can be programmed to compute any computable (recursive) function. Our method is probably not new, at any rate, it was suggested by the ingenious technique of Melzak [2] and may be regarded as a modification of the latter.

By an infinite abacus we shall understand a countably infinite set of locations (holes, wires etc.) together with an unlimited supply of counters (pebbles, beads etc.). The locations are distinguishable, the counters are not. The confirmed finitist need not worry about these two infinitudes: To compute any given computable function only a finite number of locations will be used, and this number does not depend on the argument (or arguments) of the function.

Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 4 , Issue 3 , September 1961 , pp. 295 - 302
Copyright
Copyright © Canadian Mathematical Society 1961

References

1. Kleene, S. C., Introduction to metamathematics, (New York, 1952).Google Scholar
2. Melzak, Z. A., An informal arithmetical approach to computability and computation, Canad. Math. Bull. 4 (1961), 279-293.Google Scholar