THE UNIVERSITY OF MICHIGAN
INDUSTRY PROGRAM OF THE COLLEGE OF ENGINEERING
n-HEAD FINITE STATE MACHINES
Thomas Frank Piatkowski
A dissertation submitted in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy in the
University of Michigan
Department of Electrical Engineering
1963
December, 1963
IP- 646

ACKNOWLEDGEMENTS
I would like to express my graditude to Professors
H. L. Garner, B. A. Galler, J. H. Holland, E. L. Lawler, and
N. R. Scott for serving on the doctoral committee under which
this paper was written. I would especially like to thank Professor
H. L. Garner, my chairman, for the assistance he gave me in selecting a thesis topic. Also I would like to voice my sincere appreciation to Professors Galler and Holland and to Dr. Jesse Wright,
Mr. Philip Dauber, and Mr. Rodolfo Gonzales for their valuable discussions which contributed to the quality of this paper.
The research reported in this paper was supported by
Wright-Patterson Air Force Contract AF 33(657)-7391.
ii

TABLE OF CONTENTS
Page
ACKNOWLEDGEMENTS.............................................. ii
LIST OF FIGURES................................. eomo*oeo. o o ooe * v
I INTRODUCTION.................................................. 1
II n-HEAD FINITE STATE MACHINES - A DESCRIPTION................... 4
Alphabets. o............................................. 4
Tapes o....o..o....o.. o o. e o o e e o o o o e o o o o o 4
Machines....o.....o.o.......................... e..... o... 7
State Graphs..e.. e................................... 11
III THE LANGUAGE o........................................ 18
Operations on Alphabets........................ 18
Operations on Partial Tapes................................... 19
Operations on m-tuples of Partial Tapes......24
Operations on Sets of m-tuples of Partial Tapes................ 25
Regular Expressions...... o.. o............................ 27
IV EQUIVALENCE THEOREMS...... o.... o o.............. o......... 29
1-way 1-dim 1-head Machines.................. o. O............O 29
1-way 1-dim n-head Machines.............. o*o..............o. 34
2-way 1-dim 1-head Machineso o....o e o. o....... o.......... 38
2-way D-dim 1-head Machines.............. o....oe..o....... 43
2-way D-dim n-head n-tape Machines.......................... 45
2-way D-dim n-head m-tape Machines....o...ooo.............O 48
V ASSORTED ALGORITHMS AND THEOREMS DEALING WITH THE DECISION
PROBLEMS AND SPEED OF OPERATION OF n-HEAD MACHINES, O..O o...... 53
Algorithm for Deciding 1-wayness of Machines................. 53
Algorithm for Deciding Realizability of Regular Expressions.... 55
1-way 2-head Equivalents of 2-way 1-dim 1-head Machines........ 56
The "Particular Input" Decision Problem........................ 64
The Emptiness Decision Problem.......o.......oIto............O* 66
Boolean Properties of n-head Machines........................ 70
Speed Theorems.................. o..........o............... 73

