Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-26T21:45:26.270Z Has data issue: false hasContentIssue false
  • English
  • Français

An Informal Arithmetical Approach to Computability and Computation, II

Published online by Cambridge University Press:  20 November 2018

Z.A. Melzak
Z.A. Melzak*
Affiliation:
The University of British Columbia
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.

In the first part of this paper [l] there was introduced a hypothetical computing device, the Q-machine. It was derived by abstracting from the process of calculating carried out by a man on his fingers, assuming an adequate supply of hands and the ability to grow fingers at will. The Q-machine was shown to be equal in computing power to a universal Turing machine. That is, the Q-machine could compute any number regarded as computable by any theory of computability developed so far. It may be recalled here that Turing machines were obtained by Turing [2] by abstracting from the process of calculating carried out by a man on some concrete 'symbol space' (tape, piece of paper, blackboard) by means of fixed but arbitrary symbols. Hence the contrast between the Q-machine and the Turing machines is that between arithmetical manipulation of counters and logical manipulation of symbols. In particular, one might say, loosely, that in a Turing machine, as in arithmetic, numbers are represented by signs whereas in the Q-machine, as on a counting frame, numbers represent themselves.

Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 7 , Issue 2 , June 1964 , pp. 183 - 200
Copyright
Copyright © Canadian Mathematical Society 1964

References

1. Melzak, Z.A., An Informal Arithmetical Introduction to Computability and Computation, Can. Math. Bull., vol.4, no. 3, Sept. 1961.Google Scholar
2. Turing, A.M., On Computable Numbers with an Application to the Entscheidungsproblem, J. Lond. Math. Soc., Spring 1936.Google Scholar
3. Shapiro, H.S., Rational Recurrence Formulae, Comm. Pure Appl. Math., vol.12, no. 3, Aug. 1959.Google Scholar
4. Cassels, J.W.S., An Introduction to Diophantine Approximation, Cambridge Univ. Press, 1957. Google Scholar