In a previous paper [ 1 ], we have studied a basic machine B
that is an example from a large class of similar machines which we
shall refer to as the two-storage general machines. The characteristics
of this class are as follows. (i) Each two-storage general machine
has an indefinitely expandable internal parallel storage to keep the
program, and an indefinitely expandable, tape that is divided into a
sequence of squares, to be used for input, output, computation, and
storage of intermediate data. (ii) Each machine has a (reading-
writing) head which scans one and only one square of the tape at every
moment and which can perform every one of a predetermined finite
class of types of action including at least shift left one square, shift
right one square, one way of changing the content of the square under.
its scan (e.g. making a given mark or erasing). (iii) There is a control
element which at every moment attends to one and only one program
step (in particular, the first step at the beginning of the operation)
and the square currently under the scan of the reading head; in ac-
cordance with the step and the content of the square under attention,
the control element also either directs the reading head to perform
one of its acts or shifts itself to attend to a different program step
specified in the step currently observed; we may imagine that the
movement of the reading head or the control element always takes place
between two time units. (iv) Each square on the tape is capable of
at least two states; the control element and the permissible program
steps are such that the control element is sometimes capable of choos-
ing from two or more preassigned alternative program steps as the
next to follow according to the state of the square currently under
scan; in particular, if one of the two alternative next steps is always
the immediately following in the original program, then the state of
the scanned square which is capable of producing a jump must be
among those states which can be introduced by the possible actions
of the reading head.

The basic machine B is a minimum among those which satisfy
these conditions: its reading-writing head can only do three things,

-160-