Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T16:10:40.639Z Has data issue: false hasContentIssue false

An Informal Arithmetical Approach to Computability andComputation, II

Published online by Cambridge University Press:  20 November 2018

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 hypotheticalcomputing device, the Q-machine. It was derived by abstracting from theprocess of calculating carried out by a man on his fingers, assuming anadequate supply of hands and the ability to grow fingers at will. TheQ-machine was shown to be equal in computing power to a universal Turingmachine. That is, the Q-machine could compute any number regarded ascomputable by any theory of computability developed so far. It may berecalled here that Turing machines were obtained by Turing [2] byabstracting from the process of calculating carried out by a man on someconcrete 'symbol space' (tape, piece of paper, blackboard) by means of fixedbut arbitrary symbols. Hence the contrast between the Q-machine and theTuring machines is that between arithmetical manipulation of counters andlogical manipulation of symbols. In particular, one might say, loosely, thatin a Turing machine, as in arithmetic, numbers are represented by signswhereas in the Q-machine, as on a counting frame, numbers representthemselves.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1964