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