TABLE OF CONTENTS (CONT'D)
Page
VI TOPICS FOR FURTHER STUDY.................................... 81
Reduction Problems...............................oooo 81
1. Head Reduction..... O...................................... 81
2, State Reduction............................................ 83
3. Speed Reduction..........................................e 84
Representability Problems................................ 85
VII SUMMARY....................................................... 87
BIBLIOGRAPHY. OOO....................................................... 92

LIST OF FIGURES
Figure Page
2o1 Tape t1.......................................... 5
2.2 Tape t2`.................................. 6
2.3 Subtape t............................... 7
2.4 State Graph of12
State Graph of (C2.1................................12
2.5 Simplified State Graph of 2.1.....................13
2.6 Machine OC 2.2......,I "...o...................17
4.1 Machine QO 4.1............................ 30
4.2 Machine OC'4.2..................................oo...32
4.3 Machine a.... 4.2*......................... * *. 33
4.4 Machine C34.3.....35
4.5 Machine 0:4.4..................... 37
4.6 Machine OC44..4............................... 37
4.7 Machine OC4...1~~~~~~~.,.,.......40
4.8 Machine 0.4...-. -4..................................42
4.9 Machine Ot4.6.......'..'........43
4.11 Machine 0(4.......... *..................44
4.12 Machine Ot 4....44.................................. 44
4.13 Machine C4 9............................................ 46
4.14 Machine O 41. 9...................................46
4.15 Machine 0% 4.10......................6...................47
4.16 Machine O( 4.10..........*................................ 48

LIST OF FIGURES (CONT'D)
Figure Page
4.17 Machine OL4.11......................................... 50
4.18 Machine OL 4.12........................................... 52
5.1 Machine O 51, 0.................. 61
5.2 Machine (5.1)..................................... 63
5.3 Machine O 5............................................ 72
5.4 Form of Tapes in Ak.......... oooe...o.................. 76
6.1 Machine Ot 6. 1 o...............o -.....-...oo o.o..... 84
6.2 Machine Ot 6.2.............. — * o....... 84
vi

CHAPTER I
INTRODUCTION
The field of finite automata is not a new one and many authors
have contributed significantly to it. However, except for an occasional
instance, the literature is barren of discussion dealing with multiplehead automata, The subject is not without merit for multiple-head automata possess capabilities beyond those of single-head machines -- capabilities yet to be thoroughly explored.
This paper extends the results of automata theory beyond the
usual limit of one-dimensional one-tape single-headed non-halting finite
state machinesto encompass, in the most general case, multi-dimensional
multi-tape multi-head self-halting finite state machines.
A familiarity with the material contained in the papers by
McNaughton and Yamada(3), E. F. Moore(4), Minsky(5) and Rabin and
Scott(6) will be necessary and sufficient for an intelligent reading
of this paper. Established results of other persons will usually be
stated and used without proof. The author has attempted to give proper
credit to the work of others. Thus, all theorems and remarks contained
in this paper which are not credited to others are, to the best of the
author's knowledge, original.
The material presented in this paper is arranged into seven
chapters.
Chapter I is the introductions Chapter II introduces the
concepts of alphabet, tape, and n-head machine. The operation of
n-head machines on tapes is defined and the manner in which n-head
-1

-2machines accept and reject inputs is described along with the notion
of how n-head machines define sets of inputs. Chapter III presents
a number of operations on alphabets, tapes and sets of tapes which
constitutes a language by which, beginning with primitive alphabets
one can represent certain sets of m-tuples of tapes. The language
developed in this chapter includes as one of its parts the language
of regular expressionso Chapter IV contains a set of six pairs of
analysis-synthesis theorems relating the sets of inputs defined by
n-head machines to expressions in the language of Chapter IIIo. The
theorem pairs are ordered according to the complexity of the machines
involved, beginning with 1-way 1-dim 1-head machines and terminating
with 2-way D-dim n-head m-tape machines, Chapter V consists of a
collection of algorithms and theorems pertaining to n-head machines.
In particular, algorithms are given to decide if any given n-head
machine is 1-way and to decide if any given regular expression is
realizable. The chapter also develops theorems dealing with the
questions:
1) Does a given machine accept a given input (the "particular input decision question")?
2) Does a given machine accept any input (the "emptiness
decision question")?
3) What is the relationship between state and transition
accessibility and the emptiness decision question?
4) What are the Boolean properties of n-head machines?
5) What is the relationship between the number of heads
a particular machine possesses and the speed with
which this machine reacts to inputs?

-3Chapter VI suggests several topics for further study. The topic areas
are described and some partial results pertinent to each area are given.
Chapter VII is the concluding chapter. In it the results of the paper
are summarized and discussed.

CHAPTER II
n-l1EAD FINITE STAITE MACHINES - A DESCRIPTION
Alphabets
Def 2.o.1 An alphabet is a finite collection of symbolso
By convention alphabets will be denoted by some variation on
the letter Z0 Thus 1 = B, O, 1, = iBa,b,c} and =,
are all examples of alphabetso
Tapes
Def. 2.2 If D is a positive integer then D-space is defined as a
space of dimension D in which a Cartesian cocLdinate system has been
embedded) each coordinate ranging over the integers from -o to +oo;
around each coordinate point is centered a unit D-cube called a cell0
Thus D-space consists of a D-dimensional space divided and
covered by an orderly array of unit D-cubes (or cells) where each cell
is labelled with a unique coordinate point~
Defo 2.3 Let Z be a alphabet; t is defined as a D-dimensional (D-dim)
tape over Z if t consists of a D-space in which each cell contains
precisely one element of Z.
We adopt the convention that a cell in which no symbol is
written will be called empty; a cell containing a symbol will be called
filled. It follows from the definition of tape that if t is a tape in
some D-space then every cell in that D-space is filled.
In this paper the symbol B will be used exclusively to denote
the blank. B is a legitimate possible symbol in any alphabet. Any

-5cell of any tape will be considered blank if and only if it contains
B.
Def. 2.4 Any tape t will be a finite tape if and only if t contains
a finite number of non-blank cells.
If t is a finite tape of dimension D it is equivalent to
say that the non-blank portion of t can be enclosed in a rectangular
D-dimensional parallelepiped of finite dimensions. In this paper we
will limit consideration to arbitrarily large but finite tapes. Therefore whenever the term "tape"' is used it will be understood that
"finite tape" is implied.
Def. 2.5 The initial cell of any tape will be that cell located at the
origin of that tape's coordinate system.
It will be convenient to omit explicit representation of the
coordinate system of a tape; in such cases the initial cell of the tape
will be indicated by a double boundary and the coordinate directions
established by prior convention. In this paper for all 1-dim and 2dim tapes the up, down, left, right directions will be respectively
the coordinate directions +2, -2, -1, +1.
For example, Figure 2.1 gives an illustration of a l-dim
tape over f = {B,a} and Figure 2.2 gives an illustration of a 2-dim
tape over = {B,O,l}.
B B a aml a B B
Tape t1
Figure 2.1

-6B B B B B B B B B. 00 1 B B B:B B
*B B B 1 B B B B B
0 B B B 1 B B B B B
B B B 1 B I B 1 B.
*eB B B B B 0 0 B.
BB 1 1 B B B B B.' B 0 I B B B B B
B B B B B eB B B
~'B0 5 0 B IV
Tape t2
Figure 2.2
Def 2.6 Let Z be an alphabet; tI is defined as a D-dim partial tape
over Z if t' consists of a Dspace in which a finite number of cells
contain precisely one element of Z, all other cells being empty.
Def, 2.7 If t is a tape9 t, is defined as a subtape of t if and only
if t is a partial tape of the same dimension as t and for each filled
cell in ts the corresponding cell of t contains the same symbol.
Thus, for example9 t2s given in Figure 2.3 is a subtape of
t2 (t2 is given in Figure 2.2).

-7ii i i
B 1
B B B B __
B 1 1
Subtape t2
Figure 2.3
Def. 2.8 If one is in any cell of a D-space with the coordinate axes
identified from the 1-st to the D-th, to move d where d is some
integer in the range -D < d < D is defined as moving one cell in the
Idl direction, negative d meaning backward, positive d meaning forward
and zero d meaning no move.
Machines
Def. 2.9 An n-head finite state machine (or just n-head machine) is a
system QL= < C,SsI M > where
Co the characterization of the machine is a list of
a) the set of heads H = {hi},i = 1,2,. on
b) a partitioning of H into disjoint subsets
His H2,.., Hm (m < n); O works on m tapes,
the heads of Hi reading tape ti
c) two sets {Zi} and {Di}, i = 1,2,.o.,m where Ci
is the alphabet that all the heads in Hi read in
common and where Di is the dimension of the space
(tape) in which the heads of Hi move.

-8S: a finite non-empty set which together with the states
"ACCEPT" (abbreviated A) and "REJECT" (abbreviated R)
which are not in S make up the set of internal states
of OLo
sI~ an element of S designated as the initial state of OH
M: a mapping from
S x.ox ElxX Z X *....X. -1 X.. X....X Z
_.~xoox _J
H1 Em
to
S x D X. D- x.. Dox o x D_ x o.. Dm U {,ARI
Hl1 1 1-: m Hr
where Hi. = the number of elements in H.
and Di = {dld is an integer in the range -Dito +D.;
M constitutes the table of transitions of aQ.
Def. 2.10 = < C,S,sI,M > accepts or rejects any m-tuple of tapes
t = (tl, t2,..., tm) in the following manner [it is understood that
for i = 1,2,...,m ti is a Di-dim tape written over ]i in accordance
with C ofZCt]:
1) O starts in state sI with all the heads of each Hi
resting on the initial cell of each til
2) If OL is in state sk and the heads read the n-tuple
of symbols a
(an d 0 x x L 2 Xo.X l X h aX0 D ot)
H1 Hm
and M of at has the entry

-9(Sk,c) X (S2 l%,.d2.. dn)
where (dl,d2,..., dn) x...x Dx D2.. D.. D
H1 Hm
then O goes to state sQ and each head hi of At moves dio
3) QO continues to repeat step 2 above; the heads of OL move
back and forth on their respective tapes and the machine
passes through a sequence of internal states. If in a
finite number of cycles CO goes into the A(R) state then
the machine stops and is said to accept (strongly reject)
t. If Om never goes into A or R then O is said to
weakly reject to
Example 2.1 a 2 = < Ci'Sl'SIM1 > where
C1 = 2.1is a 2-head machine operating with both heads
reading the same 1-dim tape written over 1 = (B,O,1}
S1 = {s1' 2}
I
S1 = S1
M1 = BO BB O 00 01 1 11
S1s o o 2 -:' ~, o1 ~. Is'-1' 1, O,.. 0,so
S2 oA lR 2,-1, R R R s2I 1,1
2.1 accepts the tapes
B O 0 1 0 0 1 B B
~ - B I o I O 1 1 Io 1 B B.B B lo l''B 11I O l lB!iB B l-*

-10while strongly rejecting
B O B I0II 1 1 B
and weakly rejecting
B 1 0 0o 1 BT
Def. 2.11 Given any internal state s of machine a~ which works over
m-tuples of tapes, s is said to be accessible (an accessible state)
if and only if there is some input m-tuple that takes (X from sI to s.
Defo 2.12 Given any transition T of (O (a transition of CL is an
entry in the M'table of Ot) corresponding to reading the n-tuple of
symbols a while being in state s, T is said to be accessible (an
accessible transition) if and only if there is some input m-tuple
that takes OL from sI to s and presents a with input a.
Note 2.1 If T is an inaccessible transition of machine OL(as is, for
example, the transition on sl,O,B in 02.1 of example 2.1) then the
destination state and the head movement of T can be left unspecified
without affecting the behavior of Ot
Def. 2.13 Ct, an n-head machine, is called 1-way if an only if for
each head h. of Oa on all accessible transitions of AL h. moves a
17_~~~~~ i~~1
fixed direction di. If O is not 1-way it is 2-way.
Note 2.2 It is sufficient but not necessary that aO be 1-way if all
transitions specify the same head movements. Clearly inaccessible
transitions can have any head movement at all and never affect the
operation of G L

-11Defo 2.14 The set of all m-tuples of tapes accepted by any n-head
finite state machine Ot is denoted by T(Ol)>
Def. 2o15 If Ot is any n-head machine working on single tapes and
t any tape in T(Ot) then g L(t), the generator of Ot in t, is defined
as that subtape of t in which the filled cells are precisely those
cells of t that Ct actually scans -while accepting to If Ot works
on m-tuples of tapes and t is any m-tuple in T(Ot) then gat(t) is
the m-tuple of subtapes derived by retaining as filled only the cells
actually scanned in accepting to
For example
t =.o I, B B1 O B 1 0 1010 1 B B j oo
is in T(OL1) [see example 2o1] and
g.H,(t) B 0 0 1 0 0 1 1 B:B..Ir 0 I0 1 0 I0 11
Defo 2,16 The set of all generators accepted by any n-head finite
state machine OC is denoted by G(Ot)o G(Ot) = {g ot)jteT(L)}o
State Graphs
As in example 2ol any n-head finite state machine
AO = <C,S,si,M > can be described by listing the set of states S,
mentioning the initial state sI, and by giving the'table of moves
M in tabular form. There is, however, a convenient graphical representation of any finite state machine known as the state graph~ In
it the set of internal states is represented as labelled circles.

-12The initial state is indicated by an inscribed square. Transitions
are represented by labelled arrows such that if an arrow emanates
from state sk and impinges on state sg and is labelled with the
symbol o/d then Ot when in state sk and reading n-tuple o will
fall into state sQ with head movements according to n-tuple d.
For example, the state graph of machine'~ is given
2.1l
in Figure 2.4 below.
(i~~~~0010I~/l 1,17.1.
il/1,0 /,
0,>X)'I R'J~'
Si B, 1/ I,\ I
State Graph of O.21
Figure 2.4
Note 2.3 If in any machine CL several inputs l,)2, *.., cp all
causes 0t to go from state'sk to state sf, with associated head
movements dt,d2,,o., dp then only one arrow will be drawn from sk

-13to s. in Ot's state graph and it will be labelled al /dl, 2/d2, ap/d.
If d1 = d2 = o do = dp one may further simplify the arrow label to
C1? 22 oo.n ap/do
Note 2.4 In order to simplify the drawing of state graphs this paper
will adopt the convention that the R state and all transition arrows
to R will not be represented explicitly. One will understand that
given any machineOC in some state sk and reading the input n-tuple
of symbols a, if no arrow with the input label a leaves sk then Ot
will go to REJECT. This convention in no way alters the behavior of
any machine for T(Ot) and G(Ot) remain unchanged as does the ability
of Ot to strongly or weakly reject any tape.
Applying the conventions of Notes 2.3 and 2.4 to O
2.1
yields the state graph given in Figure 2.5.
(0,o),(0,1)/,, (B,o),((B 1)/- Bq Bx.
lD),(1,1) /,0t Si..-...t A )
Simplified State Graph of L2.1
Figure 2.5
Note 2.5 Since this paper is concerned only with finite tapes it
follows that all tapes to be considered must contain the symbol B
an infinite number of times. Because of this we will require all
heads of all machines to include B in their alphabets.

-14Note 2.6 Observe that in the definition of any finite state machine
m
Z H. = n
i=l 1
Note 2.7 We will adopt the convention that if H = {hl, h2, oo o hn}
then the first H1 heads of H will constitute Hi, the next H2 heads
of H will constitute H2, etc.... One in no way limits the class of
n-head machines by doing this since any machine can be put in this
form by judicious labelling of the heads.
Note 2.8 In the definition of n-head machine it is required that
each head begin on the initial cell of its respective tape. One may
ask if the power of n-head machines is increased by allowing the
heads to adopt some other fixed but not initial cell starting configuration. The answer is negative: if 0L is any n-head machine in
which each head starts on some fixed but not necessarily initial cell
then there exists an n-head machine a which has all heads starting
on initial cells and which is equivalent to O (i.e., T(Ot') = T(Ot)).
The construction of 012 from aO consists of adding a set of states
so, St{ 0oo Sp to S the set of states of Ot' is the initial state
0~ p 0
of m' For all inputs Q1' has the transitions so -_ sl... s2 - s
p is made sufficiently large and appropriate movement n-tuples are
associated with each transition such that after p + 1 cycles a'e is in
state sI and the heads are in the desired starting position; from then
on 0C' acts precisely like Omo
Note 2.9 In the definition of n-head machine it is required that each
head movement be either a stand still or a unit jump along one of the
coordinate axes. One may ask if the power of n-head machines is

-15increased by allowing each head movement to be a finite determined
jump but not necessarily unit or along a coordinate direction. The
answer is negative: if Ot is any n-head machine in which each head
movement is afinite determined jump then there exists an n-head machine
(X' which has all head movements unit jumps along coordinate axes and
which is equivalent to 0. The construction of CO' from OL consists
of adding a number of states to t such that each non-unit jump is
decomposed into a chain of unit jumps, each chain replacing a nonunit jump transition.
Note 2.10 Readers familiar with the work of Kleene, Rabin and Scott,
McNaughton and Yamada, et al. may wonder at the relationship between
the machines defined by Rabin and Scott (RS machines) and the n-head
machines we have defined in this paper. RS machines and n-head
machines are both finite state deterministic machines; they do, however,
differ in several essential ways:
1) An RS machine has one reading head. An n-head
machine has n reading heads; each head may read
a different alphabet and one or more heads may
be placed on a tape.
2) An RS machine works only on 1-dim tapes. An n-head
machine can, in general, work on tapes of finite
but arbitrarily large dimension.
3) The method by which n-head machines accept or
reject tapes differs from that of RS machines.
One of the internal states of any n-head machine
is the ACCEPT state; if the machine ever goes to

ACCEPT the machine stops and is said to accept the
tape; the tape is rejected if the machine goes to
the REJECT state. An RS machine, on the other hand,
can only decide on accepting or rejecting a given
tape precisely at the moment that the reading head
leaves the filled portion of the tape and "steps off"
the tape in some manner.
Note 2,ll In a real sense, given any n-head machine 0t, G(OL) is a
better parameter of the behavior of Ot then T(Ot)o For all 0,
T(Ot) = 0 or co. This is clear since if 0t accepts no input then
T(Ot) = 0; if, however, T(Ot) $ 0 then there is at least one tl~T(TL)o
Consider goL(t1); got(tl) has an infinite number of empty cells;
therefore by filling these cells of goL(t with elements of Z, the
alphabet of t, we can generate an infinite number of distinct tapes
all in T(OL), so T(Ou) = c o. G(OL) is not limited to 0 or Ao, but can
be any integer value depending on COt
Further, if g is a generator of OL then any tape t containing
g as a subtape is accepted by aO whether t contains symbols out of the
alphabets of 01 or not (in other words the empty cells of g are "don't
care" cells whose contents do not affect the behavior of Q )o Thus
given G(Ot) we know T(OL)o
This chapter is concluded by an example, machine 012 which
demonstrates that 2-head machines are more powerful than 1-head machinest
a 2C2 is a 2-head machine reading 1-dim tapes over the alphabet
Z = {B,0,)l} aU2 2 will accept any tape which starting at the initial

-17cell and moving right has p 0's followed by p l's followed by B
where p = 1,2,3, 0 It is an established fact that such a set
of tapes cannot be represented by a 1-head machine.(6)
I(o,()'o9 1lyl I
Machine 2 2
Figure 2 6
For 0Q(2 observe that
G(22)= EgLg= l.o. [ O 1 | 1 11 oo1 |3 pI _ 1 B I
_ _ -.....-., J
P P
T(Ot, 2) {t t is 1-dim tape andZ go,3 gcG(0t2.2)}
~22 1land g is a subtape of to

CHAPTER III
THE LANGUAGE
Operations on Alphabets
Defo 31 If 1,, ~~, o, o are alphabets then the column alphabet
of 19 2 ~ ~ ~, nm denoted by
L -
is defined as the alphabet consisting of all column m-tuples over the
alphabets ZZ2,,0 0; ie
if ='I2 B 2 O
For example, if I B, and = {a,b,c} then
IBii ~ 0
Defo 3e2 If is an alphabet and D some positive integer then Z
-..
indexed by D, denoted by./D, is defined as the alphabet consisting
of all doubletons of the form a/d where aeZ and deD-; ioeo
L/D = {(a/d)jcZ, d is integer in the range -D to +DTo

-19For example, if Z = {0,1} then
Z/2 = {O/-2, o/-l, o/o0, 0/1, 0/2, 1/-2, 1/-1, i/o, i/i, 1/2}.
Operations on Partial Tapes
Def. 3.3 If t is a partial tape existing in some D-space and written
over the alphabet
then t will be understood to have m channels where the i-th channel
of t will be the tape existing in D-space and written over Z. and
obtained from t by replacing every occurrence of an element
lT2
J in iL
with the single element ao.
For example, if
t = a b ai
is a 2-dim partial tape written over [~

-20where = {a,b} and 2 = {B,O,i) then the 1-st channel of t is
b and the 2-nd channel of t is 1
|!r p Ia a | 0 | |~
Defo 3.4 If t is a partial tape over Z = then the
I
separation of t, denoted by tJ, is defined L
asthe m-tuple of partial tapes, (tl,t2, oo0, tm) where ti equals the
i-th channel of to
For example, if
a b c
B 0 1
0 B 1
then t = (a b icl m j l - j B 11 l ).
a a i ] a;]
Note 31 If t is a tape over and m = 1 then t* = t.
Defo 3~5 t will be said to be an initial partial tape if and only if
t is 1-dim and all the cells to the left of the initial cell are empty,
For example, tl= Cla B B b Ic | and t2 =.1B
are initial partial tapes and t3 = a0 B lB is not.
Defo 3%6 t will be said to be a connected partial tape if and only if
all cells of t are empty or if the initial cell of t is filled and for
any two filled cells in t there exists a string of adjacent filled
cells connecting the original two cells4

-21For example, tl =Ia1LKJFBX and t
0 B 0it
are connected while t =
and t = a are not.
4
Def. 3~7 If t is an initial connected partial tape over an alphabet
of the form Z/D then the fold of t (or t fold), denoted by tf, is
defined as the D-dim partial tape obtained from t in the following
manner
1) t = o0/d dld/d1 |a2/d2 j 0a Cpl/% C- ap/dpj
where aicZ and di D- o
2) read t from left to right, one cell at a time, and
simultaneously write out the following partial tape
t' in an originally all empty D-space~.o
a) let i = 0,
b) write o in the initial cell of the D-space
and move don
c) augment i by 1,
d) write ai in the cell under consideration
and move di,
e) repeat c,d until i = p at which time one
writes ap in the cell under consideration
and then stops.
The resulting partial tape t' will be finite (since
t was finite) and each cell of t' will contain a finite
number of elements of,o

-223) Examine the cells of t' that contain more than one
element of.o For each such cell
a) if the elements of Z that it contains are
identical, erase all but one of the elements;
the resulting D-dim partial tape is t f
b) if any one of the cells of t' contains nonidentical elements of Z then there is no
partial tape that equals tf and tf is defined
as 0, the null set.
For example,
if tl iZI1 B/o B/-l 0/-1 1/1 10/1
then t = 1 I 0,0 _B,,
and tl 1 - ~
if t =2 a/l b/l a/2 a/2 a/-l b/-l b/-2 b/-2 a/-2 c/-2 b/-l a/2 b/|
then t2 b b a
b a
a. b a
b c
a b
f_
and t = b b a
b a
a b a
b c
a b

-23if t3 = / i 0/-1 1/0
then t' 0, j
3
f
and t
Note 3 1 If ap/dp is the last symbol of some initial connected tape
t, then t is independent of dp. Therefore we can omit dp if we wish
and still define the fold operation without introducing any ambiguity.
Defo 3.8 If t1 and t2 are partial tapes of the same dimension then
the cover of t1 and t2, denoted by t1 S t2, is defined as the smallest
partial tape that contains tl and t2 as subtapes, if no such partial
tape exists then 1 Qt2 = MI
For example, if t a and t2 = b a
B a C b
then tlta t= a b a
b
but if t3 = T then tl. t3
Note 3.2 tl C t2 can be defined operationally as follows:
1) let D be the dimension of tl and t2,
2) start with an initially empty D-space; copy t1 into it,
3) copy t2 into the space; the result will be a finite
partial tape t' each cell of which contains at most
two symbols (one from tl, one from t2),
4) consider the cells of t' that contain two symbols;
for each such cell if the symbols are identical, erase
one of them.oo the resulting partial tape is tlO t2;
if any cell contains non-identical symbols then tlC t2 =

-24Note 3.3 If we define 0 t = tc - = C for all partial tapes t then
the cover operation becomes commutative and associative, i.e.,
t1( t2 = t2 tl and t1Q (t20 t3) = (tlC t2)C t3o
Def. 3.9 If t1 and t2 are initial connected tapes (therefore 1-dim)
then t1 concatenated by t2, denoted by t1 t2 or just t1 t2, is defined
as the tape obtained by copying into the empty tail of tl (the empty
cells of t1 that most immediately follow, and perhaps include, the
initial cell of tl) the contents of t2 beginning with the initial
cell of t2. The initial cell of t1 t2 corresponds to the initial
cell of tlo
For example, if t1= = 1 I I and t2 = 1 1 I then
tl t2 = 1j 1 111.
Note 3.4 The "null partial tape" (not to be confused with the null
set) is that partial tape in which every cell is empty. The 1-dim
null partial tape is denoted by Ao. Observe that A is an initial
connected partial tape and that for any initial connected partial
tape t, tA = At = t.
Note 3.5 Observe that the concatenation operation is not commutative
but is associative.
Operations on m-Tuples of Partial Tapes
Defo 3.10 If t = (tl t2, ooo tm) is an m-tauple of partial tapes
f
such that ti is defined for i = 1,2, o.., m then the fold of t (or
t fold), denoted by tf, is defined as the m-tuple (tf, tf,, t
if for some i = l, 2,...m t= thent = ~o
i

-25For example,
f,.~1'u b-
( 11 1 j1/1 2 | b b
and
Defo 311 If t = (tl, t2, ooa, tm) is an m-tuple of tapes and r2
an 2-tuple of non-zero positive integers whose sum equals LrJ
m(( TZ r. = m),then the cover of t with respect to rl,r2,. rQ,
denoted by tC, r2I is defined as the i-tuple
r I
(tl d t2ooo C tr trl+l trl+2G o C trl+2~' tm-r +l( tm-r +2(E
OoCtm);
if any element of t rC 7 is then tQ
For example, if
t = (I IaEI[_L, |.iiF1a'b a I)
then tC a[ ( b'b b7,J )
and t =
2
Operations on Sets of m-Tuples of Partial Tapes
Defo 3o12 If T is a set of partial tapes (ioeo, a set of 1-tuples of
tapes) then the separation of T, denoted by Tr, is defined as the set
of all m-tuples obtained by taking the separation of each element of T

-26(ieo,, T = {tYltcT})o
Defo 3o13 If T is a set of m-tuples of partial tapes such that tf is
defined for all tcT then the fold of T (or T fold), denoted by Tf, is
defined as the set'of all m-tuples obtained by taking the fold of each
element of T (ioeo, Tf = {tflteT}) rl I
Defo 3.14 If T is a set of m-tuples of partial tapes and 2 l
an ~-tuple of non-zero positive integers such that rri
t
is defined for all tcT then the cover of T with r
respect to rlr2, 0 o, ro denoted by r1
T C e!j
is defined as the set of all i-tuples 2
obtained by taking the cover with respect to rl, r2,,r
of each element of T
(ieao, T Cr2 t C ri tcT 1
Defo 3o15 If T1 and T2 are sets of initial connected partial tapes then
T1 concatenated by T2, denoted by T1 T2 (or just T1 T2), is defined as
the set of initial connected tapes obtained by concatenating all elements
of T1 with all elements of T2; (ioeo, T1T2 = {tlt2jtlc T1, t2e T2})o
Defo 3o16 If T is a set of initial connected partial tapes then T star,
denoted by T*, is defined as the set A U T U T2 U T3U
where Ti = T T oooo T
concatenated i times
and U denotes the conventional union of sets~

-27Note 3.6 T* is the smallest set that contains T and is closed under
concatenation.
Regular Expressions
A regular expression (RE) is a symbolic means of representing
certain sets of initial connected 1-dim partial tapes. The union and
intersection of sets of 1-dim partial tapes will be indicated by U and
respectively. If T is a set of 1-dim partial tapes written over Z
then the complement of T, denoted byrj T. will consist of all 1-dim
partial tapes written over Z and not in T.
Defo 3.17 If Z is an alphabet then
1) all elements of Z are simple terms and all simples
terms are RE's over Z; if acC then a denotes the
partial tape I IL~J I
2) A and 0 are RE's over ~,
3) if a is an RE over Z thenru a and at are RE's over A}
4) if a and 5 are RE's over Z then acU 5, a n0 and ac are
RE's over A,
5) no expression is a RE over L unless it is obtainable
by 1) to 4) above.
For example,
o =.. I 1 )I1 I o }}

-28Note 3~7 In any partial tape represented by a regular expression the
leftmost symbol of the partial tape is in the initial cell of the tape
and all filled cells are connected.
Note 3~8 Any finite set of 1-dim initial connected partial tapes can
be represented by a regular expression simply by taking the finite
union of the enumerated tapes. Not all infinite sets of partial tapes
n n
can be represented by RE's; for example the sets 0 1 0 (or Onln) cannot be represented by a RE (6)

CHAPTER IV
EQUIVALENCE THEOREMS
1-Way 1-Dim 1-Head Machines
Theorem 41 If Otis a 1-way 1-dim 1-head machine working on tapes
written over Z then G(OC) = D where P is an RE over o
Proof: An effective procedure exists to determine if any Ot
is 1-way (see Chapter V). Without any loss of generality we can assume
(X to be 1-way in the +1 direction in which event all the accessible
transitions of A will carry labels of the form a/l where aC.o Since
one can remove all inaccessible transitions from the state graph of Ct
without alterning G(Ot) one finds that the state graph of Otis precisely
the state graph of a "one-input, one-output automaton" as described by
McNaughton and Yamada, (3) Ot having a single output state, namely the
ACCEPT state. Therefore, using the procedure given in Part II of the
McNaughton-Yamada paper one can construct B the RE over Z that represents all 1-dim partial tapes taking Ot from si to A; ioeo = G(Ot)o
QED
Note 4o1 If a is a 1-way D-dim 1-head machine then G(Ot) consists of
a set of partial tapes, each consisting of a D-space empty except for
a finite line of symbols along one of the D-coordinates. This line of
symbols can be represented as a RE over Z, the alphabet of Oto
Example 4,ol Figure 4.1 gives 014o1 a 1-way 1-dim 1-head machine working
on tapes over Z = {a,b,B}; find G(Ot4l)~
-29

I/
\ lB.b/l
Machine Ct
4.1
Figure 4.1

-31Using the technique of McNaughton and Yamada one finds that
G(Ot) = BU (aUb)aU (aU b)(BUb)[a(aU b)(BU b)]*[bU aBU a(aU b)a].
Theorem 4.2 If P is a RE over Z then there exists a 1-way 1-dim 1-head
machine Ot working over Z such that G(Ot) = I.
Proof: Construct, via Part III of the McNaughton and Yamada
paper, the state graph of Ot' the "one-input, one-output automaton"
that represents 3 MO will in general have more than one terminal
state (output = one); merge all terminal states of Ct' into one state
labelled ACCEPT and delete all transitions from this state; call the
new machine thus obtained O. If t is a tape accepted by QL then
t must have a subtape that takes Ot' from sI to a terminal state, i.e.,
t has a subtape in P; conversely if t has a subtape in D then t will be
accepted by 0, o Thus G(0t) = 3.
QED
Example 4.2 Let 5 = (aUb)*bBUabBB be a RE over E = {B,a,b}. Find
a 1-way 1-dim 1-head machine 04.2 such that G(0t4.2) =.
Using the McNaughton and Yamada technique one first constructs
AOt (Figure 4.2) the one-input one-output machine that represents 5
[terminal states of a4o 2 are represented by double circles].
By merging the terminal states of A 4I2 into a single ACCEPT
state and by deleting all transitions from ACCEPT one obtains the desired
machine Ot 42, (Figure 4.3). The head movements for all transitions in
a1 4~2 are understood to be +1o

,ro
a I ru
Machine.
Machine 4.2
Figure 4.2

b~~~
a a b~~~~
a~~~
a~~~
B
Machine Ot42
Figure 4.3

1-Way 1-Dim n-Head n-Tape Machines
Theorem 4.3 If Ot is a 1-way 1-dim n-head machine operating such that
each head hi works on a distinct tape written over Zi (i = 1,2,..., n)
then G(Ot) = where f is a RE over -E
Proof: An effective procedure exists to determine if any QL
is 1-way (see Chapter V). Without any loss of generality we can assume
A to be 1-way in the +1 direction for all heads.,in which event all
the accessible transitions of A will carry labels of the form
V2 n/1,1, ooo 1 where ici. One can remove all inaccessible
transitions from (O without alterning G(OQ). Since the heads of tL move
in synchronism, one can imagine the input to Ot to be either a set of n
single channel tapes or a single n-channel tape (or more precisely the
separation of a single n-channel tape). If one adopts the latter point
of view then the n reading heads h1,h2, o.. h reading over,y2, o noo
respectively can be considered as one reading head reading over the
alphabet
oJ o
Therefore, via Theorem 4.1, B, the set of single n-channel
generators accepted by the 1-head machine reading over []
would be expressible as a RE over 1
Taking the separation of B one
gets G(O)o ioeo, G(OL) = Bo.
QED

-35Example 4.3 Let OL be the 1-way 1-dim 2-head machine given in
4~3
Figure 4~4. Head hi works on tapes written over f = {B,O,1} and
h2 works on tapes written over = {B,a, 1} Find G(Ot4o3 )
a)A
B,Ba)}/B (a
Machine O4o 3
Figure 4,4
Considering 04.o3 to be 1-head reading over I2j one finds
via theorem 4,1 that
[luI L i a L aJ Ul,a
and that
4 B B B' 1 B aB?
- = Ldzi, _ L)i * 11 B
Theorem 4[4 If P is a BE over ZJ then there exists a 1-way 1-dim
Li
T-FR iq qPP.nan-r n

n-head machine (- in which each head h. reads over Zi and for which
G(O., )=B~~ _
Proof: Via the method of Theorem 4.2 construct CL" a 1-way
1-dim 1-head machine reading over which has G(Ot") = Each
transition of OC" will be
labelled 0
"L C
0 2 Convert OU' to a 1-way 1-dim n-head machine by changing
_ c/ each transition label of QO' as follows:
Ldni
7 2
L nl
The resulting machine A has as generators precisely the separation
of G(O-'); ioe, G(Ot) = G(Ot")Q1 = 1
QED
Example 4o4 Given
a eC * * J LjL
construct machine such that G(t44) = Using the method
presented in Theorem 494 one first derives the machine aCO 4 (Figure 4o5)
Applying the mapping 1
to the transition labels of t4o4 one gets the desired machine ~ 43
(Figure 4o6)o

B. iB 0
7 01\B'! 0o LB'
a'B i,,
Machine (0
4o4
Figure 4. 5
A
/(,Bo), (o,o,1)
Machine O 4
Figure 4,6

-38Note 4.2 If Otis a 1-way 1-dim n-head machine working on m tapes
(m < n) then some tapes can have more than one head per tape. If any
two heads hi and hj are on the same tape and move in the same direction
then their positions will always coincide and they can be replaced by a
single head; if such is the case for all heads on each tape then GO
can be replaced by a 1-way 1-dim m-head machine (Q1' that is equivalent
to 1L (ioe. G(0t) = G(Ot"') = P where: is a RE with m channels)>
2-Way 1-Dim 1-Head Machines
Defo 4.1 Let 5 be a RE over F /D1; will be said to be realizable
if and only if 5 or any of! 2 2
Ln/Dn
its equivalent RE's has no well-formed part of the form
a~ /d2~~-/dY
Cn /dAn J,/ Y2 -
where for some i = 1,2, 0.0, n d i d (A1 and A2 are sets of partial
tapes over
o2o2
0 o
_Zn/D n_

-39Theorem 4.5 If Ot is a 2-way 1-dim 1-head machine working on tapes
written over Z then G(Ot) = f where: is a realizable RE over ~/l.
Proof: Let (r' be derived from O, by considering O! to be
a 1-way 1-dim 1-head machine reading over L/l with the head movement
of +1 for all transitions of ot' understood. 5 is the RE over Z/1
representing G(0vs)o From the fact that for a given state in At
and for each CEZ there is only one transition in OI' one deduces that
5 is realizable; the assumption that P is not realizable would imply
that COt has a state with two transitions for the same input -- this is
not allowed.
Let tcT(Ot)o The behavior of Ct on go(t) can be described
by the sequence
p sIT, Co/do; Sl,c l/dl;......; Sp-l p-/dp1; s
where Ot starts in state sI, reads a (in cell o) moves its head d and
o 0
goes to state sl..... Ot in state si during the i-th cycle reads ai
(not necessarily in cell i) moves its head d. and goes to state Si+l;.... (
in state sp during the p-th cycle reads ap and goes to A (Ot accepts g (t))o
Consider the partial tape
t = m.o /do1 cye/d1 J I _
extracted from pc Since t' derived from the functioning of A on t it
follows that ao/do is an initial symbol of 5,.pa final symbol of 5 and
(ai/di, 1i+l/di+l)a transition of P for i = 1,2,.oo, p-lo Thus t'E5o
The definition of the fold operator exactly parallels the head movement
of Ot so that t'f = g(t). But t'e - t'fef so that go (t) = tlf5f~
~ one has the partial proof ge G(Ot) - gefo

To complete the proof one must show that gef - gEG(Ot)o
Take any g in 5fo Therefore there is some t' in P such that t'f = g.
t' is in 5 therefore t'cG(Ot' )o Write the sequence
p = I ao/do; Slal/dl; ~.... Spg "p
that describes the behavior of ~ on t' = Io1 al/dl Z i' I
Qt' starts in sI, reads oo/d of t', goes to state sl, reads al/dl,
goes to s2, goes to sp. reads ap, goes to Ao But if tI' accepts
t' then t accepts t' = g since the fold operation parallels the head
movement of t0 Thus gef, which completes the proof.
QE D
Example 4o5 Let Ot4o5, the 2-way 1-dim 1-head machine working on tapes
written over Z = {B,O,1}, be shown in Figure 4o7. Find G(Ot)o
0/-1
(/ 0 sI
1/1 /
Machine 4 5
Figure 4~ 7

From' one gets a = (0/-l)(o/-l)*B U (1/l)(l/l)*B or that
G(Ot4.5) = [(O/-1)(O/-l)*B U (1/1)(1/1)*B] Observe that P
is realizable.
Theorem 4.6 If 5 is a realizable RE over V/1 then there exists a 2-way
1-dim 1-head machine Ot such that G(Ot) = 5f
Proof: An effective method exists to determine if P is
realizable (see Chapter V). Construct via Theorem 4~2 the machine Cl'
that reads over Z/1 and has G(OUM) = o Since 5 is realizable we are
assured that for each EcZ and each state of COL, Ot! will have just
one transition. Thus if we convert Ot' to a 2-way 1-dim 1-head
machine Ot reading over Z by applying to the transition labels of OU'
the mapping (a/d)/1-> /d we are assured that 0% is in legitimate
form (ioeo only one transition leaving each state for each input).
The proof follows by reversing the arguments of the proof of Theorem 4.K5
QED
Example 4.6 Let P equal the realizable RE (b/l)*B U (c/-l)*Bo Find
a 2-way 1-dim 1-head machine A 4 c6 such that G(Ot%4 6) = Kf'
At', the 1-way 1-dim 1-head machine reading over
{B,b,c}/l that satisfies G(Ot 6) = 5 is computed via Theorem 4.2
and is given in Figure 4.8.
The machine Oa 46 which satisfies G( OL4 6) = Kf is
obtained from A 4o6 by applying the mapping (a/d)/l_ a/d to all
transition labels int6 0. O t46 is given in Figure 4.9.

42-.b/1)/i
Machine 0M4.6
Figure 4.8
( b
c/-c
Figure 4. 9

-432-Way D-Dim 1-Head Machines
Theorems 4~5 and 4.6 can be immediately extended to l-head
machines working over D-dim tapes; the proofs are essentially the
same as in Theorems 4o5 and 4o6, differing only in those places where
the head movement goes to D-dimensions. The D-dim theorems are given
below without proofs but with examples.
Theorem 4,7 If Otis a 2-way D-dim 1-head machine working on tapes
written over Z then G(OL) = if where P is a realizable RE over Z/Do
Example 4_7 (Ot47 shown in Figure 4o10 is a 2-way 3-dim 1-head machine
working on tapes written over Z = {BO, 1 } o G(Ot47) is derived to be
1(B/-3)*[(0/1)(l/2)(1/-1)U (1/1)](l/-)l}fo
B/-3
s4
1/-1
55 A
Machine a 4,7
Figure 4o10

Theorem 4~8 If: is a realizable RE over Z/D then there exists a
2-way D-dim 1-head machine Ct such that G(0 ) = fo
Example 4~8 Construct a 2-way 2-dim 1-head machine 48 such that
G(Ot 4 ~8) = f when P = (a/O)(a/l)*(b/2)(a/2)*bo
0aOt8, the 1-way 1-dim 1-head machine that reads over
{a,b} /2 and for which G( O o8) = Uis computed via Theorem 4~2 and
is given in Figure 4o11o
(a/l)/l (a/ 1
Machine Ot8
Figure 4,11
The machine CL4o8 which satisfies G( t48) = f is obtained
from0a 48 by applying the mapping (a/d)/l->oa/d to all transition
labels in a,4~8 ~ 0 4 8 is given in Figure 4.12,
Machine b48
Figure 4 12

-452-Way D-dim n-Head n-Tape Machines
Theorem 4.9 If O( is a 2-way n-head machine with each head hi(i = 1,2,...,n)
working on a distinct tape of dimension Di and written over 7i then
G(C) = - f where: is a realizable RE over FL/D2
-2D2
Proof: The RE P is obtained by applying the mapping (r9l'2' o o an)/
(dld2,on,, dn) —> (al/d1y C2/d2) ooo, an/dn)/'l,l..., 1 to each
transition label of L01 thereby obtaining a 1-way n-head machine Ot' whose
heads read respectively over El/D1, 2/D2, o, Zo /Dn; let it = G(OLl )o
Arguing as in the proof of Theorem 4.5 if t' is an n-tuple in 5t then OL'
accepts t'and if t' f I then Ot when working on t'f will go through
the same sequence of states as OtI and therefore tzf is accepted by
CL (or t'f eG(Ot)). Thus PfC~ G(Ot). Conversely if t is some input
in G(OL) then by examining the behavior of 01 in accepting t we can
deduce the sequence tY' such that t'f = t. Thus P3f, G(Ot). The
conclusion then is that G(Ot) = -fo
That P is realizable follows from the observation that if B
were not then one could show a. must have a state with two transitions
leaving it for the same input n-tuple; this is not allowed. Therefore
5 must be realizable.
QED
Example 4.9 Let C41 9 be the 2-way 3-head machine shown in Figure 4.13
Each head of Oog9works on a distinct tape with D1 = 1, D2 = 2, D3 = 3
and ~1= - = 3 = {BOl}o Find G(O!t4o9)

/._ Q< O(, B/1/i' IB32BB,B, B
ooo0/0,oi s1 A
Machine OCl4 9
Figure 4013
Applying the mapping of Theorem 4~9 one obtains the 1-way
n-head machine OlA shown in Figure 4o14o
4~9, 1 ( 1/-1, 0/0, B/3 ) /1,
Machine 4
Figure 4o14
Theorem 403 applied to 019 yields G(OCt9)
where
lB/13 i i o/ 0/1io Bj

-47Thus'0011 o/o 1 u o/o! o/i B
G(Ct 4 ) = t = &. 0/1, 0/0 U. i/0 0/1 B
aio~ ~9 )'~!B/3j
- B3 B/3 o/i B/3 B
Theorem 4,10 If 3 is a realizable RE over
2 /D2
i
then there exists a 2-way n-head machine
Ct such that G(L) = /Dn
Proof: Construct via Theorem 4.2 the machine O1 that reads
over jL/D9i and has G((O' ) = Obtain OL from C'=. by applying the' /D
/D
mapping (1/i, c12/d2,..o, ~ n/dn)/ll ooo, 1 —-? (a 1, 2~ ooo on)/d l.d2 od
to all transition labels of Q', Since 5 is realizable we are assured that
will have only one transition leaving each state for each input n-tuple,
The proof follows by reversing the arguments of the proof of Theorem l4c
Q;ED
Example 4,10 Construct a 2-way 2-head machine t4o10 such that') = 0 where f - L0/1, 0t/1O * 102 0
QI, themachinewith * G/1o 1/-2- ),4, 10the machine with G(cq 10) = is shown in Figure 415.
(0/1,0/1)/1 l1 (1/2,1>2)1,1 0 0
/-,- A
Machine th 4 10
Figure 4 15

Applying the mapping of Theorem 4.10 to one obtains
4 10 shown in Figure 416,
1t 10( ~)/1, 1
Machine 4
Figure 4 16
2-Way D-dim n-Head m-Tape Machines
Theorem 4.11 If Otis a n-head machine operating on m tapes (m < n)
such that the first n1 heads work on tape t1 written over L1
in D1 dimensions, the next n2 heads work on tape t2 written over Z2
in D2 dimensions,...., -the last nm heads work on tape tm written over Zm in Dm
dimensions (n > li=1,2, 0,~ m) then
)= f Kln2
G(K2 )where P is a realizable
nm

-49RE over F/D1
1
/D1,
2
Zrn/Di
Zm-/DmZm/D m
Proof: Let Q_' be the same machine as Otbut with each head
on a distinct tape;then via Theorem 4.9 let P be the realizable RE over
/Dl n
K/D m
m
m m
such that G(Ot') = f If t' = (t t' O, t e: of and if
Vf t=(1 2' n
t=-t~ nn ~= t then OCwhen working on t will go through the same
state sequence of states as (CL working on t' Since every filled
cell of t is scanned by Ot (since every filled cell of t' is scanned by QI')
and t is accepted by 1, teG(CO) or in other words d~f nlcG(Ot)
Conversely if t = (tl, t2,,os, tm) E G(OtL) then there is
an n-tuple t' = (t{, t9 0O, tA) where t! is the generator scanned by
an n-tuple t' (ti t~ ooo~ tn) where ti~~~~~~~~~~~n,,

-50by the i-th head of t' must exist in q and tC ual
t. Thus CL nl G(Ot
_nm_ - o Io
f n1
Concluding then, Q n2 G(Ot)
QED
Example 4111 Let O 4,11 be the 3-head machine shown in Figure 4L17o
Heads h1 and h2 work on the same tape of dimension 2 written over
E1 ={Ba,c}; head h3 works on a tape of dimension 1 written over Z2 = {B,0}
Find G(Ot 4 11)~
4 11,c,B/2 1,-1 c~cB
cc,0/12,12/ aa0/2,1,.
Machine 04V1l
Figure 4017
Applying Theorem 4~9 one obtains 5 = c/2 U [a/li } c/l a/1 ic
and thus G(O'.4 11) = ~ c= / a/(l K ci a 1 nd I! o/_1 0.B/- I
0/i 0/1~ L

-51Theorem 4.12 If P is a realizable RE over |\ /
I JD1
m
Then there exists a 2-way n-head machine Q, (n = L n.), such that
Proof: Let Q be the machine obtained by applying Theorem 4o10
to 5 (ioeo G(Ot) = ~f ), Instead of letting OL operate with one head per
tape alter O1 such that the first nl heads of OC operate on a single
tape tl, the next n2 heads operate on a single tape t2, ooo, the last
nm heads operate on a single tape tmo The proof is completed by
reversing the arguments of Theorem 4ollo
QED
Example 4o12 Construct a machine Ol12 that works on 1-dim tapes
over Z = {B,O,1} and such that
CG(Ot) = {t( t = (1'~ O _ 1', ~ O |B| k = 102,1o}
One can show that G(C=) -1 F/l O Fo/li Fl/li * FBI]
0/j 0Loj Lo/o L0/l |Thus CL 4 is the 2-head machine shown in Figure 18 with both heads
working on th e same tape~

(0,90)/1,o 0 (oo)/1,1
1O.(~9)/1,0 (1,0)1,0. A
Machine 0t4 12
Figure 418

CHAPTER V
ASSORTED ALGORITHMS AND THEOREMS DEALING WITH THE
DECISION PROBLEMS AND SPEED OF OPERATION OF n-HEAD MACHINES
Algorithm for Deciding 1-Wayness of Machines
The algorithm will be given below assuming that the machine
OL under consideration is n-head working on n-tapes (ioeo, one head
per tape); the remarks following the presentation of the algorithm
indicate how the method may be extended to include machines with more
than one head per tape.
Algorithm 5o1 Let Ot be an n-head machine working on n-tapes (one-head
per tape) and let the state set of Ot be SU {A,R} with sI cSo The
transitions of aL going to A or R will be assumed to cause no head
motion of OL
1) Let i = 0 and &(0)= {sI}o
2) Pick any transition leaving si and not going to A or R;
let the head motion associated with this transition be
the n-tuple d = (dld2, ooo, dn)o If no such transition
exists 01 is trivially 1-way (ioeo ON2 never moves since
all transitions from si go to A or R)o
3) Consider all transitions leaving states in (i), all
these transitions must either go to A or R or must have
head movement n-tuples equal to do If this criterion
is not met Ot is not 1-wayo If it is met let
5 (i+l) =g(i)u {all destination states of transitions leaving states in f (i)}o
-53

4) If g (i+l) = (i) halt; Ot is 1-way; if g (i+l):D&(i)
augment i by 1 and go to step 3),
Proof: First of all, transitions leaving si are accessible
since any symbol can be put in the initial cell of each tape. If Ot
is to be 1-way all transitions leaving sI therefore must go either
to A or R or else have the same movement n-tuple do If in the
application of the algorithm O has not been disqualified as a
1-way machine after i repetitions of step 3) then we know for all
inputs to O1, QL either accepts or rejects the input or else
has moved to some state sj(# A,R) the heads of OX always moving
d each machine cycle and thus after i cycles each head of aO is
scanning a previously unscanned cell and so all transitions leaving
O (i) are accessable and therefore must go to A or R or also have
head movement d. If a transition from' (i) has a head movement
not equal to d there is an input to Ow for which Ot is not 1-way.
The algorithm halts in at most S + 2 repetitions of step 3) since
S U {A,R} g(i+l)) g (i).
QED
Note 5.1 Lets = D(i) where J (i) = (i+l) in algorithm 5,1;
is then the set of accessible states of CO o T(Ot) = 0 if and
only if A 0o
Note 5~2 One can extend the algorithm to the case of many heads per
tape by implementing the following step:

If two (or more heads), h1 and h2, of 01 work on the same
tape then during the first machine cycle of Ct we only need to conI
sider those transitions from s in which hi and h2 read the same
symbols; if the d associated with any one of these transitions indicates that hi and h2 move in the same direction then in applying the
algorithm one observes that transitions leaving g (i) are accessible
if and only if hi and h2 read the same symbols (assuming Ot is 1-way)
therefore transitions leaving g (i) and in which hi and h2 read
different symbols can be considered inaccessible and can be ignored
in applying the algorithm. If the d associated with the transitions
leaving sI indicate that hi and h2 move in different directions then
for all states in d (i) - {sI} transitions for which h1 and h2 read
different symbols must be considered accessible -- furthermore if for
some C (i) there is a transition leaving a state in (i) and
returning to sI then all transitions leaving sI and for which hi and h2
read different symbols must be considered as now being accessible.
Algorithm for Deciding the Realizability of Regular Expressions
Algorithm 5o2 Let B be a RE over E /D
/D2
h n/

To check if 5 is realizable, attempt to construct via Theorem 4o10 an
n-head machine CO such that G(OL) = -0f. When the proposed Oa is obtained
check each state of AOL to see that only one transition per state is
labelled with a given input~ If the check is unsatisfactory then it
follows that P is not realizable. Further, if 5 was not realizable O(\
would not pass the check, Therefore P is realizable if and only if aC
has one transition per state for each input.
1-Way 2-Head Equivalents of 2-Way 1-Dim 1-Head Machines
Shepherdson(7) has shown that for any 2-way 1-dim 1-head
machine Ct if one restricts the inputs of Ot to those 1-dim tapes for
which (t never scans cells to the left of cell 0 then there is a 1-way
1-dim 1-head machine which is equivalent to CL. It is impossible in
general to construct a 1-way 1-dim 1-head machine equivalent to (At for
all inputs. One can construct, however, a 2-head machine that is 1-way
and equivalent to C o
Theorem 5.1 If Ot is any 2-way 1-dim 1-head machine then there exists
a 1-way 1-dim 2-head machine, constructable from Ct and denoted by
J (ot), such that G(OL) = G(3 (Ct))o
Proof~ 5 (O w) will have two heads hi and h2. Initially
hi and h2 will both be placed on the initial cell of the tape to be
examined, Once d (OL) is operating h1 will move one cell per machine
cycle in the -1 direction and h2 will move one cell per machine cycle
in the +1 direction; therefore ~ (Ot) will be a 1-way 1-dim 2-head
machine~

For all 1-dim tapes the head positions of 5 (0t) after k
machine cycles will be
C k- k k+1 C k-l ak J ak+l
h1 h2
and the input to ~ (0t) will be (a_k, ak),
For any tape t let tk be the subtape of t consisting of the
cells -k, -k+l, o o, 0, oo k-l, k. The crux of the construction of
X (01) depends on the observation that given 01= < C,SsIM
working on tapes over Z then for any 1-dim tape t and any integer k,
2S
tk can be put into one of 2 + 2S (2Sot + 2) OL equivalence classes
depending on the behavior of Ct on tk. Furthermore, if [tk] is the
equivalence class of tk and a k-l and ak+l the contents of cells
(-k-l) and (k+l) of t then [tk+l] is uniquely determined by [tk] and
(C-k-l' k+l)~
The state set of ( (0t) is made up precisely of these
equivalence classes [tk],and the transitions of d (Ot) on inputs
(a k-l' ak+l) c: Z x Z are determined as follows:
1) If on reading tk, Ot. goes to A(R) then [tk] = A(R);
in the event Ot weakly rejects tk without ever leaving
tk then [tk] = R; thus we have identified two of the
equivalence classes, A and Ro
2) If on reading tk, 01. does not accept or reject tk
then OL must step off tk at either the left (-1) or
right (+1) end in some state sicSct o If one knew
the behavior of OL on tk if 0\ started on cell -k and

again on cell k beginning in each state of 1e then
one could find [tk+i] for all ~ > 0 without knowing
precisely what tk was, ioe., one only need know [tk]o
Thus for any tk, Ltk] can be A, R or a behavior label
of the form
si5 P
-l +1
S1 C 91
2o 1211,2
v = =Ce
where p = + 1 and si,P denotes that when working on tk
L steps of the p-th end of tk in state si and where
ax y denotes the behavior of OL on tk if started on
the x-th end of tk in state syo Caxy = A(R) if Ct
moves to A(R) without leaving tk, A = R if OL
x, y
weakly rejects tk without leaving tk axy sjpv
if Ot leaves tk on the Q-end of tk in state s
Since for every tk and a given Ot one can put tk in precisely one of the above mentioned equivalence classes one gets that
the number of equivalence classes is
2S,
2 + 2S3 (2 + 2 )2S
A,R number of behavior labels
Given [tk] ad (a-k-l' ak+l) one can determine [tk+1] as
follows

1) If [tk] = A(R) then for all i > 0, [t k+] = A(R)o This means
that if 01, accepts (rejects) tk without reading a -k-1 or ak+l then
a -k-l- and &k+l+i can be anything without affecting the behavior
of M01 or J (CL) on to
2) If [tk] = si, P
k i
SOthen one determines [t ki in the following manner: (assume p -1,
if p +1 just alter the following presentation accordingly).
a) if t: moves to A(R) on reading ak-l in state si
then [tx] I (ack-1p')_ A(R); n indicates that ak+l
can be anything, even a symbol not in Z, since
would never read ak+l; (ioe. cell k+l is not a
filled cell in this particular generator of 01- with
respect to t)>
b) if 01 on reading ak-l moves back onto tk in state
sx then consult a-l,x of [tk] to see what 01 would
do on tko
if a = A(R) then [tk] i (askulm )A(R),
if 1 x= Sw -l then one knows Ot will return
to read ak1 in Sw without scanning ak+l; so
examine what I, would do in Sw reading ak1
and re-apply b).

-60if -1J X = SW +1 then one knows Gb will step off
tk on the right to read ak+l in state sw, examine
what L would do and re-apply b) or apply c) getting
[tx] (a-k-l'ak+l) [tk+l] (ak+l is used in place of
o since if ak+l is scanned by Ot then [tk+l] is not
independent of Ok+al)
c) if in applying b) one discovers OT would move -1 to
scan a k-2 or move +1 to scan ak+2 then
[tk]
S2 51-,2 21,2
C.v _[t 1
o k+
where p = -1 if O scans a k-2 or +1 if Ot scans
ak+2, Sj being the state CO is in when moving to scan
-k- k2 or k+2; is also determined from QOL and [tk]
by using a) b) c) but by starting OL in state sy on
a k-1 if x = -1 and on ak+l if x = +1
An efficient way of constructing X (0y) is to begin with
an initial state, I, and let ~ (CO) start with both heads on the
initial cell of to Thus the only transitions from I that can occur
are transitions on inputs of the form (a,a) since h1 and h2 read the
same symbol when in I. By applying a) b) c) to I of a (OL) one finds
all the states of 7 (Q0) immediately accessible from Io To these
states one applies all inputs from Z x Z (all inputs are possible since
~ (01) is l-way) and finds the second rank of accessible states of

-6L -
0 (OL); one continues in this manner until a closed machine a (OL)
is formed.
The manner of constructing ~ (CX) assures one that
G(OL) = G( (0t))o Furthermore, (Gt) may strongly reject some
tapes only weakly rejected by OL; if one desires (Oa) to also reject
(weakly reject) a tape if and only if Qtdoes it then this can be
accomplished by adding a weak reject state, WR to 0 (OL) (WR=a state
that loops on itself for all inputs) and when in constructing (COL)
a weak reject by Otis uncovered do not send 8 (0L) to R but rather
to WR,
QED
Example 5o1 Let Ot be the 2-way 1-dim 1-head machine shown in
Figure 5.1 that reads tapes written over Z = {B,1} and accepts input
tape t if and only if t has a blank initial cell and a 1 to the right
and left of the initial cello Find (OU5ol)
B/1 B/-l
Machine {t
5ol
Figure 5ol

-62Let I be the initial state of $ (OQ5. 1)~ When5 ((t51)
is in I the only possible inputs to. ( 051) are (BB) and (1,1).
So considering tk I[ and tk- II- one finds that
~I X (B,B) (1,1) [to be read as:"state I on
input (B,B) goes to state
s2, 1 R s2, 1
s2,1 s s2,91 2- s2,1
s2 1 s21 2, etc.oo" ]
s3,-1 Is3-1 (S3)-1 s3,-1
Continuing one gets
s2, 1 s311l s21 s1 A
s21 s,1 s2,1 s1 s3,-1 R R s2,
s2,l 21,1 21 s21 s3,-1's3,-1 s3,-1 s2,1
s3 -1 | -1s3 —1 is3 -1 s3,- A A A
s,-l s -l A
_s 1R S31 3|
s,-1 s 3-1
3 3
s3,-1 A s 3-1
3 3
R Y s,1 A
R s-2.1 s2,1
s3 - 2,1 s2,1
A A A
Thus a suitable state graph for 5 (015o1) is given in Figure 5o2o

-63(BB)/-1,1 s2,1
s2,1 s2,1
s2'1 s2"1
\s3,_ -! S3,-'
(B,B)/\-1,1 ")"
(1,1 / \ V (]
(,,,,, 1,B)/-1,R s2,1, (~o,1) \ s2- s,1
A A
Machine (oX, )
Figure 5 2

The "Particular Input" Decision Problem
Def. 5.1 Let Ct be any n-head machine and t any input to O (t is in
general an m-tuple of tapes) then T (t) is defined if and only if CO1
accepts or strongly rejects t and in that event T (t) equals the number
of machine cycles it takes for Qt to accept or reject to
Theorem 5o2 If OL = < C,S,sI,M> is any 1-head machine working on D-dim
tapes and if t is a D-dim tape for which the initial cell and all nonblank cells can be enclosed in a D-dim rectangular parallelepiped of dimensions ~1 x 2 x.... x iD and if To(t) is defined (if CrIaccepts or strongly rejects t) then
(t) < S Hn (i. + 2S)
OL i=l 1
Proof: Let P1 be the rectangular parallelepiped of dimensions
x1 x.... x D that encloses the initial cell and the non-blank cells
of t. Enclose P1 with a larger rectangular parallelepiped P2 such that the
corresponding sides of P1 and P2 are S cells apart. P2 therefore has dimensions (l1 + 2S) x (t2 + 2S) x....x (eD + 2). Let it work on t, its head
starting on the initial cell inside Pio After S i (Q + 2S) = T machine
i=l
cycles one of three possibilities must have occurred:
Possibility 1) a accepts or strongly rejects t; in which
event the theorem holds~
Possibility 2) O neither accepts or strongly rejects t and the head
of aC never left P20 But T equals the total possible
combinations of head position in P2 and state of Oa;
if after T machine cycles O2 never left P2 nor accepted
or rejected t than 01 must be in a loop and therefore
never will accept or reject to Thus the theorem holds,

Possibility 3) Qlneither acceptednorrejected t and the head of Otleft
P2. Let h (the head of CO) have left P2 for the first
time during the i-th machine cycleo By the construction
of P2 and P1 one knows that h has read B for the last S
machine cycles preceeding the i-th. Since in reading
these S B's aCneither accepted nor strongly rejected t
but instead moved away from P1 we are assured that Ot
will continue to read blanks and move further away from
Pl, never accepting or strongly rejecting to Thus the
theorem holds.
QED
Note 5.3 In the trivial case of Otbeing a 0-head machine the acceptance
or rejectance of all tapes is a function only of S and M of 0 t If T_ (t)
is defined in this case then for all t, To!(t) < S
Note 5~4 Minsky(5) has shown no procedure exists for determining if a
general 2-head 2-tape machine accepts or strongly rejects a particular input
t. His results in no way require the heads of the machine to work on separate
tapes and so one can conclude that: if n > 2 no procedure exists to determine
if a general n-head machine accepts or strongly rejects a particular input t,
In contrast with theorem 502 it is a direct consequence of
Minsky's result that there is no function f(Ot,t) of Ctand t such that if
Ot is a general n-head machine and t an input T0o(t) < f(Gt) if To(t)
exists. If such a function existed then there would indeed be a procedure
to decide if any general n-head machine accepted a particular input to

-66The Emptiness Decision Problem
Of the several decision problems one can propose dealing with
n-head machines there are three which can be shown to be equivalento These
decision problems are:
1) The emptiness decision problem: given any n-head machine OXdoes Oa
accept any input whatsoever? (i.e, does T(ct) = 0)o
2) The state accessibility problem: given any n-head machine Ot and any
internal state s of Otis s accessible?
3) The transition accessibility problem: given any n-head machine Otand
any transition T of Ot is T accessible?
Theorem 503 The emptiness decision problem (1), the state accessibility
problem(2), and the transition accessibility problem (3) are equivalent in
the sense that one can devise a general procedure to answer one of the
problems for all n-head machines if and only if one can devise a general
procedure to answer all of the problems for all n-head machines,
Proof: One can present the proof by showing that a general procedure to solve (3) = a general procedure to solve (2) = a general
procedure to solve (1) a general procedure to solve (3) [ or in
short notation gp(3) ==- gp(2) gp(l)== gp(3)]o
a) gp(3) = gp(2): let Ot be any n-head machine and s any state
of a o gp(3) assures us we can determine if any transition
of OL is accessible. Consider each of the transitions entering s and determine if each is accessible. s is accessible
if and only if one or more of the transitions entering s is
accessible, Thus gp(3)-=-gp(2)o

b) gp(2)- gp(l) let CObe any n-head machine with ACCEPT
state A. T(Ot) ~ 0 if and only if A is an accessible state
of Ot. But gp(2) assures us we can determine if A is
accessible. Thus gp(2) =- gp(l).
c) gp(l) =zgp(3): let Ctbe any n-head machine and T any
transition of aO o Alter OC by letting all inputs to A
go to R and by changing the destination of T to A (if T
goes to A originally then leave it). Call this new machine
(7. T(y ) L 0 = T accessible in C0 and gp(1) assures
us we can determine if T(C ) = 00 Thus gp(1) 9gp(3).
QED
Theorem 5.4 Given any 1-dim 1-head machine 0i there is a general procedure
for determining if T(CO) = 0o
Proof: If Ot is 1-way then one can apply the result of Theorem 7
(6)
of Rabin and Scott to Ot and thereby decide if T(Ot) = 0. If 0t is 2-way
then. Theorem 7 of Rabin and Scott can be applied to 5 (CL), the 2-head 1-way
equivalent of Ct; T(OL) = ~ if and only if T(g (Ot)) = (o
QED
Note 5.5 If Ot is a 1-dim 1-way machine then Theorem 9 of Rabin and Scott
can be applied to Otto determine if G(Ot) is infinite. If Ot is 1-dim.
2-way then Theorem 9 of Rabin and Scott can be applied to (iot) to determine
if G(Ot) is infinite.
Note 5.6 Since every 1-way n-head machine reading over Z.Z2... nZ is
isomorphic to a 1-way 1-head machine reading over
Ln i it is evident via

-68Theorem 504 that a general procedure exists to determine if T(Ot) = Q if
iJs' is a 1-way n-head machine.
Theorem 5~ 5 There is no effective procedure for deciding if T(OL) =
for any general n-head machine Ot, if n > 2~
Proof: This result is proved by Rabin and Scott in their
Theorem 19o
QED
Theorem 5~6 There is no effective procedure for deciding if T(c,) =
for any general 1-head machine Ol if 0L works on tapes of dimension D > 2.
Proof: Consider the set'~ of all 2-way 1-dim 2-tape 2-head
machines such that the state set S of each machine in is partitioned
into two sub-sets S1 and S2 and such that on all transitions from states
in S1 only head h1 will move and on all transitions from states in S2 only
head h2 will move. The set' is precisely the set of "two-way two-tape
automata" described by Rabin and Scott.
The input to any machine ~ in will be restricted to pairs
of l-dim partial tapes of the form (htlh, ht2h) where the initial cell of
each tape corresponds to the first cell in t1 and t2 respectively and
where E, the alphabet of t1 and t2 does not contain ho h is an endmark
and in operation ~ confines its head movements strictly to the cells
filled by htlh and ht2ho
Rabin and Scott have shown in their Theorem 19 that in general
no effective procedure exists to determine if T( ) =
One can show that for any ~ in ~ there is a 1-head machine C(C
working on 2-dim tapes such that T(,i) =, if and only if T(OL) =

-69and therefore no effective method exists to determine if T(Ot) =- since
if a method did exist we could determine (contra Rabin and Scott) if
T( ) = i for all ~ in o
Let e ~ ~. Let t1 and t2 be any 1-dim partial tapes over
9 the alphabet of. One defines (htlh) x (ht2h) as follows:
(htlh) x (ht2h) will be a 2-dim partial tape written over
(Z U {h})2 such that cell (0,0) will be the initial cell
of (htlh) x (ht2h) and such that if Gi is in the i-th
cell of htlh and T. is in the j-th cell of ht2h then
cell (i,j) of (htlh) x (ht2h) will contain (oi,Tj). If
eg(tx) is the number of filled cells in tx then the
contents of cell (i,j) in (htlh) x (ht2h) is defined only
for
1 < i < eg(tl)
and
1 < j < jg(t) 0
From f one constructs 0t2 such that Oa2 has the same transition
structure as ~; however Ot2 is Alhead and reads over inputs in (I U {h})2
whereas ~ is 2-head and each head reads over ZUf{ho Thus the input labels
to transitions in O2 and f will identical. As for the head movements of
L 2' if a particular transition of ~ had head movement
a) (1,0) then Ct2 moves its head + 1,
b) (-1,0) then Dt2 moves its head - 1,
c) (0,1) then ([2 moves its head + 2,
d) (0,-1) then Ot2 moves its head - 2

-70By the construction of H all head movements of i must be one
of the four listed above; thus a2 is well defined for each f
It follows directly from the manner in which 012 was constructed
that
(ht h, ht2h) eT( ) - (htlh) x (ht2h) cT( t 2).
One can construct a 1-head machine O 1 that accepts any 2-dim
tape t if and only if t has a subtape of the form (htlh) x (ht2h)o Furthermore Ot1 can be built such that it will halt on the initial cell of t if
t is accepted.
If one merges and identifies the A state of Ot with the initial
state of CL2 one obtains a composite machine Ol such that
T(Ot)
~ — TT (O)L n T( z2) 0 X
~ —-~ does there exist a tl and t2 such that
(htlh) x (ht2h) E T (M2)
-c ~T(# ) 2
Since Tp) - is not effectively decidable one concludes that
T(Ot) - is not effectively decidable.
QED
Note 5.7 In a manner similar to the proof of Theorem 5.6 one can show
that no effective procedure exists to decide if any general 2-dim 1-head
machine strongly rejects any tape.
Boolean Properties of n-head Machines
Theorem 5.7 If 01- and O12 are nl-head and n2-head machines respectively,
then there exist machines 1l and ~ 2' each with at most nl+n2 heads such
that

-71a) T(1) = T(Ot l)n T(Ot 2)
and
b) T( 2) = T(t1) U T(Ot2)o
Proof~ a) Let ~1 have nl+n2 heads with the first n1 heads placed
on tapes in the manner of O~1 and the second n2 heads placed on tapes in
the manner of 2~ Let the statesof ~1 be doubletons of the form (Si l si )
where Sil E S tU {ARI and si2 So2 J {A,R}o Let (sI ~1 ) be the
initial state of 1ol
If 1 is in state (sil si2) and reads input (1n, a2,.... anl+n2)
thenmgoes to state (sjl, sj2) with head movements (dl,d2,..., dnl+n2)
where jl, s j2 and dl, d2,..0.. dnl+n2 are determined from the transition
tables of 01l and 02 as follows:
M 01 (Sil an l d
L (Si2 l a+l, s. anl+n2 ) (s2 ( dnl+l.. dnl+n2)
[it is understood that on all inputs (01 and Cl2 go from
A to A]o
TheACCEPT state in 1 is (A, A)
As constructed,1 will accept an m-tuple of tapes t if and only
if t is accepted by both Ot1 andO t2; thus T( 1) = T(t1) ( T(Ot2).
b) Construct 2 exactly as 1 above and then merge all states
of the form (A, A), (A, si2) (Sil A) into a single accept state 2 will
accept an m-tuple of tapes t if and only if Ol1 or Ot2 or both accept t;
thus T(82) = T(Ot1) U T(Otp2)

-72Theorem 5~8 If Ot is any n-head machine that strongly represents T(OL)
(ioe., any input to Ot is either accepted or strongly rejected) then there
is an n-head machine f that strongly represents rT( )o
Proof: Interchange the labels of the A and R states of Ot
One obtains an n-head machine f that strongly represents "- T(Ot) since
if t takes QL to A then it takes f to R and if t takes Otto R it takes
to A.
QED
Note 5~8 One is obliged to restrict the hypothesis of Theorem 5~8 to
machines that strongly represent their sets. The reason for this is that
there are some sets which can be weakly represented at best and thus the
construction of Theorem 5.8 would not be possible. A case in point: let
T be the set of all 1-dim tapes over {B, O} such that at least one cell
to the right of the initial cell contains 0. T can be weakly represented
by 1-way 1-dim 1-head machine GL shown in Figure 5.3.
5.2
OB/1 h
Figure 5o3o Machine OC5o2~

-73Any tape tY with all blanks to the right of the initial cell is weakly
rejected by 5. 2 therefore any machine f that purports to representJT(Q,5,2)
must accept to But no such f can exist for we would have to require
that f check all cells to the right of the initial cell for blanks -
thereby implying that f must go through an infinite number of cycles
before accepting to But via Theorem 5.o2 one deduces that f must accept
t' in a finite number of cycles. Therefore by contradiction f can not exist.
Speed Theorems
Theorem 5.9 If 0a is any 1-dim 1-head machine and t any tape for which
TOt (t) is defined then
T (t) > T ( )(t).
Furthermore if in accepting or strongly rejecting t, Ct stands still or
reverses direction then
=to(t) > T(Ot)(t)o
Proof: For any 1-dim tape t let tk be the subtape of t consisting of the cells -k, -k+l,...., -1,0,1,...., k. If t is accepted or
strongly rejected by t then there exists a smallest k such that (taccepts
or strongly rejects tk and never leaves tk Since k is the smallest such
number it follows that a must read cell -k or +k of t. Therefore
TOa(t) > k. But by construction a(Ot) is 1-way; thus one deduces that
T =(L) = k. Therefore T (t) > T (OL)(t)o
If in addition one knows that Ot stands still or reverses direction
in accepting or strongly rejecting t then
- _ (t). > k- = -_ n (+. _

Theorem 5o10 If OL is any 1-dim 1-head machine and t any tape for which
TaL(t) is defined then there is no n-head machine 3 for any n such that
G(G) = G(Ot) and such that TV (t) < T (O) (t).
Proof: If ~ is any such n-head machine then as in the proof of
Theorem 53.9, P must scan cell -k or +k of tk in order to accept or strongly
reject t. Thus T (t) > k = T ((t). Thus it is not possible that
T (t) < T 7(t)(t)
QED
Theorem 5.11 There exists an infinite collection of sets of 1-dim tapes
A?~ = {A.}, each set A. representable by 1-head machines such that if OCt
is anyl-head machine representing Aj (i.e., T(Otj) = Aj) then for any tape
t for which Totj(t) is defined
T 0j (t) > T((j)(t)
Proof: Let A. be the set of 1-dim tapes written over Z= {Ba}
such that A = {tl there are at least j a's to the right and left of the
J
initial cell)} Aj can be represented by a 1-head machine 0)j which
operates as follows:
1) 01k reads the initial cell; if B go to 2), if a go to 3)
2) move right counting the a s but not the B s; after j a's
reverse and count left for 2 j a's.o On the 2j-th a moving
left accept t.
3) move right counting the a s but not the B's; after j a's
reverse and count left for (2j + 1) a's. On the (2j+l)-th
a moving left accept t.

-75Thus there is at least one 1-head machine that represents A.
Let 0l1 be any 1-head machine that represents A.o tO.j cannot
strongly reject any tape since if tv is strongly rejected by Olj then tI
must have less than j a's either to the left or right of the initial cell
and no Ot. could check this in a finite number of cycles. Thus for any aL.
T t (t) is defined if and only if t C A.. But if t E Aj then OW must
j J j
reverse direction in accepting t since the definition of A. requires that
Oj. check both to the left and the right of the initial cell. Thus via
Theorem 5.9 TOtj(t) > T (C)(t) for all t such that T Oj(t) is defined.
QED
Note 5.9 The final paragraph of the proof of Theorem 5o1 assures one that
T (t) defined = T (t) defined for any 1-dim 1-head machine 0t and
and any tape t. Furthermore if 9 (tO) is constructed such that g(Ot)
weakly rejects t if and only if OLweakly rejects t then
T (t) defined- - Ti (t) defined.
Theorem 5.12 For any integer k>0 there exists an infinite number of sets
of 1-dim tapes all representable by 1-dim 1-head machines and such that
if A is any such set and 01, any 1-head machine representing A then
a) for all t in A Tot(t) > T (OL)(t) + 2k
b) for all t in Al, Al being an infinite subset of A,
TOa t)> k T3(~ (t) o
Proof: Part b) of the theorem will be proved first. For
convenience and without loss of generality one can limit k to the even
integers.

Let
E = {B, l 92' ~~ k+3
Let the set Ak be defined as all 1-dim tapes over Z of the form
shown in Figure 5~4 where a.,i aaj and aci, B for all i,jgi#3.
-2 Yk,-Ya Yi ~ YkiK
Figure 5.4, Form of Tapes in Ak.
There exists at least one 1-head machine t that represents AkO
C works as follows:
1) Read initial cell and remember Ado; if ao = B reject t.
2) Move right to first non-blank cell. This contains 1al Check
cll ~ acor and al 7 B and remember c~1o
3) Move left past io to first occurance of.1o Check that ago
has not occurred more than once. Move left to read sa
Check Check Check B or 2 or
4) Move right past a(... ao~.... to.2'.... etc..
o
O(Lwill finally move left to read ak-l' will check for proper
occurances of o, a)1... and will move left to read Oak. Check

-77that B. a B,, aO -... Then move right passing
E (2o k-1
ak_19 yk-2' 9 d,~ aeo1, k.... i ekl' C and stop~
Accept to
The complete process described above requires only a finite
memory and therefore can be done by a finite state machine~
Referring to the tape form in Figure 594 let the distance from
the initial cell to ai on the left and on the right be xiL and xiR
respectively~ Any tape in Ak is governed by the relations
Yi > 1 for all i
XlR = Yl
x2R - XlR + Y3
X3R X2R+ 1
X4R = X3R + Y5
X(k-l)R = (k-2)R + 1
kR = X(k-l)R + Yk+l
X1L Y2
x2L = XlL + 1
X3L = X2L + Y4
o
XkL= x(k- -)L 1
Consider any 1-head machine CL' that represents Ako Consider
also the set of tapes in Ak such that yi > S og for all io Call this

-78subset of Ak by the name A"o
( dt)tA, T L:(t) > T (t)
since ct' if it represents Ak can go at most a distance < S
past each a. before reversing direction and discovering the value of
ai +l
Consider Ak the subset of Ak that contains all tapes of A"
k
rk2 + k(k-2)
such that yl > 2
and
Y2, y3, * Yk+l = r
where
r = S3O + 1l
Ak is an infinite subset of Ak and for any tEAl, T0t (t) > T (t)
since Al c A".
But TOt(t) = 2y1 + 2(y2 +1) + 2(Yl+Y3+1)
2(y2+l+y4+) +.......... + (Y1+Y3+l+Y5+l+ + + l+yk+1)
> kyl + Y1l
Thus
TCtl(t) > ky1 + Y1 for all tEAro
Now
T (t)= max [XkR' XkL]
But for all teAk x xL + > x
k kXR kL +1 kL~
Thus
T, (t) Yl + Y3 + 1 + + 1 + Yk+l
rk+k-2
for all tAk.

-79So for all teA'
T (t)-k T (O(r) > kyl + Y1 - ky rk +k(k-2)
~~1 2~ ~ 2
rk2 + k(k-2)
But if teA' then
rk2 + k(k-2)
Y1 ~ 2
and so
To,(t) - kT > O
or
To0(t) > kT
which proves the first part of the theorem. If Ak satisfies the theorem
then A for all i > 0 also satisfies the theoremo Therefore the number
of sets of tapes satisfying the theorem for any particular k is infinite.
To deduce part a) of the theorem one can argue that if C1 is
any 1-head machine that represents Ak then Ot must at least go out to
read ok on one end and then reverse and read out to ck on the other endo
Thus for any teAk
TOt(t) > min [2xkL + XkR, 2XkR + XkL lo
But for any teAk
T () (t) = max [XkL, XkRl
Thus for all teAk
T0 (t) - T (ot)(t) = min [XkL + XkR' 2XkL, 2XkR]
> 2k
or
Tz,(t) > T (o)(t) + 2k. QED

-80Theorem 5.13 Let = {0ti} be the set of all 1-head machines recognizing
some set of 1-dim tapes Ao Let d (J) be the 1-way 2-head equivalent of
any machine in ~ > Then for any particular tape t in A there is a machine
Ot in 9 such that
T (to) < 3T ()(to).
Proof: (I) is independent of which machine in o was used
as its basis since all machines in gi have the same set of generators.
Let tocA and let T () (to) = x. Ot can be constructed to first
check any tape t by reading left x cells and then right 2x cells - this
gives OLenough information to decide if t and to have the same generator.
If t has the same generator as to then Ot accepts t; if not aO moves x
cells left (which returns its head to the initial cell) and then proceeds
to examine t according to the procedure of any machine O\tin 9 o
By the construction of 0t1 it is necessary that cOLE and that
TO(to) < 3x =3T (to)
QED

CHAPTER VI
TOPICS FOR FURTHER STUDY
Reduction Problems
Among the possible criteria one can use as a measure of the
complexity of n-head machines are three that arise naturally from the
structure of n-head machines; namely, the number ofheads, the number of
states, and the speed in accepting or strongly rejecting inputs. Relative
to these criteria three problems can be formulated:
1) Head Reduction Problem: given a set of tapes T produce
a machine with as few heads as possible that represents To
2) State Reduction Problem: given a set of tapes T produce
a machine with as few states as possible that represents T.
3) Speed Reduction Problem: given a set of tapes T produce
a machine that represents T and that accepts or rejects
inputs as quickly as possible.
The above three problems, both in their most general form and
in many special forms, constitute an area of almost totally unexplored
questions. A collection of remarks and observations on these reduction
problems follows below.
1. Head Reduction
Two heads, hi and hj, of any machine Otwill be said to be bound
if and only if hi and hj are on the same tape and if for all inputs to t
there is a finite upper bound on the distance that ever exists betweenhi
and hjo The bound property determines an equivalence relation on the set
-81

-82of heads H of OA in that heads are in the same equivalence class if and
only if they are bound to each other. It is a consequence of the bound
property that if H is divided into p such equivalence classes then OL
can be shown to be computationally equivalent to a machine with p heads
(one head per equivalence class of H). However, no general method is
known to determine if two heads are bound and further there is no guarantee
that the p-head machine is indeed the minimum head machine equivalent to Ot
One might try to show that for each i = 1,2,.. there is a set
of inputs Ci such that Ci can be represented byamachine with i-heads but
no fewer. This is indeed the case if Ci equals some non-trivial set of
i-tuples; thus to represent Ci any machine must have at least one head per
tape or at least i-heads. In order to render the question more significant
one might re-ask the question but restrict Ci to be a set of 1-dim tapes.
It is the author's conjecture that the set Ci defined as the set of 1-dim
tapes written over Z = {B,0,1) and having generators of the form
Xi X X 1 0x3 XlX2 x 1
O X1 0X 03. 01 011 0 1- can be represented with no machine
having fewer than i-heads. Certainly Ci can be represented by an i-head
machine.
It is an interesting application of Minsky's paper that if the
initial cell of every tape submitted to a machine is uniquely distinguishable then every set of m-tuples definable by a Turing machine is representable by an n-head machine with at most m+2 headso This result follows from
letting two heads in conjunctionwith the uniquely distinguishable initial cells
of their tapes represent the total state transition of the Turing machine
via Minsky and letting the remaining m heads be placed one head per tape
and read and move according to the inputs and the state of the Turing machine.

-832, State Reduction
If one confines one's interest to 1-way machines then the
classical reduction methods as introduced by Moore(4) suffice to yield
the minimum state equivalent of any machine. The general problem for
2-way machines is, however, unsolved. Namely, given a representable set
of inputs, no method is known for securing a minimum state machine to
represent the set.
Some remarks can be made about reducing the number of states
in a given machine. All inaccessible states can be eliminated from any
machine. All inaccessible transitions can be made "don't care" transitions. Further, given a machine 0C possibly with some don't care transitionsone can ignore the head movement associated with each transition and
apply a conventional state reduction procedure to O uthus partioning the
state set of Otinto equivalence classes of mergable states; given any two
states in the same equivalence class one proceeds to merge them if and only
if for any input the transitions leaving each state on that input have
identical head movements. The above technique of state reduction never
alters the number of heads in a given machine.
In general the head reduction and state reduction problems are
not independent - consider the machines 016.1 and a6o2 shown in Figures
6.1 and 6.2 respectively: C56.1 has 1-head and four states while Ot6.2
has four heads and one state (A and R are not counted here). O 6.1 is a l-way
l-head machinein reduced form but 0t6.2 is a 2-way 4-head machine with
fewer states than L 6.1 1 Careful inspection will show that
G( 1 6.1) = G( 6.2) = aa*bb*cc*B,

-84a/i b/i c/i
a/i ab/i c/i B A
S21 S3 s4
Figure 6.i. Machine Ot
(a,bc,c)/O,0, 01,
(abbb)/OOll a
Figure 6.2. Machine 6 2~
3. Speed Reduction
If Al is a set of tapes representable by some i-dim i-head machine
011 then via theorem 5.10 one knows that i (0~1) is the fastest (or one of
a set of the fastest) machine that recognizes any tape in Alo If A2 is a
set of D-dim tapes representable by some n-head machine Ot2 then if G(OM2)
is finite one can construct a machine 01,2 such that G(0L2) = G(0 2) and
such that no machine is faster than 012. [Ot 2 will be provided with a

suitably large number of heads that will fan out from the initial cell of
the tape such that after each machine cycle an increasing region of tape
will have been scanned; if g is any generator in G(02) and if md(g) is the
Manhattan distance to the cell of g farthest away from the initial cell
then a02 will recognize g in md(g) machine cycles - no machine could do it
faster~ If A3 is a set of D-dim tapes representable by some n-head machine
OL and such that G(Ot ) is infinite then in general it appears that there
3 3
is no single machine equivalent to O 3 and which detects all gEG(0t)
3
faster than any other machine; rather it seems that for any machine O 3
computationally equivalent to O3 there is another machine Qa3 such that
for all inputs0a3 is just as rapid as Ot3 and for some inputs OL3 is more
rapid.
One might also expect that the state reduction and head reduction
problems are not independent of the speed reduction problem.
Representability Problems
In the synthesis theorems of Chapter IV one was required to begin
with a realizable RE; failure to do so resulted in an "improper" machine,
ime., a machine in which some of the states had several transitions leaving
it on the same input, each transition having a different associated head
movement. In general it appears that non-realizable RE's cannot be used as
a basis for machine synthesis; however, some techniques can be tried in an
effort to procure "proper" machines to represent sets of inputs based on
non-realizable RE's. For example:
If Ct is the improper machine derived in an attempt to represent
a set of inputs based on I, a non-realizable RE,

-861) if one of the offending transitions goes to A then the remaining
offending transitions that leave the same state as the transition
going to A can be deleted from C! without affecting T(Ot);
2) if any offending transition can be shown to be inaccessible then
that transition can be deleted from Ok without affecting T(MO);
3) if the number of times the machine will pass through a state s
from which offending transitions emanate is finite for all inputs
then by expanding the number of heads and states of the machine
one can construct a new machine Ot that is proper in regard to
all transitions leaving s and equivalent to Ot [ (DC operates by
dividing part of its head set every time it embarks on the offending transitions; a part of the set follows each transition; since
C passes through s a finite number of times Ot will have to
split its head set at most a finite number of timesl;
4) if p3f is finite then one can always construct a realizable RE PI
such that O'lf -='ff, thus the machine Ot' based on'i will be
equivalent to Ot; if &Vf is not finite one can still search for
a realizable RE PI such that ~''*f = OVf in which case a machine
derived from'i will be equivalent to the machine derived from Pf

CHAPTER VII
SUMMARY
This paper attempts to treat the problems associated with multiple
head finite state machines. It begins, in Chapter II, by (1) defining
n-head machines, (2) defining the form of their inputs, and (3) prescribing
the manner in which these machines accept and reject inputs. As defined
in this paper n-head machines are the same as classical single head automata,
as understood by say McNaughton and Yamada, with the restrictions and additions that (1) there can be only two final states, namely ACCEPT and REJECT,
(2) if the machine enters one of these final states it halts operation
immediately, (3) each transition in these machines is specified by the present state of the machine and by the n-tuple of input symbols scanned by the
heads, (4) each transition is accompanied by an n-tuple of head movements
which need not be identical for all transitions in a given machine, and (5)
the inputs are multi-dimensional tapes that in general can extend in all
directions from the initial (or starting) cell of each tape.
Resulting from these machines' ability to accept and reject inputs
is the notion of using them to define sets of inputs depending on whether
an input set is accepted or rejected by a particular machine. Chapter II
develops the concept of generators as it applies to sets of defined inputs
and shows that for each machine its generator set is equivalent to its set
of defined inputs.
It is evident from the examples included in Chapter II that n-head
machines are more powerful than single head machines. It is further demonstrated that even with the restrictions that (1) n-head machines always
-87

-88start with their heads on the initial cells of their input tapes and (2)
all movements are one-cell-at-a-time -in-a-coordinate-direction, nevertheless
the computational power of the machines is just as great as with machines
that do not start on initial tape cells and whose head movements may not
all be unit moves.
Chapter III introduces a language which is later shown to be
equivalent to n-head machines in its ability to define sets of tapes. The
language presented includes the already well known language of regular
expressions which has been augmented to include the newly defined operations of column alphabets, indexed alphabets, and the separation, fold
and cover of tapes. These newly defined operations correspond in a
natural manner to the structure of n-head machines - i.eocolumn alphabets
correspond to multiple heads, indexed alphabets correspond to the movements
associated with each head, separation corresponds to several distinct heads
working simultaneously, fold corresponds to 2-way D-dim head movements and
cover corresponds to several distinct heads scanning the same tape.
In Chapter IV an equivalence is developed in the form of twelve
theorems between the input generators defined by n-head machines and particular expressions in the language of Chapter III. The theorems constitute
six analysis-synthesis pairs which treat n-head machines of various complexities beginning with 1-way 1-dim 1-head machines and concluding with 2-way
D-dim n-head m-tape machines. Aside from their academic value these
theorems are useful in that given a desired set of generators if one can
represent them by a suitable expression in the language then the synthesis
theorems allow direct implementation of a machine possessing the given
generators,

-89Chapter V deals with a number of questions relating to n-head
machines. It begins by presenting two algorithms - one to decide if a
given n-head machine is 1-way, the other to decide if a given regular expression is realizable; both of these algorithms are necessary for execution of
some of the theorems in Chapter IV. Chapter V develops a 1-way 2-head equivalent of every 2-way 1-dim 1-head machine. Note that under the assumptions
of this paper a 2-way automaton is allowed to scan both sides of the initial
cell; under this condition the fifteenth theorem of Rabin and Scott becomes
invalid and is replaced by Theorem 5.1 of this paper.
The work of Rabin and Scott is extended in Chapter V to include
all n-head machines. The results of Theorems 5.3 to 5.6 can be summarized
as follows:
The existence or non-existence of effective procedures
to answer certain decision questions partitions the
class of n-head machines into three categories as per
the following table.
TABLE 7.1
THE EXISTENCE OF EFFECTIVE PROCEDURES
FOR DECISION PROBLEMS
*i \ Type of
Ma chine 1-Dim D-Dim General
f 1-Head 1-Head n-Head
i Decision D > 2
Problem! Particular
ParticularYes Yes No
Input Problem
i Emptiness, State Acces- ll
sibility and Transition Yes t No No
Accessibility Problems
I ~~~~~~~~~~~i

-90Chapter V continues by presenting a number of theorems treating
the Boolean properties of n-head machines and concludes with a number of
theorems treating the relative speeds of computationally equivalent machines,
The speed theorems are developed within the milieu of 1-dim machines. Some
but not all of the speed theorem results can be extrapolated to multi-dimensional machines. The speed theorems can be paraphrased as follows:
For each 1-head machine Ot working over 1-dim tapes there
is a 2-head 1-way machine' (Ot) which is computationally
equivalent to 0. ot (1L) is always as fast as m and
is faster than Ot if and only if Ot reverses or halts its
head movement during examination of an input. There are sets
of 1-dim tapes Al, A2,ooo Aj,ooo such that if O is any
1-head machine defining Aj then (Olj) is faster than
01j for all inputs. Furthermore, the A. can be defined
such that for all inputs in Aj $ (O1j) is faster than
Ot. by an arbitrarily large difference and for all inputs
in some infinite subset of A. (Otj) is faster than OL
by an arbitrarily large factor. For any set A of 1-dim
tapes definable by 1-head machines and for any particular
tape to in A there is a 1-head machine ao that defines A
and has the property that no machine that defines A is more
than three times faster than Oto in recognizing to,
Chapter VI contains some suggestions for further studyo These
suggestions lie in the areas of (1) head-state-speed reduction and (2)
representability problems. A number of partial results are included with
each suggestion. Some of the partial results are:

-911) It is evident that the number of heads and states a machine
has and the speed with which it recognizes inputs are not
independent quantities. The work of previous authors on
these reduction problems has been confined to 1-way 1-dim
1-head machines; expansion of the field of inquiry to 2-way
n-head machines seems reasonable and re-opens many questions
considered answered for the 1-way case.
2) Given any set of inputs one can ask if an n-head machine
exists that defines the set. Using the work of Minsky for
direction one can conclude that if the initial cellsof all
tapes are uniquely distinguishable by machines - as they
must be by us - then all sets of m-tuples of tapes definable
by Turing machines are definable by finite state machines
with at most m+2 heads. If, however, as this paper has
assumed, the initial cell is not uniquely distinguishable
by the machines then it is an open question in general as
to whether one can decide given a set of inputs if an n-head
machine exists that defines the set.

BIBLIOGRAPHY
1. Harrison, M. A. EE 467 Notes, Department of Electrical Engineering,
University of Michigan, Ann Arbor, Michigan, October 10, 1961.
2. Kleene, S. C. Representation of Events in Nerve Nets and Finite
Automata, Automata Studies, Annals of Mathematics Studies, 1956,
Princeton University Press, Princeton, New Jersey~
3~ McNaughton, Ro F. and Yamada, H. Regular Expressions and State Graphs
of Automata, IRE Transaction on Electronic Computers, Vol. EC-9, No~ 1,
March, 1960.
4o Minsky, Mo L. Recursive Unsolvability of Post's Problem of "Tag"
and Other Related Topics, Annals of Mathematics, Vol. 74, No. 3, (1961),
437-455.
5. Moore, E. F. Gedanken - Experiments on Sequential Machines, Automata
Studies (see Reference 2)~
6. Rabin, M. 0. and Scott, D. Finite Automata and Their Decision Problems,
IBM Journal of Research and Development, Vol. 3, No. 2, April, 1959.
7. Shepardson, J. C. The Reduction of Two-way Automata to One-way
Automata, IBM Journal of Research and Development, Vol. 3, No. 2,
April, 1959.
-92