COMPUTATION BY ONE-WAY MULTIHEAD MARKER AUTOMATA BY MICHAEL MARTIN GORLICK A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE IN THE FACULTY OF GRADUATE STUDIES (Department of Computer Science) We accept t h i s thesis as conforming to the required standard. THE UNIVERSITY OF BRITISH COLUMBIA October, 1978 1978 (c) Michael Martin Gorlick, In p r e s e n t i n g t h i s t h e s i s in p a r t i a l f u l f i l m e n t o f the r e q u i r e m e n t s f o r an advanced degree at the U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e that the L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r a g r e e t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by the Head o f my Department o r by h i s r e p r e s e n t a t i v e s . It i s u n d e r s t o o d that c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l not be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . Michael Martin Gorlick Department o f rnmpnter Sr.iflnr.fi The U n i v e r s i t y o f B r i t i s h Co lumbia 2075 Wesbrook Place Vancouver, Canada V6T 1W5 D a t e Qctmbgr 11, iq78 i i A b s t r a c t A new f a m i l y o f automata, one-way mul t ihead marker automata, i s i n t r o d u c e d . I n t u i t i v e l y these dev i ces c o n s i s t o f one or more read heads t r a v e l l i n g i n a s i n g l e d i r e c t i o n on a bounded tape and a f i n i t e f i x e d pool of markers which may be depos i ted on the t a p e , sensed , and l a t e r removed. The major r e s u l t s obta ined a r e : ( i ) A one-way n-head k-marker automaton w i t h d i s t i n g u i s h e d markers (each marker i s r e c o g n i z a b l y d i s t i n c t ) may be s imulated by a one-way n-head (k+1)-marker automaton w i t h un i form markers (one marker cannot be t o l d from a n o t h e r ) ; ( i i ) Minor r e s t r i c t i o n s i n pebble use and head movement do not s i g n i f i c a n t l y a f f e c t the r e c o g n i t i o n power o f these d e v i c e s , consequent ly i t i s p o s s i b l e to o b t a i n normal forms f o r dev i ces w i t h e i t h e r d i s t i n g u i s h e d or un i form markers ; ( i i i ) I f p(x) i s a po lynomia l w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s o f degree k>0 then the language { 0 P ^ in e {0,1,2, . . . }} i s recogn ized by a d e t e r m i n i s t i c s.one-way k-head ( k - 1 ) - m a r k e r automaton; ( i v ) There e x i s t s a c l a s s o f o n e - l e t t e r languages , c h a r a c t e r i z e d by f i n i t e l i n e a r d i f f e r e n c e e q u a t i o n s , which are recogn ized by a d e t e r m i n i s t i c one-way n-head 2 -marker automaton. Members o f t h i s c l a s s i n c l u d e the f i b o n a c c i numbers and a l l languages {Cr ; j n 6 {0 ,1,2, . . . } } , k a f i x e d n a t u r a l number. Th is c l a s s i s o f p a r t i c u l a r i n t e r e s t s i n c e i t c o n t a i n s languages not generable by any p o l y n o m i a l , p rov ing that a complete c h a r a c t e r i z a t i o n o f the o n e - l e t t e r languages recogn ized by one-way mul t ihead marker automata can not r e s t upon the po lynomia l languages a l o n e . i Table of Contents i i i Chapter I N o t a t i o n and d e f i n i t i o n s 1 S e c t i o n 0 I n t r o d u c t i o n 1 S e c t i o n 1 Elementary n o t a t i o n 3 S e c t i o n 2 Programs, dev i ces and products o f dev i ces 5 S e c t i o n 3 R e d u c i b i l i t y and s i m u l a t i o n s 9 S e c t i o n 4 Machines 15 S e c t i o n 5 C l a s s i c a l d e v i c e s 17 Chapter I I One-way mul t ihead marker automata 19 S e c t i o n 0 I n t r o d u c t i o n 19 S e c t i o n 1 P r e l i m i n a r y d e f i n i t i o n s 20 S e c t i o n 2 Equ iva lence o f dev i ces w i t h d i s t i n g u i s h e d markers 25 S e c t i o n 3 The equ iva lence of un i form and d i s t i n g u i s h e d markers 33 S e c t i o n 4 Normal forms 42 Chapter I I O n e - l e t t e r languages 54 S e c t i o n 0 I n t r o d u c t i o n 54 S e c t i o n 1 N o n d e t e r m i n i s t i c o n e - l e t t e r languages 56 S e c t i o n 2 D e t e r m i n i s t i c o n e - l e t t e r languages 64 S e c t i o n 3 Other o n e - l e t t e r languages . 76 B i b l i o g r a p h y 84 List of Figures iv Figure II.2.3 32 Figure II.3-4 41 Figure II.4.9 53 Figure III.2.1 64 V Acknowledgement My g r a t e f u l thanks t o : The i n d i v i d u a l s who prov ided f i n a n c i a l support d u r i n g my long a s s o c i a t i o n w i t h the department. They a r e : John L. Baker , W i l f r e d Hansen, F r e i d e r Nake, J . L. P a r k e r , J . E. L. Peck and Ray R e i t e r ; Pau l Gi lmore and David K i r k p a t r i c k f o r t h e i r a i d and understanding d u r i n g the d i f f i c u l t l a s t months; John Baker , my t h e s i s a d v i s o r , f o r h i s p a t i e n c e , wise c o u n s e l , and u n f l a g g i n g i n t e r e s t i n my work; Tom Rushworth f o r h i s a s s i s t a n c e i n the e d i t i n g and f o r m a t t i n g of chapter I I I ; Da l ton Cameron f o r h i s company d u r i n g the wee hours of the n i g h t ; My p a r e n t s , who had the good sense to l e t me do p r e t t y much as I damn w e l l p l e a s e d . Th is t h e s i s i s ded icated to Robbi Oake f o r whom s imple thanks are complete ly inadequate . Chapter I 0 I n t r o d u c t i o n , The s i m p l e s t c l a s s o f automata u s u a l l y c o n s i d e r e d c o n s i s t s o f a d e v i c e w i t h a s i n g l e r ead head t r a v e l l i n g i n a f i x e d d i r e c t i o n a l o n g a f i n i t e t a p e . The head may examine, but no t a l t e r , t he c o n t e n t s o f the tape squa re under s c a n . The l anguages a c c e p t e d by d e v i c e s o f t h i s d e s c r i p t i o n a r e known as t he r e g u l a r l a n g u a g e s . G e n e r a l i z a t i o n s o f t h e s e d e v i c e s have been c o n s i d e r e d by s e v e r a l w o r k e r s . Rosenberg [Rosenberg 64, 66, 67a , 67b] i n v e s t i g a t e d the powers o f r e c o g n i t i o n o f one-way i n p u t d e v i c e s w i t h more than one h e a d . Sudborough [Sudborough 71 , 76], m o t i v a t e d by l i n e a r bounded automata ( d e v i c e s w i t h a s i n g l e head c a p a b l e o f mot i on i n e i t h e r d i r e c t i o n which may r e p e a t e d l y i n s p e c t and o v e r w r i t e the c o n t e n t s o f any t a p e s q u a r e ) , s t u d i e d one-way m u l t i h e a d w r i t i n g f i n i t e au tomata , d e v i c e s w h i c h , though r e s t r i c t e d t o one-way t a p e m o t i o n , a r e a l l o w e d t o w r i t e on the t a p e . In an e f f o r t t o g e n e r a l i z e pushdown au tomata , I b a r r a [ H a r r i s o n and I b a r r a 68] c o n s i d e r e d o n e - and two-way m u l t i h e a d d e v i c e s w i t h o u t powers o f w r i t i n g , bu t accompan ied by a pushdown s t o r e . To c a p t u r e the n o t i o n o f f i n i t e w r i t i n g , S p r i n g s t e e l [ S p r i n g s t e e l 67 , R i t c h i e and S p r i n g s t e e l 72] found i t p r o f i t a b l e t o d e f i n e two-way m u l t i h e a d d e v i c e s c a s t i n t he f i g u r e o f "bounded c o u n t e r " au tomata . In one f o rm, such a d e v i c e has a s i n g l e two-way read head and a f i x e d number o f marker s wh ich may be d e p o s i t e d on the t a p e , s e n s e d , and l a t e r removed. We s h a l l cons ide r a dev i ce which stands midway between the g e n e r a l i z a t i o n s o f Rosenberg and Sudborough, and bears some resemblance to the dev i ces o f S p r i n g s t e e l o u t l i n e d above. One-way mul t ihead marker automata are obta ined from Rosenberg 's d e v i c e s by a l l o w i n g the heads to l a y down and p i c k up markers obta ined from a f i n i t e f i x e d pool ( thus are ab le to perform a l i m i t e d amount of w r i t i n g ) as they pass a long the input t a p e . Why study such dev i ces? In p r a c t i c a l terms, our aim i s to o b t a i n e f f i c i e n t r e c o g n i z e r s o f l a r g e c l a s s e s o f i n t e r e s t i n g languages. The d e t e r m i n i s t i c pushdown automata which correspond to the c l a s s o f d e t e r m i n i s t i c c o n t e x t - f r e e languages are one example, f i n i t e s t a t e acceptors and the r e g u l a r languages another . I f we r e s t r i c t our a t t e n t i o n to d e t e r m i n i s t i c Chapter I 2 computat ions , the appeal o f one-way head motion i s o b v i o u s , f o r i t i m p l i e s the abscence of backup. We s h a l l see t h a t , w i t h respec t to o n e - l e t t e r languages, one-way mul t ihead marker automata are s u r p r i s i n g l y p o w e r f u l , ab le to recogn ize such languages as the f i b o n a c c i numbers, the range o f any po lynomia l w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s whose domain i s r e s t r i c t e d to the n a t u r a l numbers, and a l l s e t s o f numbers o f the form {k n } , where k i s a f i x e d n a t u r a l number and n v a r i e s over the n a t u r a l numbers. Mu l t ihead d e v i c e s have the f l a v o r of m u l t i p a s s a l g o r i t h m s w i t h s e v e r a l passes (heads) p o s s i b l y runn ing c o n c u r r e n t l y , each pass t a k i n g advantage of the i n f o r m a t i o n obta ined by the p r e v i o u s . Rosenberg's d e v i c e s t r a n s m i t i n f o r m a t i o n from one head to another s imply by t r a n s f e r s i n the f l ow o f the f i n i t e s t a t e c o n t r o l . One-way mul t ihead marker automata i n a d d i t i o n to t h i s method use markers as a means o f " i n t e r h e a d " communicat ion, so these dev i ces may be used to c o n s i d e r the e f f e c t i v e n e s s and u t i l i t y o f markers as a programming t e c h n i q u e . Th is t h e s i s has th ree c h a p t e r s . The f i r s t chapter i s devoted to i n t r o d u c i n g the n o t a t i o n and b a s i c d e f i n i t i o n s employed i n the f o l l o w i n g two. I make heavy use of a n o t a t i o n [Baker 77b] which bears l i t t l e resemblance to the forms o f c l a s s i c a l automata t h e o r y ; s e c t i o n s 1-3 of chapter I t h e r e f o r e r e q u i r e c a r e f u l r e a d i n g . Chapter I I c o n t a i n s the formal d e f i n i t i o n s o f a v a r i e t y o f one-way mul t ihead marker automata. There i t i s shown t h a t a one-way n-head k-marker automaton w i t h d i s t i n g u i s h e d markers (each marker i s r e c o g n i z a b l y d i s t i n c t ) may be s imula ted by a one-way n-head (k+1)-marker automaton w i t h un i form markers (one marker can not be t o l d from a n o t h e r ) . In a d d i t i o n I s h a l l o b t a i n s e v e r a l normal forms which correspond to those d e r i v e d by Sudborough [Sudborough 71] fo r one-way mul t ihead w r i t i n g f i n i t e automata. Chapter I I I e x h i b i t s two l a r g e and v a r i e d c l a s s e s o f o n e - l e t t e r languages - the f i r s t c h a r a c t e r i z e d by po lynomia ls w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s , the second by f i n i t e l i n e a r d i f f e r e n c e equat ions - acceptab le by d e t e r m i n i s t i c one-way mul t ihead marker automata. These c l a s s e s y i e l d languages which are not a c c e p t a b l e by any one-way mul t ihead automaton, bounded r e v e r s a l mul t ihead automaton, n-head pushdown automaton or one-way s t a c k automaton. Chapter I 1 Elementary notation. 3 The following notation i s used here: card X denotes the c a r d i n a l i t y of the set X. X\Y denotes the differ e n c e {x6X!x0Y}. XUY and X f!Y denote set union and i n t e r s e c t i o n r e s p e c t i v e l y . X e Y i f and only i f x 6X implies x 6 Y . X<=Y means Xs=Y where y eY and y 8X for some y. P(X) = {S|S^X}, the powerset of X. D denotes the empty set, 1 the set {0} and 2 the set {0,1} (where convenient), N the set {0,1,2, ...} of natural numbers, N + the set N\{0}, and R the set of r e a l numbers. The word " p o s i t i v e " when used i n reference to the integers means "greater than or equal to zero". I f 0 i s to be excluded I s h a l l say " s t r i c t l y p o s i t i v e " . Members of cartesian products are expressed as ordered tuples or as functions defined on an index set, according to convenience. However i t i s assumed that cartesian products are defined by a universal construction so that, f o r example, cartesian product as an operation on sets i s asso c i a t i v e and commutative. X+Y denotes the d i s j o i n t union of sets X and Y, s i m i l a r l y assumed to be defined by a universal construction. Members of X+Y are usually expressed as i f they were members of XUY, with X("]Y=D. "Function", here, unless e x p l i c i t l y stated otherwise, means " p a r t i a l function". S p e c i f i c a l l y f:X->Y means that f i s a function (single-valued r e l a t i o n ) defined for some elements of the set X and taking values i n Y. dom f={x!y=f(x) f or some y eY}; codom f={y!y=f(x) for some x6X}. As usual the barred arrow s p e c i f i e s a function by i t s action on an element. f:x|->y means (in the proper context) y=f(x). I f X i s a set, I d x denotes the i d e n t i t y r e l a t i o n (or function) on X. o denotes composition of ( p a r t i a l ) functions and i s always defined. z=[gOf](x) i f and only i f there i s some y such that y=f(x) and z=g(y). Thus dom(gOf)={x!f(x) edom g} and codom(gOf)={g(y)!y ecodom f}. If A i s a set then A denotes the set of st r i n g s over A as an alphabet (the free monoid generated by A). A + i s the set of nonempty s t r i n g s over A. For x 6 A , |x| denotes the length of x (number of components), (x] denotes the s t r i n g obtained by deleting the f i r s t component, i f any, of x. [x) Chapter I 4 denotes the s t r i n g obta ined by d e l e t i n g the l a s t component, i f any, o f x . S denotes the empty s t r i n g (the i d e n t i t y o f A*) . Thus |3|=0, (B]=[3)=*. The symbol j_ w i l l mark the end of a p r o o f . I t a l i c [ s c r i p t ] w i l l be i n d i c a t e d by the presence of a - [~] beneath a l e t t e r ; to i l l u s t r a t e , "D" and " L " are i t a l i c "D" and s c r i p t " L " r e s p e c t i v e l y . Uppercase gamma, p i , s igma, ph i and p s i w i l l be represented by l - , u , "J, 0 , and Ij r e s p e c t i v e l y . The b o l d f a c e l e t t e r s a , i , x , z denote lower case a l p h a , i o t a , x i and ze ta r e s p e c t i v e l y . E and V a re the e x i s t e n t i a l and u n i v e r s a l q u a n t i f i e r s r e s p e c t i v e l y . The m a j o r i t y o f s e c t i o n s 2-4 i s excerpted from [Baker 76 , 77a , 7 7 b ] . The reader i s r e f e r e d t o [Baker 77b] i n p a r t i c u l a r f o r a d e t a i l e d d i s c u s s i o n o f the m a t e r i a l summarized h e r e , and f o r p roofs o f 2 . 8 , 3-5, 3 - 8 , 3-9, 3-16, 3 . 1 7 , 4 . 6 , 4 .7 and 4 . 8 . Chapter I 2 Programs, d e v i c e s and products o f d e v i c e s . 5 2.0 D e f i n i t i o n . A program [7 comprises the f o l l o w i n g : T|Q, a f i n i t e set - the nodes. i~[g BTTQ - the s t a r t node. n A , a p a r t i a l f u n c t i o n w i t h dom M£^MQ - the a c t i o n f u n c t i o n . n B , a p a r t i a l f u n c t i o n w i t h dom Tlg^dom n A X U f o r some f i n i t e set U and w i t h codom Mg^MQ - the branch ing f u n c t i o n . I t i s a l s o convenient to d e f i n e Up = nqNCdom u A ) - the t e r m i n a l nodes. MQ = codom ["[A - the commands. uy (z )={ ii edom ng) - the va lence o f z , de f ined f o r each z SMQ. -u = u z e u - Q { [ V z ) } -The usua l d o t s - a n d - a r r o w s n o t a t i o n f o r d i r e c t e d graphs i s convenient f o r s p e c i f y i n g programs. For a node z i n a program T]: to s p e c i f y t h a t [T A(z)=a w r i t e " z : a " (or j u s t " a " i f no r e f e r e n c e to z i s needed) near the dot r e p r e s e n t i n g z ; to s p e c i f y t h a t z i s a t e r m i n a l node, w r i t e " z : " or noth ing near i t s d o t ; to s p e c i f y tha t M g ( z , i ) = z ' , w r i t e " i " near the arrow r e p r e s e n t i n g the a p p r o p r i a t e edge < z , z ' > . Designate M S by p u t t i n g i t s dot at the head o f an arrow w i t h n o t h i n g a t i t s t a i l . To avo id g r a p h i c i n c o n v e n i e n c e , use an arrow w i t h " z " but no dot at i t s head to i n d i c a t e tha t the arrow i s to be taken as ending at the dot f o r node z . 2.1 D e f i n i t i o n . A dev i ce D comprises the f o l l o w i n g : DQ , Dg, Drj,, s e t s - the memory, i n p u t , and output s e t s . D-pDg-^Dq, DQ:DQ->D,J,, p a r t i a l f u n c t i o n s - the input and output f u n c t i o n s . DQ , a se t - the commands. DQ , a p a r t i a l f u n c t i o n w i t h dom D Q ^ D Q X D Q and codom DQ<=DQXU f o r some set U - the g e n e r a l i n t e r p r e t a t i o n . Chapter I 6 I t i s a l s o convenient to d e f i n e , f o r each a S D ^ , Dy(a)={i!D(a,m)= f o r some m, m'} - the va lence o f a . - a : D - Q ~*-Q X P - V ^ -nir>DQ(a,m) - the i n t e r p r e t a t i o n of a . Remark. By convent ion pure commands ( those a e D ^ f o r which card Dy(a) = 1) have va lence {0}. 2.2 D e f i n i t i o n . I f " i s a program and D a d e v i c e , then C ( u , D ) , the set of computat ions by n on D, i s the set o f sequences < Z Q , I I ] Q > . . . i n ]~IQ X DQ i n wh ich , f o r a l l j e {1,2, . . . ,n} , Drj ( 2 . \_ (mj_i ) = and n B ( Z j _ 1 , i ) = Z j f o r some i e{~} v(Zj_.,). Crj . (n,D), the set of t e r m i n a t i n g computat ions by TT on D, i s the set o f sequences < Z Q , I I1Q > . . . as above i n which z n eTCj,. The l e n g t h o f a computat ion of the above form i s n . 2.3 Lemma. I f " i s a program, D a d e v i c e , and 6{~IQXDQ, then there i s a t most one sequence . . . i n C^([j,D). 2.4 D e f i n i t i o n . I f " i s a program and D a d e v i c e , then Drr, the f u n c t i o n computed by IT on D, i s a p a r t i a l f u n c t i o n d e f i n e d t h u s : Drr :D s ->D T :xr>D 0(m) where . . . e C T(1T,D). The e f f e c t o f ( 2 . 5 ) , which f o l l o w s , i s to d e f i n e the product o f a f a m i l y F of d e v i c e s to be a dev i ce whose memory, input and output s e t s are the c a r t e s i a n products o f the cor responding s e t s i n F, and whose command set i s the d i s j o i n t union o f the command s e t s i n F. Def ine the input and output f u n c t i o n s to operate componentwise, and each command i n t e r p r e t a t i o n to respond to and to a f f e c t on ly the component (of a memory set element) to which i t a p p l i e s . In the f o l l o w i n g , the c a r t e s i a n product o f a f a m i l y { X j ! j 6J} of s e t s ( indexed by a se t J) i s taken to be the set o f f u n c t i o n s f : J - > U j g j X j f o r which f ( j ) ex.; f o r a l l j e j . Chapter I 7 2 . 5 D e f i n i t i o n . I f J i s a set and f o r each j 6 J D. i s a d e v i c e , then a dev i ce Xj g j Dj i s de f ined thus ( w r i t i n g P fo r the product Xj g j D j ) : £Q = x j e J ( D - j V Is - x j ej (P-j)s> £T = x j ej ( P . j V P j . - x b m , where m(j) = (Dj) j (x(j)) f o r a l l j 6 J . P 0 :mr>y, where y(j) = (Dj)n(m(j)) f o r a l l j 6 J . PQ i s the d i s j o i n t un ion +j g j (DJ)Q. For each a6PQ, i f a e ( D j )Q then P a :mr> where m'=m except t h a t m'(j) i s such t h a t (Dj) a(m(j)) = . A l l p roducts o c c u r r i n g i n t h i s paper have f i n i t e index set J . For these d e v i c e s and f o r t h e i r i n p u t s e t s , e t c . I use the u s u a l n o t a t i o n s D X E X D^, l e a v i n g the s p e c i f i c a t i o n o f index set i m p l i c i t . In case o f repeated f a c t o r s or where o therwise necessary , I d i s t i n g u i s h commands by n a t u r a l number or o ther a p p r o p r i a t e s u b s c r i p t s . When a product i s be ing denoted D X E X . . . or D^, elements o f i t s i n p u t , ou tput , and memory s e t s may be denoted by ordered t u p l e s , the order cor respond ing to t h a t o f the n o t a t i o n f o r the product , but p o s s i b l y w i t h s i n g l e t o n f a c t o r s o m i t t e d . 2 .5 D e f i n i t i o n . I f IT i s a program and D a d e v i c e , then IT i s f o r D i f and o n l y i f ITC?=DC and ITv(z) eD v(IT A(z)) f o r a l l z eJTQ. 2.6 Lemma. I f IT i s a program and D a dev i ce w i t h DQ^-Q, then there i s a program IT' f o r D such tha t JTj[ = Y\± f o r i 6 {Q ,S ,T } and C(|T',D) = C(TT,D). The f o l l o w i n g development f o r m a l i z e s the o b s e r v a t i o n tha t f i n i t e data s t r u c t u r e s are i n d i s t i n g u i s h a b l e from c o n t r o l s t r u c t u r e s . 2 .7 D e f i n i t i o n . A d e v i c e D has t r i v i a l i n p u t [ r e s p e c t i v e l y output ] i f and on ly i f card Dg=1 [ r e s p e c t i v e l y card DIJ.= 1] and dom D T = Dg [ r e s p e c t i v e l y dom DQ = DQ]. A d e v i c e i s t r i v i a l i f and on ly i f i t has t r i v i a l input and output and DQ i s f i n i t e . Chapter I 8 2 .8 Theorem. I f D i s a d e v i c e , E i s a t r i v i a l dev ice and ["[ i s a program then there i s a program IT such that Drr'(x)=y i f and on ly i f (D X E ) r j(x , s ) = where E s={s} and E T ={t } . N o t a t i o n . By v i r t u e o f 2 . 8 we may i n c l u d e use o f variables over f i n i t e s e t s i n any program. Where a p p r o p r i a t e , we s p e c i f y i n i t i a l values f o r such v a r i a b l e s . The commands to be employed a r e : x<-a , x<-y : assignment o f constant or c u r r e n t v a r i a b l e v a l u e s , valence={0}; x= : t e s t o f c u r r e n t v a l u e , va lence i s the set over which x v a r i e s . These n o t i o n s are to be understood i n t h e i r usua l programming language senses , assuming s t a t i c s torage a l l o c a t i o n f o r v a r i a b l e s . Chapter I 3 R e d u c i b i l i t y and s i m u l a t i o n s . 9 3.0 D e f i n i t i o n . I f D and E are d e v i c e s , then D i f f . . . eC T ( r , D ) . N o t a t i o n . I f G, D, D' are as i n 3-5 we c a l l the elements o f G programmable o p e r a t i o n s f o r D. We may d e f i n e programs under tha t name and use them i n programs f o r D wi thout f u r t h e r apo logy . 3.6 D e f i n i t i o n . For any dev ice D, No i s the programmable o p e r a t i o n s p e c i f i e d by - >®0 : . Remark. As a matter o f s t y l e , programmable o p e r a t i o n s whose va lence set i s {0,1} should be i n t e r p r e t e d as boolean p r e d i c a t e s w i t h 0 denot ing " t r u e " and 1 " f a l s e " . Chapter I 10 3.7 D e f i n i t i o n . I f D and E are d e v i c e s , then a s i m u l a t i o n o f D by E comprises f u n c t i o n s fq :Dq->Eq, f s : D s - > E g , f . j , :D T ->E T , f-j- and fQ:Eq->Eg, and f o r each a e D c f g :EQ ->EQ X Dy (a ) , a l l s a t i s f y i n g dom fq=Dq. fqODj = f I ° E I o f s , f T O D Q = E 0 o f 0 o f q . ^ Q X I d D v ( a ) ) ° e a = f a ° f Q f o r e a c h a e 2 C " There are programs Tj and {~Q such t h a t f o r i 6 { 1 , 0 } , m'=f^(m) i f f <(r^ )g,m> . . . <0,m'> 6 C T ( r i ( E ) . For each aep_Q and each f i n i t e subset V ^ D y ( a ) there i s a program i ~ a ^ such tha t ( f a (m) = and i e v ) i f f <(raV))s,m> . . . 6 C T ( ] ~ a V ) , E ) . The s t r i c t l y a l g e b r a i c requirements o f t h i s d e f i n i t i o n are s imply tha t the f o l l o w i n g diagrams commute: D s i ->DQ f I I f S I I Q I I S s — - - — » 5 Q - - — » E Q D Q y 4 D T 1 1 , I l f T § Q — ; — — ; — * £ T to ^0 D Q :S 4 D Q X Dv(a) 1 f 1 f Q X = Eq ->EQ*XD v(a) a The computat iona l requirement i s that E be microprogrammable to s i m u l a t e D i n the sense t h a t f T , f q and the f be computable on E. S ince Hp must be f i n i t e f o r any program ]~f, but Dy(a) may be i n f i n i t e , some strategem l i k e the i n c l u s i o n o f V as a parameter i n the requirement tha t Chapter I 11 the i ~ a ^ ( suppor t ing f a ) e x i s t i s n e c e s s a r y . I f Dy(a) i s f i n i t e , i t i s c l e a r l y s u f f i c i e n t to s p e c i f y X=D v ( a ) , which we denote s imply J~ a . 3.8 Theorem. I f D and D' are d e v i c e s and f i s a s i m u l a t i o n o f D by D', then whenever E i s a dev i ce and IT a program, there i s a program IT such tha t (D ' X E )n'0( f o X Idc- ) = ( f T X I d j , )0 ( D X E ) r r . - - 11 o 1 tip — - 11 3.9 C o r o l l a r y ( S i m u l a t i o n theorem). I f D and D' are d e v i c e s and there i s a s i m u l a t i o n f o f D by D' w i t h f"s= I ddom D£ a n d f T = I d c o d o m DQ T H E N 2 < < : 2 ' -With r e s p e c t to s i m u l a t i o n s , the f o l l o w i n g n o t a t i o n i s conven ien t . 3.10 D e f i n i t i o n . Let D be a d e v i c e , a6D c, w i t h Dy(a) = { i 1 , . . . , i s } f i n i t e ; d e f i n e UJJ a to be the program To show how the s i m u l a t i o n theorem i s used , I w i l l prove the f o l l o w i n g two d e v i c e s s t a b l y e q u i v a l e n t . 3.11 D e f i n i t i o n . I f A i s a f i n i t e s e t , the one-way i n p u t dev ice I n 1 ^ i s s p e c i f i e d thus ( o m i t t i n g the s u p e r s c r i p t ) : In1Q=A*XN, In1 s =A*, In1 T =1. In1j :x r>, In1 Q : h>0. In1 c ={I=,R} . I n 1 R : < x , k>K> « x , k + 1 > , 0 > i f and on ly i f 0r><,a> where, f o r some u,v e (A+{|-,H)) |-xH=uav, iu '=k , a eA+{h,-|}. 3.12 D e f i n i t i o n . I f A i s a f i n i t e s e t , the t i d y one-way i n p u t dev i ce t i d y I n 1 ^ A ^ i s s p e c i f i e d thus ( w r i t i n g D f o r t i d y I n 1 ^ ) : ( ¥ i 6 {Q ,S ,T , I ,C } ) D ± = I n l £ A ) . Chapter I 12 DQ.r>0 (undef ined o t h e r w i s e ) . (¥a 6 D C ) D A = i n 1 a A ) 3.13 Example. I n 1 ( A ) •« t i d y I n 1 ( A ) . P r o o f . To see tha t D=In1^A^ « E=tidy I n 1 ^ A \ c o n s t r u c t a s i m u l a t i o n f by d e f i n i n g f Q = I d D , f s = I d A * , f T = I d 1 , f j = I d E , . i f n<|x!+1 f 0 :r> < 1 undef ined otherwise , ( V a 6 D c ) f a = D a . The microprograms to support f a r e : T -' I " $No (vaeD c) ra = nn>a. Converse l y , to prove that t i d y I n l ^ << I n l ^ , l e t f Q , f g , f T , f T , f a , I ~ T > Va be as g i v e n b e f o r e , ( i f n=|x!+1 f 0 :r> < (^undefined otherwise Let i~Q be the program i h 1 3 .13 3.14 D e f i n i t i o n . I f D i s a d e v i c e , then a dev i ce Rec(D) , the r e c o r d i n g v e r s i o n o f D, i s s p e c i f i e d thus ( w r i t i n g R f o r Rec(D) ) : RQ = {< . . . < m k _ 1 , a k _ 1 > , mk> [ fo r each j , 1}= ( D Q X D C ) * X D Q . — j R'p — Dip. R T : x r><*,D T ( x )> . R Q: r>D 0(m). 5c = 2 c For each a eD^, Ra: |->< ,m'> , i> , where D a (m)=. Comparison o f t h i s d e f i n i t i o n w i t h 2 .2 shows tha t < ... ,mk> eRQ i f and on ly i f the re i s some program IT such tha t . . . eC(TT,D) and n A(Zj )=aj f o r a l l j , 00 (undef ined on nonempty s t r i n g s ) . Aux c={A}. A u x A : i x r > < x , i > f o r 1Q2 (undef ined on M):. Chapter I 14 Remark. For any set X, l e t R(X) denote the r e g u l a r languages over X (as a l p h a b e t ) . I t i s easy to show, u s i n g f a m i l a r t e c h n i q u e s , tha t {dom(In1 ^ VT) !M i s a program}=R(A) f o r any f i n i t e se t A. Programs f o r I n 1 ^ are i n t h i s sense d e t e r m i n i s t i c f i n i t e - s t a t e a c c e p t o r s . Programs f o r A u x X I n l ^ are l i k e w i s e n o n d e t e r m i n i s t i c f i n i t e - s t a t e accepto rs i n the sense tha t {L 'L={x ! e dom(Aux X In1 ^ )rr f o r some w62*} and some program ri} i s a l s o R(A) . S i m i l a r l y , A u x X O u t ^ i s a programmable n o n d e t e r m i n i s t i c g e n e r a t o r , and we have {L|L={x!<0,x> 6codom(Aux X Out^ A^ )rr} f o r some program l-,} = R(A) . Chapter I 4 Machines . 15 4.0 D e f i n i t i o n . A machine M comprises the f o l l o w i n g : Mp - an i n d e x i n g f u n c t i o n w i t h Mp(j) a dev ice f o r a l l j 6dom M^ ; M^, M^edom M D - the i n d i c e s a c t i v e f o r input and o u t p u t , r e s p e c t i v e l y . I t i s a l s o convenient t o d e f i n e Mj = dom MD - the index s e t . ~D = X j e j ~ D ^ - t h e u n d e r l y i n g d e v i c e . ~S = X j 6 M K ^ ~ D ^ ^ S _ t h e i n P u t s e t -~T = X j 6M ^ M D ( J ) ) T _ t h e o u t P u t s e t -4.1 D e f i n i t i o n . I f M i s a machine and 17 a program, then the r e l a t i o n computed by 17 on M, R(u,M), i s { 6 M S XMT! (MD)rr(x)=y f o r some x e (M n) s and y e ( M n ) T w i t h x ( j ) = x ( j ) f o r a l l j eM R and y ( j ) = y ( j ) f o r a l l j 6M^}. N o t a t i o n . A machine M i s o r d i n a r i l y t o be s p e c i f i e d by e x h i b i t i n g Mp, s p e c i f y i n g the index set Mj and the f u n c t i o n Mp i m p l i c i t l y . The s e t s M^ and M^ may a l s o be s p e c i f i e d i m p l i c i t l y by r e f e r i n g to dev i ces which are f a c t o r s i n the product M D as a c t i v e f o r input or o u t p u t . The dev i ces I n 1 ^ are a c t i v e f o r input i n a l l machines and none o f I n 1 ^ or Aux i s o therwise a c t i v e f o r i n p u t or o u t p u t . In p a r t i c u l a r Aux i s not a c t i v e f o r i n p u t or output i n any machine. The f o l l o w i n g i s conven ien t . 4.2 D e f i n i t i o n . I f M i s a machine then X^Mg i s M-acceptab le i f and on ly i f there i s a program 77 such tha t X = dom R(77,M). 4.3 D e f i n i t i o n . I f M i s a machine then L(M) = {X'X i s M -acceptab le } . 4.4 D e f i n i t i o n . I f M and N are machines then M < » , « , « > , D o :K>0. D C={L,R,T=} U {T<-b|b 6 B } . Dj j : |-><<[x) , a ' , a y > ,0> where x = [ x ) a ' . D R :r><,0> where y = a ' ( y ] . D T = : < x , a , y>K> « x , a , y > , a > . (DV(T=)=B U {*}). 2 T < _ b : < x , a , y > ! - X < x , b , y > , 0 > . Tur^ ; i s normal l y not a c t i v e f o r input or o u t p u t . The memory element rep resents the s t r i n g xay over B scanned at the i n d i c a t e d occurrence o f a . P o s s i b l y x=a=B, so tha t the scan po in t may be beyond the l e f t end of the s t r i n g . A l s o p o s s i b l y a=y=S, so tha t the scan po in t may be beyond the r i g h t end. The T= command r e p o r t s the symbol (or S) scanned. New i n f o r m a t i o n can be recorded by execut ion o f a T<-b command. In p a r t i c u l a r , execut ion o f 1 or lengthens the s t r i n g . I n i t i a l l y , the s t r i n g i s empty. Execut ion o f L l e a v e s <3,S,y> unchanged, and execut ion o f R l e a v e s unchanged. (You might say the unrecorded par t o f the i n f i n i t e tape i s s l i p p e r y . ) By i t s e l f , Tur v ' can on ly compute two f u n c t i o n s : 0h>0 and the empty f u n c t i o n . I n t e r e s t l i e s i n i t s r o l e i n products such as I n 1 ^ X T u r ^ . 5 .1 D e f i n i t i o n . I f B i s a f i n i t e s e t , a dev i ce P d s ^ , (the pushdown s t o r e dev ice ) i s d e f i n e d thus ( w r i t i n g D f o r P d s ^ ) : DQ=B*, D S=D T=1. D-j-:0 h>3«, D o :X|-»0 (undef ined on B + ) . D c = {^-P} U {P<-b|b 6 B } . D^ _ p:xar> (undef ined on B ) . Chapter I 18 D p < _ b : x h>. Pds v ' i s normal l y not a c t i v e f o r e i t h e r input or o u t p u t . The memory element x , x 6 B , rep resents a pushdown s t o r e whose top i s the r i g h t - h a n d end of x . The command 4-P s i m u l t a n e o u s l y r e p o r t s the symbol on the top o f the s t o r e and pops i t o f f . A d d i t i o n a l elements may be pushed onto the s t o r e by execut ion of a P<-b command. I n i t i a l l y the s t o r e i s empty. 5.2 D e f i n i t i o n . I f B i s a f i n i t e s e t , a d e v i c e S t ^ , (the s t a c k dev ice ) i s d e f i n e d thus ( w r i t i n g D fo r S t ^ ) : DQ = B* X (B U {8}) X B* , D S=D T=1. D T :0r><*,5,5>, DQ:|->0 (undef ined o t h e r w i s e ) . D c = ( L , R , f S,S=} U { S < - b ! b 6 B } . Dj j:r><<[x) ,b,ay>,0> where x=[x)b. D R : < x , a , y > H K < x a , b , (y]> ,0> where y=b(y] . D^ _ g : (-7><, 0> where b eB (undef ined o t h e r w i s e ) . Dg_:|-X,a> where aeBU{!f}. Dg^_ j ):r><,0> (undef ined o t h e r w i s e ) . S t v ; i s normal l y not a c t i v e f o r input or ou tput . The memory element r e p r e s e n t s the s t r i n g xay over B at the i n d i c a t e d occurrence o f a . P o s s i b l y x=a=S, so tha t the scan po in t may be below the bottom of the s t a c k . A l s o p o s s i b l y a=y=S, so tha t the scan po in t may be beyond the top o f the s t a c k . The S= command r e p o r t s the symbol (or X) scanned. A d d i t i o n a l symbols may be pushed onto the s t a c k by execut ion o f a S. Symbols are removed from the top o f the s t a c k by the command, <-S, d e f i n e d o n l y i f memory has the form . Execut ion o f L l e a v e s unchanged and execut ion of R l e a v e s unchanged. Chapter I I 0 I n t r o d u c t i o n . 19 A v a i l a b l e to each s p e c i e s o f marker automaton i s a f i x e d f i n i t e number, say k, o f p e b b l e s . Each head has f r e e access to t h e s e , and may l a y pebbles down upon or remove pebbles from the tape square under s c a n . There i s noth ing t o prevent a head from l e a v i n g a pebble behind as i t moves t o the a d j o i n i n g tape square . N a t u r a l l y , at most k pebbles may appear on the tape at any one t i m e . Marker automata e x h i b i t a c l e a n and l i m i t e d form of w r i t i n g , a tape square be ing m o d i f i e d on ly to the extent o f the presence or absence o f markers . The f a m i l y o f one-way mul t ihead marker automata may be roughly d i v i d e d i n t o two c l a s s e s , those whose i n d i v i d u a l markers are i n d i s t i n g u i s h a b l e from one another and those f o r which each marker may be un ique l y i d e n t i f i e d ; f o r the l a t t e r , we say the markers are d i s t i n g u i s h e d . Fu r ther d i s t i n c t i o n s are based on the number o f markers permi t ted per tape square . The fundamental c h o i c e s a re z e r o , one, and many - ze ro l e a v i n g us w i t h Rosenberg 's one-way mul t ihead f i n i t e automata. The sys temat i c e x p l o r a t i o n o f the taxonomy j u s t o u t l i n e d w i l l beg in i n s e c t i o n 1 of t h i s chapter w i t h the formal d e f i n i t i o n s o f the c l a s s e s o f d e v i c e s made p o s s i b l e by v a r i a t i o n s i n marker s t r u c t u r e and u s e . S e c t i o n s 2 and 3 are devoted to demonstrat ing the computat iona l equ iva lence o f the d e v i c e s enumerated i n s e c t i o n 1. In s e c t i o n 4 , I show t h a t s imple r e s t r i c t i o n s on head movement and pebble use do not s u b s t a n t i a l l y a f f e c t the r e c o g n i t i o n powers o f these d e v i c e s . Consequent ly , we may content o u r s e l v e s w i t h a few s imple types d i f f e r i n g on ly i n programming convenience . Chapter I I 1 P r e l i m i n a r y d e f i n i t i o n s . 20 The f o l l o w i n g two d e f i n i t i o n s g i v e the pr imary forms o f one-way mul t ihead marker automata. A l l f u r t h e r d e f i n i t i o n s w i l l be v a r i a t i o n s on these two themes. 1.0 D e f i n i t i o n . Let A be a f i n i t e s e t , n,k 6 N . Then an n-head one-way i n p u t d e v i c e w i t h k markers , I n l ^ ' 0 ' ^ , i s s p e c i f i e d thus ( w r i t i n g D f o r I n 1 ( A ; n ; k ) ) ; D q = A * X 2 * X N n . An element m of DQ i s denoted < i n p u t , m a r k s , h ^ , . . . , h n > . DS=A*, D T =1. D j i x r X x . y . O , . . . ,0> where y 6 { 0 } * , !y! = !x|. D g K i n p u t , m a r k s , h ^ , . . . ,h n >r>0. D c = {Rj|1r><, 0> i f f h^ where | -m( inputH = t>Q. . .b r , b i6A+{h,H} f o r a l l i . 3 |j : < i n p u t , m a r k s , , h j , . . .>( -><,0> i f f count(marks)N :XK»0 : txK>t+count(x) , t 6 2 . ] T j : <±nput,marks, . . . , h j , . . . > !->< ,0> i f f 1 i f f 1hn>. Dg=A*, D T =1. D-r r> where y 6 { - } * , ! y != ix| . D0:m|->0. D c = {Rj! lf -><, 0> i f f h j<| input| . I j= :mr-> where !~m(input)-{ = b Q . . . b r , b^eA+{h,H} f o r a l l i . 3 |jP :< input ,marks , . . . ,h j , . . .>r><,0> i f f p 6M\{s ! (Eu ,v ) marks=usv, s 6M} & 1 |->< ,0> i f f 1 i f f 1 . Dg=A*, D T =1. D p X p X x . y ^ , . . . ,0> where y 6 { 0 } * , |y! = |x! . D Q :mr>0. Dc=imcA;n;k). (¥a 6 {R,! 1 r > < < i n p u t , u ( i + 1 ) v , . . . , h j , . . .> ,0> i f f count(marks)N :Xh>0 : ( i ) xh> i+count ( x ) . ] T ^ :< input ,marks , . . . , h i , . . . > r > « i n p u t , u ( i - 1 ) v , . . . , h i , . . .> ,0> i f f K h ^ l i n p u t j & ( (Eu ,v ) marks=u( i )v , ! u | = h i - 1 , i > 1 ) . M i = :mr> i f f 1 M ) f ± s s p e c i f i e d thus ( w r i t i n g D fo r p d D I n l ^ A ' n ; M ^ ) : DQ=A* X(M*)* X N n . An element m of DQ i s denoted < i n p u t , m a r k s , h ^ , . . . , h n > . Remark. A marker tape i s a s t r i n g whose components are a l s o s t r i n g s . To denote members o f a set o f t h i s fo rm, I w i l l use <,> to d e l i m i t components, X X X thus a s t r i n g over (M ) i s w r i t t e n .. • , where x i 6 M f o r a l l i . For example {<8>} i s the set c o n s i s t i n g o f the empty s t r i n g and a l l s t r i n g s whose components are the empty s t r i n g . Chapter I I 23 DS=A*, D T=1. D I : x r > < x , y , 0 , . . . , 0 > where y e { « > } * , !y !=!x! D o :mr>0. D c = D m i £ A ; n ; M ) . (¥a e{Rj!1K>«input,uv,... ,hj , . . .> ,0> i f f 1v, !u!=hj-1) (the right hand of x is the top of the. pushdown store). [unpack:(M ) ->P(M) :&r>0 :<&>yr>unpack(y) :yhMp} Uunpack(y), where p 6 M . ] T ^ :< input ,marks , . . . ,h^ , . . .>r><v , . . . , h - , . . .> ,0> i f f K h X ! input i & ( (Eu ,v ) marks=uv, |u|=hj -1, x=[x)p, p 6 M ) . M =^ :mr> i f f 1v, x=[x)p, peM+{*}, !u !=ra(h j ) -1 ) . pdDInl(A;n;M) ^ g n o r f f l a i i y a c t i v e f o r input but not f o r o u t p u t . 1.4 D e f i n i t i o n . Let A and M be f i n i t e s e t s . Let n 6 N . An n-head one-way i n p u t d e v i c e w i t h subsets o f d i s t i n g u i s h e d markers M, s D I n l ^ A ; n ; M ^ , i s s p e c i f i e d thus ( w r i t i n g D fo r s D I n l ^ A ' n ' M ^ ) : DQ=A* XB* X N n where B=P(M). An element m of D Q i s denoted < i n p u t , m a r k s , h ^ , . . . , h n > . DS=A*, D T =1. D j i x h X x j ^ , . . .0> where y 6{D}*, !y!=!x|. D Q : m ^ 0 . D c = {Rj ! 1|->< ,0> i f f h j where (-m(input)H = b0...br, b i 6A+{[-,-{} f o r a l l i . 3 | j p : < i n p u t , m a r k s , . . . , h j , . . . >|-><,0> i f f 1P(M) :*r>D :Sxh>S Uunpack(x) where seP(M).] T j P : < i n p u t . m a r k s , . . . , h j , . . .>r>< ,0> i f f K h ^ j i n p u t ! & ( (Eu ,v ) marks=uRv, !u!=h,-1, peRsM). ~* J — J peMj :mHKm,t> i f f 1Eg :mr>m' where ( i ) m' ( input)=m(input) ( i i ) i f m(marks)=T^ . . . T r then m ' ( m a r k s ) = x 1 . . . x r where f m i n 7L i f T ^ Q 1 1^ - o therwise ( i i i ) ¥ n = 1 m' (h j )=m(hj ) . ( i v ) (¥peP) m ' (S p ) = ( s | ( E T e P ) T>-D, m(marks)=uTv, p=min T, & s 6 T } . (Example. I f m(marks)=uTv, T={3,5} then m'(S3)={3,5} and m'(S5)=0.) Def ine f T : E g - > E g :m->m' where m'=m except tha t ¥ k _ 1 S ^ D ; and fg= Id E . Def ine the f o l l o w i n g programs T -1 I " V Chapter I I 1 0 " i ©No ( ¥ J = I ¥ P E P ) R ; J P ®using(p) p - 1 ^ S p _ 1 U { p } ? S « - { p } 5 I lo: ( ¥ J = 1 ¥ P E P ) r T j P Itransfer^k, ! J i ^transferj(p+1,p) f s p ^ s p \ { P } f s ^ S l \ { p } f S p . ^ S p ^ X C p } |1 3p+1 e s p ?j—>©transferj(p,p+1) 5 Ik e S P Q—>®transf er j (p, k) Chapter I I 27 (vp ep v n = 1) P 6 M , IM .= {-.P+1. ! J ->©1 (¥p eP) us ing (p ) : 0:©<-1 1 0<-P e s k 1 «1: ( ¥ n = 1 -¥p,q eP) t r a n s f e r ^ p,q) = i S q ^ S p U { q } (¥a 6 {I l S|1 E Q :mh>m' where ( i ) m' ( input)=m(input) Chapter I I 28 ( i i ) i f m ( m a r k s ) = b 1 . . . b r then m'(marks)=. . . where ¥ £ = 1 fb± i f b± 6 P 1 \_B otherwise ( i i i ) ¥ n = 1 m' (h j )=m(hj ) . Let f j -z fQzIdg . ( ¥ a e (D c \{| jP l 1a. F i n a l l y ( ¥ n -i ¥ p 6 P ) l e t T i n be the program l M j = A p p l i c a t i o n o f the s i m u l a t i o n theorem completes the p r o o f . 1 2 .1 2 .2 Lemma. p d D I n l ( A ' n ' P ) « s D I n l ( A 5 n ; p ) . P r o o f . Let D=pdDIn1 ^ A ; . n ; P \ E=sDIn1 ^ A ; n 5 p ) . We assume, wi thout l o s s of g e n e r a l i t y , t h a t P = { 1 , . . . , k } . Augment E by k+1 elements o f f i n i t e memory: ( i ) s ^ , s k where dom s ^ t x eP ! |x| , c ^ P , as an unordered set { o ^ , . , . , o } and the o r d e r i n g o f the s t a c k ' s c o n s t i t u e n t s as a s t r i n g c . | . . . c m bound to the elements o f f i n i t e memory s c , s indexed by 1 m the i n d i v i d u a l components o^, c m . Def ine fg:DQ->Eg :m|->m' where ( i ) m ' ( input )=m( input ) ; ( i i ) Let m(marks)=.. .. I f ( ( E i , j ) i^ j x ^ u p v , Xj= u ' p v ' , and p 6 P ) v ( ( E i ) x ^ u p y p w , and p 6 P ) then m'(marks)=S and ¥ k _ 1 m'(s^)=S, o therwise m'(marks) = T .| . . .T p where = u n p a c k ( x i ) and Chapter I I (¥peP) m ' ( s p ) = 29 i f (E j ) 1. . .. . ,, and Xj=upv 8 otherwise [unpack: P*->P(P) :5r>D : px hHp} U unpack(x) , p 6 P ] . ( i i i ) V^ = 1 m' (h j )=m(hj ) . Let f j - :EQ^EQ :mr>m' where m'=m except t h a t ¥^_^ m' ( s i )=X ; and fQ=Id E -Q Def ine the programs I " £s..<-X i l I SNC (••5=1 vP ep) • J 1 >©push.j(p) >®push k (p ) Chapter I I 1 . . . k (¥a 6{I j=!1E, where D and E are dev i ces should be taken to mean D << sDIni(A;n;P) i I t DInt(A;n;P) i I I 2 . 3 F i g u r e . Chapter I I 32 In r e t r o s p e c t i t i s easy to see why memory s t r u c t u r e s f a i l to i n f l u e n c e the computat iona l power o f marker automata. S ince the t o t a l number of a v a i l a b l e pebbles i s f i n i t e , each memory s t r u c t u r e , no matter how complex, can be s imula ted w i t h an element of f i n i t e memory (one f o r each m a r k e r ) . One-way mul t ihead marker automata w i th memory s t r u c t u r e s may t h e r e f o r e be f r e e l y employed f o r reasons o f programming or pedagogica l convenience wi thout f e a r tha t the computat iona l power o f the dev i ce i s be ing compromised or enhanced. Chapter I I 3 The equ iva lence o f un i form and d i s t i n g u i s h e d markers . 33 I next show t h a t the pr imary d i s t i n c t i o n among marker automata, hav ing d i s t i n g u i s h e d pebbles as opposed to u n i f o r m , i s m i s l e a d i n g , s i n c e any dev i ce w i t h d i s t i n g u i s h e d markers may be s imulated by one w i t h un i form markers a t the expense of a modest i n c r e a s e i n the number o f p e b b l e s . 3 .0 Theorem. D I n 1 ( A ; n ; P ^ « I n 1 ( A ; n ; k + 1 5 where k=card P. P r o o f . Let D = D I n 1 ( A 5 n ' P ) , E = I n 1 ( A ; n ; c a r d P + 1 > , P = { p 1 , . . . , p k J . Augment E by a s i n g l e element o f f i n i t e memory, map, whose domain i s { x|xe ( P { 1 , . . . , n } X (P+{-})) , | x ' < (card P)+n}. E keeps a complete record o f the order o f heads and pebbles f o r D. The va lue . . . (a s t r i n g of l e n g t h r over P { 1 , . . . , n } X(P+{ - } ) ) f o r map r e p r e s e n t s a c o n f i g u r a t i o n m of D i n which ( i ) t ^ . . . t i s a subsequence o f -m(marks ) - i n c l u d i n g a l l occurrences o f a c t u a l pebb les ; ( i i ) i f t^ 6 P then i s the set o f heads on the same square as t ^ ; ( i i i ) i f t^=- then i s the set o f a l l heads on some one square wi thout a pebb le ; ( i v ) i < i ' and j e H^, j'eH^' i m p l i e s h j < h j ' j (v) u ! [ = 1 H i = { 1 , . . . , n } ; ( v i ) vr=1 ^. Def ine fg iDg -^Eg :m|->m' where i f !m( input ) ! = !m(marks)! & C¥ N = 1 0 r > < x 0 , H 0 , t 0 > . . - < x r + i > H r + 1 i t r + . , > where ( i ) hinputH = x 0...x r + 1, - ¥ [ + J Xj^eA+d-.Hl ( i i ) vJ+J H i z t j l h j s i , 1) )*->(P{1,.... ,n} X(P+{ - } ) )* :S r>* fselect(w) i f UtU v ti-:Wr>< (^select(w) o therwise uniform: (P+{ - } )* ->2* :&h>* f1(uniform(x)) i f p 6 P :pxr>< LO(uniform(x)) i f p=-*I : -Q~*-Q : m r * m ' w h e r e m'=m except tha t m'(map) = <{ 1 , . . . ,n} , - > ; and f 0 = I d E Q ' Def ine the f o l l o w i n g programs T -' I " $map<-<{1, . . . ,n } ,-> $ 0 : T _ 1 o -©No i &0: Chapter I I i 35 i (*) |same s q u a r e d , j ) -°—^©map<-uv where fo rmer l y map=uv, J 6 H , i 6 H ' i l l j = -i^®map<- (map)<{ j} ,-> |A i l M j = - Q - > ® m a p < - u < H \ { j } , t > < { j } , - > v where fo rmer l y map=uv, j 6H | i 4 <{ j} ,p>v where fo rmer l y map=uv, j 6 H , p 6 P ©0: (*) a l l such nodes itj, 1v h 6X i I ©map<-uv where fo rmer l y map=uv, j 6H ®"o: i t . i J ®map<-uv where fo rmer l y map=uv, j e H , p e p Jo: ( ¥ j = 1 J rMj= i SM.= 0 ->©-: i J I1 &(Eu,v) map= uv, j e H [ ]uv, j e H ®PV Ip k: An a p p l i c a t i o n of the s i m u l a t i o n theorem b r i n g s us to the d e s i r e d r e s u l t . 1 3 .0 Thus d e v i c e s w i t h d i s t i n g u i s h e d markers may be s imulated by a dev i ce w i t h un i form markers a t the expense o f a f i x e d constant i n c r e a s e i n the number o f markers . I t would be i n t e r e s t i n g to know whether t h i s i n c r e a s e i s s u b s t a n t i v e or s imp ly an a r t i f a c t o f the p r o o f , t h a t i s , whether there e x i s t s a language which i s D I n 1 ^ A ; n ; M ^ - a c c e p t a b l e but not I n 1 ^ A ; n ; k ^ - a c c e p t a b l e where k=card M. Though I cannot answer t h i s q u e s t i o n , one c a n , i n some c a s e s , o b t a i n from a program {"[ f o r D I n 1 ^ A ; n ' P ^ an e q u i v a l e n t program V f o r i n 1 ^ A ; n ' k ^ where k=card P. 3 -1 Theorem. Let f l be a program f o r D=DIn1( A 5 n 5 p ) such tha t i f Chapter I I 37 ... e C(i~[,D), z0=ITs, (Ex) m 0 =Dj(x) , x 6 A* then ¥ [ _ 0 m i ( h 1 ) > . . . > m i ( h n ) . Then there e x i s t s a program V f o r E = I n 1 ^ A ; n ; k ^ , k=card P such tha t Drj P r o o f . (Sketch) A c a r e f u l study o f the proof tha t D I n 1 ^ A ; n 5 p ) « I n 1 ( A ; n ; ( c a r d P)+1) w i l l r e v e a l t n a t t n e a d d i t i o n a l uni form pebble i s on ly r e q u i r e d to d e t e c t head c o i n c i d e n c e - i n t h i s manner the order o f the heads on the input tape i s known to I n 1 , p e r m i t t i n g i t to i n f e r the order and d i s t r i b u t i o n o f the d i s t i n g u i s h e d markers o f DIn1, i n f o r m a t i o n tha t i s c r u c i a l to the s u c c e s s f u l s i m u l a t i o n o f D I n 1 ^ A ; n ; P ^ by I n 1 ( A ; n ; ( c a r d p ) + 1 ) . S ince i n t h i s case the o r d e r i n g of the heads o f DIn1 i s known a p r i o r i the e x t r a pebble may be d ispensed w i t h . The essence o f the c o n s t r u c t i o n i s the augmentation o f E w i t h an element ft of f i n i t e memory, map, whose domain i s {x!x 6 ( P { 1 , . . . ,n} X (P+{ - } ) ) , jx|<(card P)+n}. The va lue o f map, . . - r e p r e s e n t s a c o n f i g u r a t i o n m of D i n which ( i ) t ^ . . . t r i s a subsequence of -m(marks ) - i n c l u d i n g a l l occur rences o f a c t u a l pebb les ; ( i i ) i f t^ eP then i s the set o f heads on the same square as t ^ ; ( i i i ) i f t^=- then i s the set o f heads which l i e between a p a i r o f pebbles p and p ' - p to the l e f t and p ' to the r i g h t - w i t h no pebble p" between the two, or H^ i s the set of heads l e f t [or r i g h t ] of a l l pebb les . I f j j j ' e t L then i t i s not n e c e s s a r i l y t r u e tha t h ^ h ^ ' . To i l l u s t r a t e , the map i n d i c a t e s tha t HQ i s the set o f heads scanning marker p, H^ the set o f heads l y i n g somewhere between p and p ' , and H 2 the set o f heads scanning p ' . ( i v ) i < i ' , j e H i ? j ' e H ^ ' i m p l i e s h i < h i ' j (v) Ur=1 H i = { 1 , . . . , n } ; ( v i ) V[ = 1 >.. The i n i t i a l v a l u e o f map i s < { 1 , . . . , n } , - > . The remainder o f the proof i s s i m i l a r to tha t o f (3 .0 ) and may e a s i l y be g i v e n . 1 3 .1 Chapter I I 38 Remark. A s i m i l a r r e s u l t , w i t h a n e a r l y i d e n t i c a l p r o o f , may be cas t f o r D=Aux X D I n 1 ( A ; n 5 p ) and E=Aux X I n 1 ( A ; n 5 k ) , k=card P. Proceeding i n the reverse d i r e c t i o n , the next two lemmas, by way o f s i n - | ( A ; n ; k ) a g a n i n t e r m e d i a r y , prove tha t In1 ^ A ; n ' k ^ « D I n 1 ^ A ; n ; P ^ where (card P)=k. 3.2 Lemma. i n 1 ( A ; n ; k ) « s I n 1 ( A 5 n ; k ) . P r o o f . Let D = I n 1 ^ A ; n ; k ) , E = s l n 1 ( A ; n ; k ^ . Let f Q = I d D n and f I = f 0 = I d Def ine the f o l l o w i n g programs T _ T _ 1 I - 1 o -®"o: « n T-•J-1 ij • I M j = 1° (Va eDc\{jj! 1 Ta = [T D > a An appeal to the s i m u l a t i o n theorem completes the p r o o f . I 3.2 3.3 Lemma. s I n 1 ( A ; n ; k ) « p d D I n l ( A ' n 5 p ) where (card P)=k. P r o o f . Let D = s l n 1 ( A ' n ' k ) , E = p d D I n 1 ^ A ; n ; P ^ . We assume, wi thout l o s s o f g e n e r a l i t y , tha t P = { 1 , . . . , k } . Augment E by a s i n g l e element o f f i n i t e memory, a v a i l a b l e , whose domain i s P ( P ) . Def ine f Q : R e c ( D ) Q - > E Q :r>m' where m' ( input )=m( input ) , im' (marks) ! = |m( input ) ! , m'(marks) 6{<->}*, ¥ j j = 1 m' (h j )=m(hj ) , m ' ( a v a i l a b l e ) = P . Chapter I I 3 : « m 0 , a 0 > — < m r , a r > , m r + 1 > h> i f fg ( . . .,m r )=m then ( i ) i f a r e{Ij=|1v where |u!=m(hj ) -1 , m(marks)=uv, p=min (m(ava i lab le ) ) , m ' (ava i lab le )=m(ava i lab le )\ {p } ( i i i ) i f ar=Tj, 1v where |u|=m(hj)-1, m(marks)=uv, x=[x)p, p 6 P , m ' ( a v a i l a b l e ) = m ( a v a i l a b l e ) U{p} ( i v ) i f a r =R-j , 1Eg :m|->m' where m'=m except tha t m ' ( a v a i l a b l e ) = P ; and fg=Idg . Def ine the f o l l o w i n g programs T -1 I " I ©"avai lable^-P 1 ® 0 : T 1 0 -I ©No 1 lo: 1 0 : ® < ®M.: = - 1 1 |{1,...,k} Chapter I I ®"available<-j a v a i l a b l e \ { k } 5 An appeal to the s i m u l a t i o n theorem completes the p r o o f . 1 3.3 F i g u r e 3-4 summarizes lemmas 3.0, 3.2 and 3.3. Chapter I I 4 D I n l ( A ; n ; M ) i I t I n 1 ( A ; n ; ( c a r d M)+1) i I v s I n 1 ( A ; n ; ( c a r d M)+1) i I t p d D I n 1 ( A 5 n ; M + { P } ) 3.4 F i g u r e The r e s u l t s below f o l l o w immediate ly from lemmas 2 .0 - 2 . 2 , 3 . 0 , 3 .2 and 3 - 3 . For b r e v i t y l e t D k > E n > k 6 { D I n 1 ( A i n > M k > , s D I n l ( A ' n ' M k ) , , p d D I n 1 ( A ; n ; M K ) > I n 1 ( A ; n ; k ) ( s I n 1 ( A ; n ; k ) } w h e r e MQ=[]. H ^ . , 0 { k } . 3 .5 Theorem. For n 6 N + U k = Q L ( D n > k ) = u k = 0 L ( E n > k ) . 3 .6 C o r o l l a r y . l £ = 1 U~ = 0 L ( D n > k ) = IJ~ = 1 fcCE^). 3 .7 Theorem. For n 6 N + U k = 0 t ( A u x X D n k ) = u f l 0 L ( A u x X E n > k ) . 3 . 8 C o r o l l a r y . U* = 1 U ^ 0 L ( A u x X D n > k ) = U „ = 1 U ^ Q L ( A u x X E n > k ) . Chapter I I 4 Normal fo rms. 42 The f o l l o w i n g d e v i c e s may be thought o f as normal forms f o r the two pr imary c l a s s e s o f marker automata. 4 .0 D e f i n i t i o n . Let A and P be f i n i t e s e t s . Let n G N . Then an ordered n-head one-way i n p u t dev i ce w i t h d i s t i n g u i s h e d markers P, ordered D I n 1 ^ A ' n ' P \ i s s p e c i f i e d thus ( w r i t i n g D f o r ordered D I n 1 ^ A ' n , P ^ ) : (Vi e { Q , S , T , I , 0 , C } ) D j = D I n l { A 5 n ; p > . (Va eD c\{Rj|1'r ->< , 0 > i f f 0 < h j < ! i n p u t ! & V r < j h j < h r . ordered D I n 1 ^ A ' n ' P ^ i s no rmal l y a c t i v e f o r i n p u t , not f o r o u t p u t . ordered D I n 1 ^ A ; n ; P ^ i s i d e n t i c a l to D I n 1 ^ A ; n ; P ^ save f o r the r e s t r i c t i o n tha t no head may over take and pass another . I t may be f u r t h e r r e s t r i c t e d by i n s i s t i n g t h a t t e r m i n a t i n g computat ions end w i t h a l l heads scanning the r i g h t end marker and the tape c l e a n o f pebb les . More f o r m a l l y I o f f e r : 4 .1 D e f i n i t i o n . Let A and P be f i n i t e s e t s . Let n 6 N . Then a t i d y ordered n-head one-way i n p u t dev i ce w i t h d i s t i n g u i s h e d markers P, t i d y ordered D I n 1 ( A ; n ; P ) ? i s s p e c i f i e d thus ( w r i t i n g D f o r t i d y ordered D I n 1 ^ A ; n ; P ^ ) : (Vi 6 { Q , S , T , I , C } ) D ± = ordered D I n l { A ; n 5 P ) . D Q : < i n p u t , m a r k s , h 1 , h n > r > 0 i f f marks 6{ - }* & v"_1 h j=| input !+1 . ( V a e D c ) D a =ordered D I n 1 a A ; n 5 P ) . t i d y ordered D I n 1 ^ A ; n ; P ^ i s normal l y a c t i v e f o r i n p u t , not f o r o u t p u t . A s i m i l a r development i s p o s s i b l e f o r I n 1 ^ A ; n ' k ^ . 4 . 2 D e f i n i t i o n . Let A be a f i n i t e s e t . Let n , k 6 N . Then an ordered n-head one-way i n p u t d e v i c e w i t h k markers , ordered I n 1 ^ A ' n ' k ^ , i s s p e c i f i e d thus ( w r i t i n g D f o r ordered I n 1 ( A 5 n 5 k ) ) : (Vi e { Q , S , T , I , 0 , C } ) D± = I n l { A ; n ; k ) . Chapter I I 43 (Va eD c \ { R j i K j < n } ) D a = I n 1 a A ; n 5 k ) . V j = 1 R j : < i n p u t , m a r k s , . . . , h j , . . . > r > < < i n p u t , m a r k s , . . . , h j+1 , . . .>,0> i f f 0 r > 0 i f f marks e {0}* & V n = 1 h j = ! i n p u t ! + 1 . (VaeD c) D a = ordered I n 1 a A 5 n ; k ) . t i d y ordered i n 1 ^ A ' n ' k ^ i s normal l y a c t i v e f o r i n p u t , not f o r o u t p u t . Remark. The ordered v e r s i o n s o f DIn1 and In1 are analogous to the normal mul t ihead w r i t i n g f i n i t e automata o f Sudborough [Sudborough 71] w h i l e the t i d y ordered d e v i c e s are the marker automata e q u i v a l e n t o f h i s type 2 mul t ihead w r i t i n g f i n i t e automata. The o b j e c t i v e o f lemmas 4.4 - 4 .7 i s to demonstrate tha t any language recogn ized by DIn1 v ' ' J i s accepted by the dev i ces o f 4.0 - 4.3. I beg in by showing tha t at the expense of a s i n g l e a d d i t i o n a l pebble any f u n c t i o n computable by DIn1 may be computed by an e q u i v a l e n t dev i ce whose heads never c r o s s . 4.4 Lemma. D I n 1 ^ A ; n ; M ^ « ordered D I n 1 ( A ; n ; P ^ where card P = (card M)+1. P r o o f . Let D = D I n 1 ( A ; n ; M ) , E=ordered D I n 1 ( A 5 n ; P ) where A+{|-,-|} = { a 0 , . . . , a r } , M={ m1>•••>ms) a n d P=M+{!}. Augment E by n+1 elements o f f i n i t e memory H i , . . . , H n where V " = 1 dom ^ = { 1 , 2 , . . . ^ } ( the i n t e r p r e t a t i o n be ing tha t i f H^=j then head^^ o f dev i ce E i s s i m u l a t i n g the a c t i o n s of headj o f d e v i c e D ) , and temporary , whose domain i s { 0 , 1 , . . . , n } . Device E i s s imply D w i t h the r e s t r i c t i o n tha t the heads o f E must never c r o s s ; head^ i s always a t l e a s t as f a r down the tape as head^ + ^ f o r i = 1 , n - 1 . E s i m u l a t e s D by u s i n g head^ to mimic the a c t i o n s o f the l e a d i n g head o f Chapter I I 44 D, h e a d n t o mimic the a c t i o n s o f the t r a i l i n g head o f D. When head^^ and h e a d j , i < j o f E, s i m u l a t i n g head^ ' and headj ' of D r e s p e c t i v e l y , are about to c r o s s ( tha t i s , headj i s about to over take head^) E in te rchanges the f u n c t i o n s o f the two, head^ t h e r e a f t e r s i m u l a t i n g head, : ' and head^ s i m u l a t i n g h e a d . : ' . E r e q u i r e s the e x t r a pebble to d e t e c t c r o s s i n g p o i n t s ; i t aan not r e l i a b l y depend on another pebble be ing f r e e s i n c e a l l o f the o thers may be i n a c c e s s i b l e . To c o n s t r u c t the s i m u l a t i o n d e f i n e fg.DQ->EQ :mh>m' where: (a) m' ( input )=m( input ) , m'(marks)=m(marks), m'(temporary) = 0 . (b) Let p be the pe rmuta t ion , p : { 1 , . . . , n } - > { 1 , . . . , n } de f ined by ( i ) m ( h p ( 1 ) ) > m ( h p ( 2 ) ) > . . . > m ( h p ( n ) ) and ( i i ) m ( n p ( i ) ) = m ( h p ( i + 1 ) ) i m p l i e s p ( i ) < p ( i + 1 ) . Then ¥ ? = 1 m ' ( h i ) = m ( h p ( i ) ) , m ' d L ^ p U ) . Example. Let m= 6 D I n 1 ^ A 5 4 ; M ) then f Q (m) = < x , y , 5 , 3 , 3 , 0 , H - j ,H 2 ,H2,Hi|,temporary> where =2, H 2=3, H3 = i*> H4=1 » temporary=0. Def ine f T :EQ->EQ :mr>m' where m'=m except tha t ¥"_^ m'(H^) = i ; and f 0 = I d E Q -Def ine the f o l l o w i n g programs: T -1 I " IH.,<- 1 ®"o: 1 o -©No i Id: Chapter I I ¥ j _ i l e t s i m u l a t i n g ( j ) be the program i 1 : ® < — i — S H 1 = J , 1 |{1, . . . ,n}\{ j } n - 1 : © <— - .—SH 1 J i n - i j {1 , . . . , n }\ { j } H - 1 = | { 1 , — ,n}\{ j} n:®<- •—IH = J n Remark, s i m u l a t i n g ( j ) r e t u r n s the index of the head o f E tha t s i m u l a t i n g the a c t i o n s o f headj o f D. « 5 . i > r i , . -s i m u l a t i n g ( j ) ¥p eM) T. n = s i m u l a t i n g ( j ) s i m u l a t i n g ( j ) Chapter II ( V n - i ) . 'j = 1 ' 1 M simulating(j) -:®4 Vj_2 l e t s a m e square(i,j) be the program I s e e s ( i , j ) I l i = i 1 I - i *1 i-1 1 V j _ 2 s e e s ( i , j ) i s the program . © < — j — I M , : J i ! i 1 |M+{-} l T . i J I-i. m1 jM+{-}\{m.,} 1 m V n _2 l e t l e a s t index(j) be 1:®<—Q—Isame square(1,j) j-1:®<—Q—Isame square(j-1,j) Chapter I I 1-1 ( ¥j= 2 s w a p ( i , j ) = i ^temporary*-temporary &temporary4- 0 !(): R -j ® <—=j—Is imul at i n g (j) l e a s t index ( 2)I swap(1,2)© swap(1 ,n)I I l e a s t index(n) n-1 K-1 47 Iswap(n -1,n) l R n 8 A p p l i c a t i o n o f the s i m u l a t i o n theorem completes the p r o o f , i 4 .4 4 . 5 Lemma, ordered D I n 1 ^ A ; n ; P ^ << t i d y ordered D I n 1 ^ A ' n ; P ^ . P r o o f . Let D=ordered D I n 1 ^ A ' n ; P \ E=tidy ordered D I n 1 ^ A ; n ' P ^ and assume that P={p-|,. . . , p k J . Augment E by one element o f f i n i t e memory, a v a i l a b l e , whose domain i s P ( P ) . Const ruc t a s i m u l a t i o n by d e f i n i n g fQ:DQ->E n :m|->m' where i f |m(input)!=!m(marks)! & (V n = 1 m(hj)nT where m'=m except tha t m ' ( a v a i l a b l e ) = P . f 0 : EQ ->Eg :mr>m' where m'=m except tha t V n _ 1 m ' ( h . ) = i m ' ( i n p u t ) im ' (marks ) != im(marks ) ! , m'(marks) 6 { - } . Def ine the f o l l o w i n g programs T -' I " I ©"available^- P 0 = V<—ATfFT Kt<—c ?i„= (Va 6 { R j ! K j < n - 1 } U {Ij=.1 E 0 by Chapter I I 50 m :mr>m' where m' ( input )=m( input ) , m'(marks)=m(marks), ¥ j _ 1 m' (h j )=m(hj ) , x fO i f m(h n)=0 v ( ( E u , v ) , u e{-}* m(marks)=uv, |u|=m(h n)-1) ( c lean) =< " n 1.1 o therwise f I : - Q ^ - Q : m r > m ' where m'=m except tha t m' (c lean) =0, f 0 : E . Q ^ Q , f m i f m(clean)=0 & ( ¥ n , m(h .) = |m(input)|+1) :m|-> < j - 1 j (^undefined otherwise Def ine the f o l l o w i n g programs T -1 I " I Iclean<- 0 i 0?aeg c\{Rn}) Ta = T^.a Chapter I I 51 A p p l i c a t i o n o f the s i m u l a t i o n theorem completes the p roo f . 1 4 .7 4 . 8 Lemma, ordered I n 1 ( A : n : k ) « i n 1 ( A ; n ; k + 1 ) e P r o o f . Let D=ordered I n 1 ^ A ' n ! k ^ , E = I n 1 ^ A ; n ; k + 1 ^ . Augment E by one element o f f i n i t e memory, c o u n t e r , whose domain i s { 0 , 1 , . . . , k } . Def ine f Q :DQ->Eg :mr>m' where m' ( input )=m( input ) , m'(marks)=m(marks), Vn_1 m ' ( h i ) = m ( h i ) , m'(counter)=min{count(m(marks)) ,k} [count:2*->N :*r>0 :tx|->t+count(x) where t e { 0 , 1 } ] . f I = f O = I d E Q ' Def ine the f o l l o w i n g programs _ T-I - 1 o -I ©No i lo: (¥aeD c \ ( { R j | 2 < j < n } U{|j|1*n;k+1) i I v I n 1 ( A ; n ; k + 2 ) 4.9 F i g u r e Chapter I I I 0 I n t r o d u c t i o n . 54 O n e - l e t t e r languages are the i d e a l t e s t i n g ground f o r determin ing the advantages con fe r red by the l i m i t e d w r i t i n g a b i l i t i e s o f one-way mul t ihead marker automata. S ince the sentences o f a s i n g l e - l e t t e r language have no i n t e r n a l f e a t u r e s t h a t would a s s i s t i n t h e i r a n a l y s i s , we are assured tha t the r e c o g n i t i o n o f a p a r t i c u l a r language not accepted by other s t r u c t u r a l l y s i m i l a r dev i ces i s due s o l e l y to the use of markers . I t i s a l s o u s e f u l to app ly one-way mul t ihead marker automata to o n e - l e t t e r languages accepted by d e v i c e s which are g e n e r a l i z a t i o n s o f , and t h e r e f o r e i n t u i t i v e l y more powerful t h a n , one-way mul t ihead marker automata. To t h i s end I w i l l prove t h a t a number o f o n e - l e t t e r languages recogn ized by one-way mul t ihead w r i t i n g f i n i t e automata are a l s o accepted by one-way mul t ihead marker automata, thereby demonstrat ing t h a t , f o r these languages at l e a s t , the a b i l i t y to w r i t e a r b i t r a r i l y i s not r e q u i r e d . I beg in i n s e c t i o n 1 by showing tha t the languages L k = { 0 U ; i n 6 N } (k a f i x e d i n t e g e r >2) proved by Sudborough [Sudborough 71] to be acceptab le by a n o n d e t e r m i n i s t i c one-way 2-head w r i t i n g f i n i t e automaton, are Aux X In1 ' 2 ' k ^ - a c c e p t a b l e . The s i m p l e s t o f t h e s e , L g , be ing i n p a r t i c u l a r I n 1 u ' - a c c e p t a b l e . Not a s i n g l e member of t h i s c l a s s i s recogn ized by any n o n d e t e r m i n i s t i c one-way mul t ihead f i n i t e automaton [Rosenberg 6 4 ] , n o n d e t e r m i n i s t i c one-way mul t ihead pushdown automaton [ H a r r i s o n and I b a r r a 68] or any d e t e r m i n i s t i c bounded r e v e r s a l mul t ihead f i n i t e automaton [Sudborough 7 4 ] . In a d d i t i o n , i s not recognized by any n o n d e t e r m i n i s t i c one-way mul t ihead s tack automaton [ G i u l i a n o 7 0 ] . These languages are g e n e r a l i z e d i n s e c t i o n 2 to L p ( x ) = { 0 p ^ n ^ | n e N } , p(x) a po lynomia l w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s , where I show that L p ( x ) i s In1 ' k ' k - ^ - a c c e p t a b l e , k be ing the degree of p ( x ) . I t f o l l o w s there e x i s t d e t e r m i n i s t i c marker automata languages not recognized by any n o n d e t e r m i n i s t i c one-way mul t ihead f i n i t e automaton [Rosenberg 6 4 ] , n o n d e t e r m i n i s t i c one-way mul t ihead pushdown automaton [Har r i son and I b a r r a 6 8 ] , d e t e r m i n i s t i c bounded r e v e r s a l mul t ihead f i n i t e automaton [Sudborough 74] or n o n d e t e r m i n i s t i c one-way mul t ihead s tack automaton [ G i u l i a n o 7 0 ] . S e c t i o n 3 e x h i b i t s a d i f f e r e n t c l a s s o f o n e - l e t t e r languages , c h a r a c t e r i z e d by constant l i n e a r d i f f e r e n c e e q u a t i o n s , tha t are a l s o Chapter I I I 55 d e t e r m i n i s t i c a l l y a c c e p t a b l e , u s i n g a t most 2 pebb les . Desp i te t h e i r resemblance to the languages o f s e c t i o n 2 , there are members o f t h i s c l a s s not generable by any p o l y n o m i a l , p rov ing tha t a complete c h a r a c t e r i z a t i o n o f the o n e - l e t t e r languages recogn i zed by one-way mul t ihead marker automata can not r e s t upon the po lynomia l languages a l o n e . Chapter I I I 1 N o n d e t e r m i n i s t i c o n e - l e t t e r languages. 56 2 1.0 Theorem. The language L={0^ n ^|neN+} i s i n i ( { 0 } ; 2 ; 1 ) (hence Aux X I n 1 ( { 0 } > 2 > 1 > ) - a c c e p t a b l e . Proof Let D = I n 1 ^ 0 } ; 2 ; 1 ^ and l e t fT be the program z:advance where advance i s the subprogram •2 f R 1 I We a s s e r t tha t dom(Dri) = {0^ n '|neN+}. Observe tha t the d i s t a n c e between the two heads i s always odd, i n c r e a s i n g by two f o r each c y c l e o f the loop c o n t a i n i n g nodes z and z'. I t i s easy to prove by i n d u c t i o n on n , the number o f occur rences o f z i n .. . e C(fT,D), tha t n+1 n m'(h.,)=(J 2 j -1)+1 and m'(h2) = ()" 2 j - 1 ) + 1, ~J=1 ~j=1 consequent ly m'(h 1)=(n+1) 2+1 and m'(h 2 )=n 2 +1. I f the l e n g t h o f the input s t r i n g i s a p e r f e c t square then headj w i l l f i n d i t s e l f scanning the r i g h t Chapter I I I 57 endmarker and by c o n s t r u c t i o n o f IT, h a l t , o therwise i t w i l l be fo rced o f f the end of the t a p e , i 1.0 We can now show t h a t one-way mul t ihead marker automata are s t r i c t l y more powerfu l than one-way mul t ihead f i n i t e automata. ft 1.1 Theorem. [ H a r r i s o n and I b a r r a 68] Let a eA be g i v e n . I f L e f a ) i s recogn i zed by A u x X I n 1 ^ A ' n ^ X P d s ^ then L i s a r e g u l a r language. ft I b a r r a ' s proof proceeds by demonstrat ing tha t L<={a} i s A u x X I n 1 ^ A ' n ^ X P d s ^ - a c c e p t a b l e i f and on ly i f L i s s e m i l i n e a r . S ince a l l s e m i l i n e a r languages over a o n e - l e t t e r a lphabet are r e g u l a r the r e s u l t f o l l o w s . Let L^{a}* be g i v e n , fT a program f o r machine M = A u x X I n 1 ^ A ' n ^ such tha t L=dom R(ff ,M). I t f o l l o w s tha t IT i s a program f o r A u x X I n 1 ( A ; n ) X P d s ( B ) i m p l y i n g 1.2 Theorem. I f L<={a}* i s recognized by A u x X I n 1 ^ A ' n ^ then L i s r e g u l a r . 1.3 C o r o l l a r y . ¥n>2, ¥k>1, L ( I n 1 ( A ; n ) ) ( _ L ( l n 1 ( A 5 n 5 k ) ) and L(Aux X I n 1 ( A ' n ) ) c=L(Aux X I n 1 ( A 5 n 5 k ) ) . P r o o f . I n c l u s i o n i n both cases f o l l o w s immediate ly from the d e f i n i t i o n 2 o f I n 1 ( A ; n ; k ) . Let a e A be g i v e n . S ince L = { a ( n ) in 6N + } e L ( I n 1 ( A ; 2 ; 1 h <= L ( I n 1 ( A ; n ; k ) )<=L(Aux X I n 1 ( A ; n ; k ) ) i s not recogn ized by A u x X I n 1 ( A ; n ) f o r any n>2, the i n c l u s i o n s are proper , i 1-3 ( A • n • \c) I t a l s o f o l l o w s tha t there are languages which are I n 1 v ' ' J [Aux X I n 1 ( A ; n ! k ) ] - a c c e p t a b l e , n>2, k>1 which are not Aux X I n 1 ( A ; m ) X P d s ( B ) - a c c e p t a b l e f o r any m or B. I t i s easy to c o n s t r u c t a program f o r I n 1 ^ X S t ^ which accepts {0^ n ^ i n e N + } . However, G i u l i a n o has proven tha t L = { 0 ( n ) i n 6 N + } i s not A u x X I n 1 ( A ) X S t ( B ) - a c c e p t a b l e [ G i u l i a n o 7 0 ] . The Chapter I I I 58 r e s u l t s which f o l l o w prove tha t L i s both Aux X In1 ; 2 ; 3 ) a n ( j I n 1 v l J , J ' - a c c e p t a b l e . Consequently there e x i s t languages recognized by a d e t e r m i n i s t i c one-way 3 -head 2-marker automaton which are not recognized by any one-way n o n d e t e r m i n i s t i c s t a c k automaton. Sudborough [Sudborough 71] a l s o demonstrates tha t {0^ n 'ineN +} i s a c c e p t a b l e by a n o n d e t e r m i n i s t i c 2-head w r i t i n g f i n i t e automaton and remarks tha t the argument may be e a s i l y g e n e r a l i z e d to show that f o r any k 6 N + / ks L k={Cr ; | n e N } i s acceptab le by a n o n d e t e r m i n i s t i c 2-head w r i t i n g f i n i t e automaton. A s i m i l a r argument may be employed to show t h a t L k i s acceptab le by Aux X i n 1 ( { 0 } ; 2 ; k ) # 1.4 Theorem. F i x k 6 N + . Then the language L k = { 0 ( n MneN +} i s Aux X I n 1 ( * ° * ; 2 ; k ) - a c c e p t a b l e . P r o o f . (Sketch) S ince s D I n 1 ^ A ; n ; P ^ « D I n 1 ^ A ; n ; P \ i t i s s u f f i c i e n t by theorem I I . 3 . 1 to p rov ide a program nk f o r D=Aux X s D I n l ( A ; n , P ) w n e r e c a r d p=k, P = { P l , . . . >Pk_i »'•) > such t h a t i n a l l computat ions by f l on D ( a c c e p t i n g or o therwise ) the heads never c r o s s . The a l g o r i t h m r e s t s upon the o b s e r v a t i o n made by Sudborough tha t there are n s t r i n g s x 6 ( 0 , 1 ) of l e n g t h n which have one and on ly one occurrence o f the symbol 1. I t f o l l o w s tha t there are n tapes o f l e n g t h n w i t h k -1 # t r a c k s such tha t each t r a c k c o n t a i n s a s t r i n g x e { 0 , 1 } o f l e n g t h n w i t h p r e c i s e l y one occurrence o f the symbol 1. By forming between two heads each o f these t a p e s , a dev i ce can measure whether the l e n g t h i s o f n k , n 6 N + . The l e n g t h o f the i n i t i a l s t r i n g between the two heads i s chosen by c o n s u l t i n g an Aux t a p e . An a l t e r n a t i v e po in t o f v iew , b e t t e r s u i t e d to s D I n l , i s to t h i n k o f the k -1 d i s t i n g u i s h e d markers l y i n g between the two heads as p l a c e h o l d e r s i n the e x p r e s s i o n o f a number i n base n , count ing from zero to n k _ ^ - 1 i n c l u s i v e w i t h the p o s i t i o n o f p^ r e p r e s e n t i n g the l e a s t s i g n i f i c a n t d i g i t , P 2 the next l e a s t s i g n i f i c a n t d i g i t and so on . Augment D w i t h an element of f i n i t e memory, t , whose domain i s P{p- j , . . . , P k _ 1}. n k i s the program Chapter I I I "guess .1*1' 1 f t 2 P l v ?v 2P k-1 J -^.©"finished where guess i s the program iA r^T^>©R 1 i 1 1 and f i n i s h e d i s the program i 1 :©<_J—| P i e M i k i « — 1 — f p 2 e M i lo 1 1 ^ - f P k - i e M i lo Jo: Chapter I I I and advance i s the program and r e s e t i s the program I> 6 M 2 1-c k u p l putdown®" Chapter I I I and p ickup i s the program ® t < - t U {p2} lo l t < ^ t u { p k _ 1 } Chapter I I I and putdown i s the program I p-i e t o f v 2 p 1 ] * P 2 e t o t / fPk -1 e t f * 2 P k - 1 and V^_2 move(p^) i s the program / ? P i e M 2 .-2Pi f t i P i I >lu: k -1 and increment(p^) i s the program i IR. i i j R 2 @ < _ L l p.eM 2 o IT. I IR. ft IPJ Chapter I I I i 1.4 63 1.5 Example. The diagram below i l l u s t r a t e s the f i r s t few s teps i n the acceptance of 0 ( 3 ) eLg by running on Aux X s D I n l ( { 0 } ; 2 ; P ) . The numerals " 1 " and " 2 " represent heads 1 and 2 r e s p e c t i v e l y and the symbols " a " and " b " represent the pebbles p 1 and p 2 mentioned i n theorem 1 . 4 . count H 0 0 0 0 0 0 0 0 0 0 o o n 0 0 1 2 00 2 a h 1 1 01 2 b a 1 i '02 2 b 1 a ! 10 2 a b 1 i 11 • • • 2 a b 1 i E n t r i e s i n the column "count" g i v e the r e l a t i v e p o s i t i o n s ( w i t h i n the tape segment o f l e n g t h n bracketed by the two heads) of the markers p 2 P i ( i n that order ) when the node " f i n i s h e d " i s reached . Regarded as a number t w r i t t e n i n base n , each "count" ent ry a l s o s p e c i f i e s the p o s i t i o n of the l e a d i n g head as n*(t+1). From t h i s , we can aga in see the s u i t a b i l i t y o f ["1^ .: i f i t h a l t s , the l a s t "count" ent ry w i l l have shown p^=p 2=..•=Pj c_i=n-1, r e p r e s e n t i n g n k - 1 - 1 i n base n and s p e c i f y i n g the l e a d i n g head p o s i t i o n (on the l a s t 0) as n k . Chapter I I I 64 2 D e t e r m i n i s t i c o n e - l e t t e r languages. The program g i ven w i t h theorem 1.4 may, wi thout d i f f i c u l t y , be r e w r i t t e n t o accept { C r a n ^ n 6 N + } f o r c o n s t a n t s a , k 6 N + . From t h e r e i t i s a s t r a i g h t f o r w a r d e x t e n s i o n to c o n s t r u c t a program f o r Aux X In1 >2>k) to recogn i ze { 0 ^ n ^ ! n eN +} where p(x) = a k x k + a K_.|X K~ 1 + ... + a^x + a.Q i s g i ven f o r c o n s t a n t s k 6 N + , a Q , a ^ , . . . , a k eN. (Paste t o g e t h e r , i n s u c c e s s i o n , programs f o r the r e c o g n i t i o n o f ( o ' a j n ^ | n eK +}, j = 0 , . . . , k , i n s e r t i n g at each j u n c t i o n the a p p r o p r i a t e i n i t i a l i z a t i o n s . ) The f o l l o w i n g development shows tha t i f p(x) i s a po lynomia l o f degree k>0 w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s , then i t i s p o s s i b l e to to compute {O p^ n^|neN} d e t e r m i n i s t i c a l l y a t the expense of i n c r e a s i n g the number of heads to k (but w i t h one l e s s pebb le , on l y k - 1 ) . A s i m i l a r r e s u l t i s c i t e d by Sudborough [Sudborough 76] f o r mul t ihead w r i t i n g f i n i t e automata f o r which he c l a i m s , but does not prove , tha t Lm={Cr Mn eN } f o r m>1 i s recogn ized by a d e t e r m i n i s t i c m-headed w r i t i n g f i n i t e automaton. The arguments here are based upon an a n a l y s i s o f the d i f f e r e n c e t r i a n g l e s ( t a b l e s ) of po lynomia ls w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s . Perhaps t h i s i s the approach Sudborough had i n mind. 2 .0 D e f i n i t i o n . Let X={x n}^.Q be any sequence o f r e a l numbers. The backward d i f f e r e n c e o p e r a t o r , denoted by V, i s d e f i n e d by ( V X ) n = x n - x n _ ^ . I n t e g r a l powers o f the operator are d e f i n e d i n d u c t i v e l y by the r e l a t i o n V k X = V ( V k - 1 X ) , k = 2 , 3 , . . . • I t i s a l s o convenient to s p e c i f y ( V ° X ) n = x n . The v a l u e s o f s u c c e s s i v e powers o f V are c o n v e n i e n t l y arranged i n a " t r i a n g l e " , as i n f i g u r e 2 . 1 . ( V 3 X ) 3 . . . ( V 2 X ) 2 ( V 2 X ) 3 . . . (VX)j (VX ) 2 (VX) 3 . . . XQ X-J ^2 ^3 • • • 2.1 F i g u r e F i g u r e 2 .1 i s c a l l e d the d i f f e r e n c e t r i a n g l e o f the sequence X. Each ent ry i n the t a b l e i s the d i f f e r e n c e of the two e n t r i e s immediate ly below i t . Chapter I I I 65 Lemma 2 .2 shows the r e l a t i o n s h i p between the base of the d i f f e r e n c e t r i a n g l e and the row immediate ly above i t . 2 .2 Lemma. Let X={x n }^Q be any sequence of r e a l numbers. Let Y={y n} ( n°_Q where y i = ( V X ) i + 1 . Then ( V i + 1 X ) J + 1 = W1?) y n 1 P r o o f . We proceed by i n d u c t i o n on i . We have (V Y ) j = y^ = (V X ) j + ^ . Assume the r e s u l t f o r i - 1 . Then ( V i Y ) j = V ( V i _ 1 Y ) J = ( V i _ 1 Y ) j - ( V i - 1 Y ) J _ 1 [by d e f i n i t i o n o f V] = ( V 1 X ) j + 1 - ( V l X ) j [by i n d u c t i v e hypothes i s ] = V ( V i X ) j + 1 I 2.2 Lemma 2 .3 shows tha t any element x^ + ^ of a sequence X = X Q , X ^ , X 2 , . . . may be expressed as the sum of the preced ing element x^ and the l e a d i n g edge of the d i f f e r e n c e t r i a n g l e w i t h X as i t s base . 2 .3 Lemma. Let Y={y n }^Q be any sequence of r e a l numbers. Then ( f o r ieN) y i + 1 = y i + f ( | ) ( V k + 1 Y ) k + r k=0 P r o o f . .We proceed by i n d u c t i o n on i . We have 0 *i = y 0 + ^ i - y 0 ) = y 0 + < v l Y > i = y 0 +1 ( k > ( v k + l Y > k + r k=0 Assume the r e s u l t t r u e f o r i - 1 > 0 . Let X={xn}< n 3_0 where x i = ( V 1 Y ) i + 1 . Then by i n d u c t i v e hypothes i s we have tha t i - 1 x i = x i - 1 + / ^ k 1 ) ^ * ^ ) ^ k=0 i - 1 = x i _ 1 + ) ( ^ X ^ Y W [ ( V i X ) j = ( V i + 1 Y ) j + 1 by lemma 2 .2 ] k=0 Chapter I I I 66 i - 1 = ( V 1 Y ) i + J ( i k 1 ) ( v k + 2 Y ) k + 2 [ b y d e f i n i t i o n o f X i - 1 ] k=0 i = ( V 1 Y ) i ( j I i ) ( V j + 1 Y ) j + 1 where j=k+1 ~j = 1 i - 1 = ( V 1 Y ) i +) ( j l ] ) ( V j + 1 Y ) j + 1 + ( V i + 1 Y ) i + 1 j = 1 i - 1 = ( V 1 Y ) i + ) [ ( J M 1 } 1 ) ] ( V J + 1 Y ) j + 1 + ( V i + 1 Y ) i + 1 C(k) = ( n k 1 ) + (kZi)] j = 1 i - 1 i - 1 = ( V 1 Y ) i + ) ( j ) ( V J + 1 Y ) j + 1 - } ( i j 1 ) ( V J + 1 Y ) j + 1 + ( V i + 1 Y ) i + 1 j=1 j=1 i i - 1 = ( V 1 Y ) ± + [J ( j ) ( V j + 1 Y ) j + 1 - {lh), - ( V l + l Y ) i + 1 ] - [ ) ( l 3 1 ) (V J + 1 Y) j + 1 j=0 j=0 - (V 1 ! ) . , ] + ( V i + 1 Y ) i + 1 = (Vh)i+J ( j ) ( V J + 1 Y ) j + l -f 1 ( 1 J 1 ) ( V J + 1 Y ) J + 1 j=0 j=0 i - 1 i = y± - y i - 1 "I ( l j 1 ) ( v J + l Y ) j + 1 + / ( j ) ( V J + l Y ) j + 1 Cby definite" of V 1 Y ) ± ] j=0 j=0 = Y i " [Yi_1 + f 1 ( i j 1 ) ( V J + 1 ^ ) j + l ] +f ( J ) C V J - 1 Y ) J ^ 1 j=o j=o i = y± - y± + ^) (j)(V^"*'1 Y ) j + 1 [by i n d u c t i v e hypothes i s ] ~j=0 -f ( j ) ( v - J + 1 Y ) j + 1 . But = (V Y ) i + 1 = y i + *| -Y i by c o n s t r u c t i o n . Consequently y i + i = H +f < J ^ J + 1 Y > J + I as d e s i r e d . 1 2 . 3 Theorem 2 .4 s t a t e s tha t the k t h d i f f e r e n c e s o f a sequence x = f x n ] ' n 0 = o a r e i d e n t i c a l l y zero i f and on ly i f there e x i s t s a po lynomia l o f degree0. I f x=f x n} rf-o» x n = f ( n h ) , a necessary and s u f f i c i e n t c o n d i t i o n i n order that (V k X) n =0 f o r a l l i n t e g e r s n i s t h a t f(nh)=p(nh) f o r a l l n , where p i s a po lynomia l o f degree0 . P r o o f . We proceed by i n d u c t i o n on r . For r=0, we have Vn e N p(n)=aQ>0. Assume the r e s u l t t r u e f o r r -1>0. Then r r p(n+1)-p(n) = y a i ( n + 1 ) i - y a ^ 1 ~i=0 - i = 0 r = ) a i [ ( n + 1 ) i - n i ] i=1 r i - 1 i i - 1 = ) a j (j )nJ ( s i n c e ( n + o W = [J ( JjnM - J ] - n 1 = J (J ) n J ) . ~i=1 ~~j=0 j=0 j=0 Observe tha t ( i ) p(x+1) -p(x) i s a po lynomia l of degree < r - 1 , tha t i s ( V X ) n = q(n) f o r some po ly lnomal q w i t h degree0 f o r a l l m e a n i n g f u l k and n. S ince q(n)=p(n+1)-p(n)=(VX) n + ^ we have by lemma 2 .2 t h a t ( V k + 1 X ) n + 1 = ( v k Y ) n > 0 . S ince ( V ° X ) n = p ( n ) > 0 we have tha t (V k X) n >0. i 2 . 5 Chapter I I I 68 In a d d i t i o n , i t i s p o s s i b l e , wi thout l a b o r i o u s c a l c u l a t i o n , to determine the v a l u e s o f the r t h row o f a d i f f e r e n c e t a b l e whose base i s the sequence X mentioned i n the hypotheses o f lemma 2 .5 above. 2.6 Lemma. Let p(x) = a r x r + a r _ 1 x r ~ 1 + . . . +a^x + ag be a po lynomia l of degree r . Let X={p(n) }^_Q. Then ( v r X ) r = r ! a r -P r o o f . S ince by theorem 2.4 (v k X) n =0 f o r a l l k>r we must have that ( v r X ) n = c , a c o n s t a n t . Thus i t w i l l s u f f i c e to show that ( V r X ) r = r ! a r . We proceed by i n d u c t i o n on r . For r=0, we have (7° X ) 0 = p ( 0 ) = a 0 = 0 ! a 0 . Assume the r e s u l t f o r r -1>0. We can demonstrate , employing p r e c i s e l y the same argument as g i ven i n lemma 2 . 5 , tha t (V X) n + ^=q(n) where q i s a po lynomia l of degree < r - 1 whose c o e f f i c i e n t r f o r the term x m , 0 h n _ ^ > i n s t e a d of < i n p u t , m a r k s , h ^ , h f i > . 2.7 D e f i n i t i o n . Let p(x) = a k x k + . . . + a^x + ag be a po lynomia l of degree k>0 w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s . Let fTp( x) be the f o l l o w i n g program f o r i n i ( ( 0 } ; k ; k - 1 ) . ( i ) k=1 i z 2 < — 5 — © i n i t i a l i z e g * — > ® z n a d v a n c e n | 0 0 ^ ^ © z . , :I = v ®z H 2: Chapter I I I 69 ( i i ) k>1 z 04 2^ 0 " i n i t i a l i z e 0 z-,4 2 V ~ 0 ~ ^ i n i t i a l i z e k -1 t k - 1 ? i 1 ! * 1 t f i k - 1 I >®"zQ:advanceQ ©advance^ ^ I ! z 1 : I k - 1 H where VJ_Q i n i t i a l i z e j i s the program © V > p(j)+1 t imes ®R . i ^ 0:®< _i Il,= Chapter I I I ¥ i - 0 a a v a n c e i i s the program -> i " 1 Y Y U ^ 1 ) times K - 1 Y W k i 1 ) t imes and advance k _^ i s the program k - 1 k - 1 > k ! a k t imes lO: 70 The program np(x) c o n s i s t s o f four phases: ( i ) the k heads 0 , . . . , k - 1 are moved to p o s i t i o n s p(0)+1, p(k-1)+1 r e s p e c t i v e l y . I f the input s t r i n g i s o f l e n g t h p ( i ) f o r 00 w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s . Let D = I n 1 5 k 5 k _ 1 ) . Let V be the program 1 IXQ radvanceQ * i & x k 1 : a d v a n c e k ^ i x k -where V^IQ advance.^ i s as g i ven i n d e f i n i t i o n 2.7 f o r v f p ( x ) - Choose n 6 N , y6{0}* such t h a t {y-| >p(n+k) , X = { x n } " n ° _ 0 where x j L=p(n+i) + 1. Let m 6 DQ be such tha t m(input)=y, V K " ] m(marks) = u 1 1 u 2 1 . . . 1 u k - 1 1 u k where ¥ k = 1 u ^ f O } * , V K"{ j u 1 1 . . . lu-j j \ = x i ( tha t i s heads 1 , . . . , k - 1 are each scanning a m a r k e r ) , jm(marks)!= i y j . I f .. . e C t (T~ ,D ) where mQ=m then ( i ) mQ(marks)=m^(marks)=.. .=m k(marks); ( i i ) ¥ k l J m±+^h±)- m i ( h i ) = ( V i + 1 X ) i + 1 ; ( i i i ) ¥ ^ l j m k ( h i ) = p(n+1+i)+1. P r o o f , ( i ) : S i n c e each subprogram advance^, 0 0 and cons ide r i . By i n d u c t i v e hypothes is ¥ J ~ Q m j + 1 ( h j ) - m j ( h j ) = ( V ^ + 1 X ) j + 1 . I t f o l l o w s from the c o n s t r u c t i o n o f V and advance j , 0 < j < i - 1 , tha t m i ( h i ) = mQ(h±) + ( j ) ( V 1 X ) 1 + . . . + ( i ^ 1 ) ( V i X ) i i - 1 = x ± + J ( j ) ( V J + 1 X ) j + 1 [by d e f i n i t i o n o f m Q ] . ~ j = 0 Now by c o n s t r u c t i o n o f advance^, head^ w i l l t r a v e l forward u n t i l i t encounters a marker , the nearest a c c e s s i b l e marker be ing tha t l o c a t e d at p o s i t i o n x^ +^ s i n c e x^0 w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s . Let r f p ( x ) be as g i ven i n d e f i n i t i o n 2 . 7 , D=In1 ; k ; k - 1 ^. (A) I f W = < ( n p ( x ) ) s , D I ( y ) > . . . e C ( r f p ( x ) , D ) then l e t t i n g s be the number o f occur rences o f the l a b e l Z Q i n W, then ( i ) V ^ l J m(h i )=p(s -1+i )+1; and k ,, a m i * uk -1 |„ 1 1 I ( i i ) m(marks) = u 1 1 . . . 1 u k - l 1 u k > -VJ = 1 u ± 6 {0} , -Y j l j • | u 1 1 . . . u i 1 p (s -1+ i )+1 . (B) I f W i < ( n p ( x ) ) S ' 2 l ( y ) > ••• < z 1 ' m > E 5 ( "p ( x )»2> fcnen l e t t i n g s b e t h e number of occur rences o f the l a b e l Z Q i n W, then ( i ) ¥ ^ : J m(h i )=p(s+i )+1; and ( i i ) m(marks) = u 1 1 . . . 1 u k _ 1 1 u k , ¥ k _ 1 u ^ f O } * , ¥ k l ] | u 1 1 . . . u ± 1 J = p (s -1+ i )+1 . P r o o f . (A) We proceed by i n d u c t i o n on the number o f o c c u r r e n c e s , s , o f the l a b e l Z Q i n W. I f the l a b e l Z Q appears on ly once then i t i s obvious from the d e f i n i t i o n of n p ( x ) tha t ¥ K ~ Q m(h^)=p(i)+1 and m(marks) = u ^ 1 . . . 1 u k _ ^ 1 u k , v£ = 1 \U^...U±M = p ( i ) + 1. Assume the r e s u l t t r u e f o r s-1>1 and c o n s i d e r s . Let W = <([] p ( x ) ) s , D I ( x ) > . . . . . . . . . e C(rfp(x) ,D) where there are p r e c i s e l y s - 1 occurrences o f the l a b e l Z Q i n <(rfp(x) )g,D-|-(x)> . . . < Z Q , m > and on ly two occur rences o f the l a b e l Z Q i n < Z Q , m > . . . . . . < Z Q , m " > . By i n d u c t i v e hypothes i s ¥ K ^ Q m(h^) = p (s -2+ i ) + 1 and m(marks) = u ^ 1 . . . 1 u k _ ^ 1 u k where ¥ k _ 1 U j^efO}*, ¥ k " | 1 ' u 1 . 1 . . •u i1-j = p (s -2+ i ) + 1. From the c o n s t r u c t i o n o f r i p ( x ) and lemma 2 .8 ( i ) and ( i i ) i t f o l l o w s tha t m'(marks) =m(marks) and ¥ K ~ Q m'(h^)=p(s-1+i)+1. Thus i n memory c o n f i g u r a t i o n m' heads 1 , . . . , k - 2 are each scanning a square marked by a pebble w h i l e head k _^ i s n o t . Chapter I I I 74 We i n f e r from the c o n s t r u c t i o n o f n p ( x ) that m"=m' except tha t m"(marks) = v 1 1 . . . 1 v k _ 1 1 v k where V K ~ ] v i 6 {0}* and ¥ k ~ ] | v 1 1 . . . v i 1 1 l = p (s -1+ i ) + 1. (B) I t f o l l o w s from the c o n s t r u c t i o n o f i ~ i p ( x ) t h a t W = < ( n p ( x ) ) s , D T ( x ) > . . . . . . where the computat ion . . . c o n t a i n s on ly one occurrence o f the l a b e l Z Q . Let s be the number o f occur rences o f the l a b e l ZQ i n < ( n p ( x ) ) s J S T ^ ^ ••• . We have by (A) tha t ( i ) ¥ ^ l j m ' (h i )=p (s -1+ i )+1 ; ( i i ) m'(marks) = u 1 1 . . . 1 u k - 1 1 u k , ¥ k = 1 u ^ t O } * , ¥ k l ] { u 1 1 . . . u i 1 - | = p (s -1+ i )+1 . A p p l i c a t i o n o f lemma 2 .8 y i e l d s ( i ) ¥ k l J m(h i )=p(s+i )+1; ( i i ) m(marks)=m'(marks) which i s the d e s i r e d r e s u l t , i 2 .9 2.10 Theorem. Let p(x) be a po lynomia l o f degree k>0 w i t h p o s i t i v e i n t e g e r c o e f f i c i e n t s , D=In1 ' k > k _ 1 ^ and n p ( x ) as g i ven i n d e f i n i t i o n 2 . 8 . Then L_/ „ \ = { 0 p ( n ) | n e N } = dom D r r plx; _ " p ( x ) ft P r o o f . We f i r s t show t h a t i f z n e {0} , i z n l = p ( n ) , n 6 N then z R 6 dom Dn thereby p r o v i n g L - z ^ N ^ d o m Dn . The argument proceeds by i n d u c t i o n 'p(x) p ( X ) ~"p(x) on n. I f n = 0 , 1 , . . . , k - 1 then c l e a r l y , by the c o n s t r u c t i o n o f fTp(x) z n e d o m Dn _ " p ( x ) Assume the r e s u l t t rue f o r n - 1 > k - 1 . By i n d u c t i v e hypothes i s W = <(np(x))s,Dj(zn_1)> . . . 6CT(np(x),D). By lemma 2.9 (B) we must have i n p a r t i c u l a r m(h k - 1 )=p (n -1 )+1 and i n genera l tha t ¥ k I ^ m(h i )=p(s+i)+1 where s=n-k, the number o f occur rences o f the l a b e l ZQ i n W, and m(marks) = u . , 1 . . . u k _ 1 1 u k where ¥ k = 1 u ^ f O } * , ¥ k ~ ] | u 1 1 . . . u i 1 | = p (s -1+ i ) + 1. We a s s e r t tha t W' = <(ri p( x) ) s , D T ( z n ) > . . . . . . Chapter I I I 75 ... 6 C T ( r f p ( x ) , D ) where there i s p r e c i s e l y one occurrence o f ZQ i n . . . ... . Observing that there are s+1 occur rences o f the l a b e l z Q i n < ( r f p ( x ) ^ S ' ^ i ^ n ^ < z 1 'm> "' < z o » m ' > f r o m lemma 2 .9 (A) we have t h a t ¥^lj m'(h i )=p(s+i)+1 and m'(marks) = u ^ 1 . . . u k - 1 1 u k , v£=1, u£ e{0}*, vj"] i 1 . . . u ^ 1 J = p(s+i ) + 1. App ly ing lemma 2 .8 to the computat ion ... 6 C ( r f p ( x ) , D ) we conclude tha t V^IQ m"(h^)=p(s+1+i)+1 and i n p a r t i c u l a r tha t m"(h k_^) = p(s+k) + 1 = p(n) + 1. Thus D/ T \(m") = s i n c e the l e n g t h o f the input - u k - 1 = ; tape i s p(n) ( that i s , head l c _ 1 must be scanning the r i g h t endmarker) whence W' 6 CT(]*L/ »D) demonstrat ing tha t z „ 6 d o m Dn ~ l 'p(x)'-' ° n - H p ( x ) Converse l y , i f some s t r i n g z 6dom r f p ( x ) then i t f o l l o w s d i r e c t l y from lemma 2 .9 (B) and the c o n s t r u c t i o n of r f p ( x ) tha t jz|=p(n) f o r some n 6 N , p rov ing dom Dn <=L n/ Y\. - " p ( x ) p ( x ) i 2 . 10 Remark. S ince every bounded language accepted by a d e t e r m i n i s t i c bounded r e v e r s a l mul t ihead f i n i t e automaton ( d e t e r m i n i s t i c one-way mul t ihead f i n i t e automaton) i s s e m i l i n e a r [Sudborough 7 4 ] , i t f o l l o w s tha t there e x i s t d e t e r m i n i s t i c marker languages not recogn ized by any d e t e r m i n i s t i c bounded r e v e r s a l mul t ihead f i n i t e automaton ( d e t e r m i n i s t i c one-way mul t ihead f i n i t e automaton) . Chapter I I I 3 Other o n e - l e t t e r languages. 76 One might t h i n k t h a t the po lynomia ls exhaust the o n e - l e t t e r languages ( A • n • \r) a c c e p t a b l e by I n 1 V r t ' ' '. However, the re e x i s t s a c l a s s , c h a r a c t e r i z e d by constant l i n e a r d i f f e r e n c e e q u a t i o n s , which are not generable by any p o l y n o m i a l . The f o l l o w i n g d e f i n i t i o n i s g i ven f o r completeness ; the reader i s r e f e r r e d to [ H e n r i c i 64] f o r a d e t a i l e d p r e s e n t a t i o n . 3 .0 D e f i n i t i o n . A constant l i n e a r d i f f e r e n c e equat ion o f o rder n i s a f u n c t i o n f : S n + 1 - > R , S<=R, : ( y Q ,y 1 , , y n ) r > a n y n + . . . + a Q y 0 + b, { a Q , . . . , a n , b } S R . A sequence X={x i}^>_Q<=S i s c a l l e d a s o l u t i o n o f f i f VkeN f ( x k , x k + i , • • • » x k + n ) = 0 . We s h a l l be d e a l i n g w i t h constant l i n e a r d i f f e r e n c e equat ions o f order n w i t h domain N n +^ and whose form i s f ( v 0 ' y 1 ' y n } = y n + a n - i y n - 1 + ••• + a o v O + b where a Q , . . . , a n _ 1 < 0 and b<0. To f we s h a l l a t t a c h i n i t i a l c o n d i t i o n s Q = 6 N n, 0 and i n s i s t tha t a s o l u t i o n , X, to f , i f one e x i s t s , meet the c o n d i t i o n V"IQ x^=q^. Note t h a t , except f o r t r i v i a l c a s e s , the sequence XQ,X^ , X 2 , . . . i s always p o s i t i v e and, w i t h the p o s s i b l e except ion o f the f i r s t n+1 e lements , s t r i c t l y i n c r e a s i n g . Given the p a i r the order o f f , n , i s i n d i c a t e d by order f . The f i b o n a c c i sequence, f o r example, i s a s o l u t i o n to « y 0 »y 1 r> y 2 - y 1 -Yo, may be generated i n a way t h a t i s amenable to computat ion by I n 1 ^ A ' n » k ^ . 3.1 Lemma. Let be g i v e n , X a s o l u t i o n to f ( y 0 . y v - . y n > = y n + a n - i y n - i + ••• + y 0 a o + b -n-1 Then ¥m 6N x m + n + 1 = x m + n + ) ( - a j ) ( x m + j + 1 - x m + j ) . n-1 P r o o f . x m + n + ) ( - a j ) ( x m + j +1 - x m + j ) j=0 Chapter I I I j=0 \ n _ 1 (xm+n + ]_ ajxm+j) j=0 n-1 I (-aj ) xm+j+1 j=0 - b = x m+n+1 3.1 On the b a s i s o f the prev ious lemma I o f f e r 3 . 2 D e f i n i t i o n . Let be g i v e n , n=order f . I n l ( { 0 } ; n + 1 ; 2 ) t o b e t h e p r o g r a m Def ine z2< g- -I i n i t i a l i z e 0 z 2 < — Q — © " i n i t i a l i z e ^ z 0 : v n Iadvancen i U t ^advance n-1 z 1 : I n = » z 2 : where Vn_Q i n i t i a l i z e j i s the program ?R0 1 J +^1 t imes SR. i i .=—2—>©i So: Chapter I I I 78 and i n i t i a l i z e n i s the program JR 1 i n 1 t >( -a 0 )q 0 + . . . +(-a n_-| ) q n _ 1 + ( -b) + 1 t imes where VJIQ advancej i s the program )(-a.= ) t imes and advance n_.| i s the program i >SM -—,— " n - 1 1 i ' n - 1 U - a n _ 1 ) t imes The program Pt<^ Q > f i r s t d i s p a t c h e s h e a d i f o r i = 0 , . . . , n - 1 to p o s i t i o n q^+1 on the t a p e . I f the input i s o f l e n g t h q^ then head^ w i l l be scanning the r i g h t endmarker and the computat ion w i l l te rminate s u c c e s s f u l l y . I f the tape i s o f l e n g t h 1, q ^ K q ^ i f o r some i then the input w i l l be r e j e c t e d s i n c e head^ + ^ w i l l be fo rced " o f f " the end o f the t a p e . Head n moves to p o s i t i o n (-aQ)qQ+ . . . + ( - a n _ 1 )q n _^ + ( -b) + 1 which i s the va lue x f i +1, x n 6 X , the s o l u t i o n o f . When the f l ow o f c o n t r o l reaches node ZQ heads 0 , . . . , n - 1 are i n p o s i t i o n s Chapter I I I 79 xm+1 , x m + n + 1 f o r some m 6 N . Head n then l a y s down a marker which i t w i l l l eave behind as i t i s " f o r c e d " by heads 0 , . . . , n - 1 to the p o s i t i o n x m + n + i + 1 . The " f o r c i n g " proceeds i n n stages beg inn ing w i th headg and c o n t i n u i n g i n sequence w i t h h e a d p h e a d n _ ^ . The j t h s t a g e , 0 •••> xm+n +^ r e s p e c t i v e l y and h e a d n occup ies x ra + n + 1 + ( - a 0 ) ( x m + 1 - x m ) + ••• + ( " a n - 1 > ( x m + n - x m + n - 1 ) w n i c n b y l e m m a 3 - 1 i s xm+n+1 + 1* ^ n e a d n ^ s n o w s c a n n i n g the r i g h t endmarker ( i m p l y i n g tha t the l e n g t h o f the input i s x m + n + - | ) the program w i l l h a l t , a c c e p t i n g the i n p u t , o therwise another i t e r a t i o n o f the " f o r c i n g " c y c l e w i l l be executed . Observe tha t i f the input i s o f l e n g t h 1 , and x m < l < x m + 1 f o r some m>n then h e a d n w i l l e v e n t u a l l y be pushed " o f f " the end of the t a p e , caus ing the input to be r e j e c t e d . The f o l l o w i n g lemmas are a formal restatement o f the above d e s c r i p t i o n . 3 .3 Lemma. Let be g i v e n , X a s o l u t i o n to f (yg,y.|, . . . , y n ) = y n + an_iY n_i + ... + aoYo + b » w n e r e n=order f . Choose r 6 N . Let D = I n 1 ( { 0 } ; n + 1 ; 2 ) _ Const ruc t m 6DQ such tha t m(input)=y 6{0}*, i y i > x r + n + 1 , Vn_0 m ( h i ) = x r + i + 1 , (Eu,v) m(marks)=u1v, u,v e{0} , j u 1 v | = i y i , i u 1 ^ = x r + n (=m(h n ) ) . Let r be the program 1 IXQ :advanceQ t j>xn_^ :advance n _^ =»xn: Chapter I I I 80 where V^~Q advance^ i s as g i ven i n 3 . 2 , the d e f i n i t i o n of Q>. I f . . . e Crp(r,D) where niQ=m then <*> *i=0 W = x r + i + i + 1 ; i - 1 ( i i ) V N = 1 m i ( h n ) = ( x r + n + ) ( - a j ) ( x r + j + 1 - x r + j ) ) + 1; j=0 ( i i i ) m n ( h n ) = x r + n + 1 + 1 ; ( i v ) m n (marks) 6{0}*. P r o o f , ( i ) and ( i v ) : S ince advance^, (01 and c o n s i d e r i . By i n d u c t i v e hypothes is i - 2 m i - 1 ^ n n ) = ^ x r + n + 1 ^ + T ( _ a j ^ ( x r + j + 1 " x r+ j^* S i n c e m i ( n i _ - | ) - m i _ i ( n i _ i ) = ~j=0 x r + ^ - x r + ^ _ ^ by ( i ) i t f o l l o w s from the c o n s t r u c t i o n o f advance^_^ tha t m i ( V = m i - 1 < h n ) + ( ^ i - ^ ^ m ^ m - l 5 i - 1 = ( x r + n + D + J ( - a j ) ( x r + j + 1 - x r + j ) . j=0 m-1 ( i i i ) : m n ( h n ) = ( x r + n + 1 ) + ^ ( - a j ) ( x r + j + 1 - x r + j ) [by ( i i ) above] ~j=0 = x r + n + 1 [by lemma 3 . 1 ] . Chapter I I I 81 i 3.3 3.4 Lemma. Let be g i v e n , X i t s s o l u t i o n . Let D = I n 1 ( { 0 } ; n + 1 where n=order f , n as g i ven i n d e f i n i t i o n 3 - 1 . Choose y 6{0} . I f W = < ^"^S'2i (y) > ••• < Z 1 » M > E Q ( n < f >Q>»D) then v"= 0 m(h.j_) = x i + g where s i s the number o f occur rences o f i n W. P r o o f . We proceed by i n d u c t i o n on s . I f s=1 the r e s u l t f o l l o w s from the c o n s t r u c t i o n o f ]~] and s e c t i o n s ( i ) and ( i i ) o f lemma 3.3. Assume the r e s u l t t r u e f o r s-1>1 and c o n s i d e r s . We then have W = ^ ™ < f Q>^S'2i^y) > ••• < Z 1 » m > ••• 6 C(Ti»D) where there are s - 1 occur rences o f z^ i n <(n a n d on ly one occurrence o f z.| i n . . . . By i n d u c t i v e h y p o t h e s i s Yj|-1 m ( n i ^ = x i + s - l • A p p l i c a t i o n o f lemma 3.3 y i e l d s Vn_0 m ' ( h i ) = x i + s . i 3.4 3.5 Theorem. Let be g i v e n , X i t s s o l u t i o n . Let D = I n 1 ( { 0 } ; n + 1 ; 2 ) where n=order f , r!< f as g i ven i n d e f i n i t i o n 3 . 1 . Then L = { 0 ^ x i ^ j i 6 N } = dom Drr - " P r o o f . C l e a r l y L = {y Q ,y 1 , y 2 , . ..} where y^ ^ 6 {0} , ! y ± i =x ± . We proceed by i n d u c t i o n on the i n d e x , i , t o show t h a t y.. e dom Dn . For i = 0 , 1 , . . . , n 1 -" the r e s u l t f o l l o w s from the c o n s t r u c t i o n of n< f Q>. I f i=n+1 i t f o l l o w s from lemma 3-3 t h a t W = <(n < f }Q>)s'2i( wn+1^ ••• < Z 1 » M > ES('i~I,D) where the l a b e l z 1 appears o n l y once i n W i m p l y i n g by lemma 3-4 t h a t Vn_Q m(h i ) = x i + 1 + 1 and i n p a r t i c u l a r m ( h n ) = x n + 1 + 1 . Consequently W ec T(f] < f Q>»B)» whence y n . 1 6 dom Drr n + 1 -" Assume the r e s u l t t r u e f o r i-1>n+1 and cons ide r i . C l e a r l y W = < ^ < f Q ^ S ' - I ^ i ^ ••• < z i ,m> 6 ^ (n^f Q>»D) where the number of occur rences o f Chapter I I I 82 z.| i n W i s i - (n+1) ( that i s , m(hn)=x^_^ + 1 ) . I t f o l l o w s from lemma 3-3 t h a t ( i ) . . . 6C(rl>2) where there i s p r e c i s e l y one occurrence o f i n . . . and ( i i ) m ' (h n )=x i +1. Consequently W . . . 6C-j idl^f Q>>2) which means tha t y^ 6dom Dn . Thus L<=dom Dn " n ~" To see that dom Dn <=L suppose tha t W = <(T\sr n\)Q>D-r(y)> . . . "" ' y ~ 1 6 Cj(ri»D) where {w| tha t ( E i ) , 0x n then by lemma 3.4 m(h n ) = x n + g + 1 where s>1 i s the number o f occurrences o f z^ i n W. I t f o l l o w s tha t l y i = x n + s , hence y 6 L . 1 3.5 3.6 Example. The f i b o n a c c i numbers are the s o l u t i o n to the p a i r where f ( y n > y i » y 2 ) = y2~yi~yo a n d Q = < 0 > 1 > . Therefore the se t {w{w6{0} , ( ( E f , a f i b o n a c c i number), |w]=f)} i s I n 1 » 3 ' 2 ^ - a c c e p t a b l e . 3.7 Example. Let k 6 N + be g i v e n . The sequence X = ( X i ^ - Q ' x i = k 1 i s the s o l u t i o n to the p a i r where f(yg,y-|) = y^ -kyg and Q=<1>. Thus the set { O ^ ^ j n e N } i s In1 ; 2 ; 2 ^ - a c c e p t a b l e . (A c a r e f u l read ing of d e f i n i t i o n 3.2 w i l l show t h a t i t i s a c t u a l l y I n 1 v 1 } ' ' ' - a c c e p t a b l e : s i n c e n=1, no subprograms advance^ f o r j1, the language of example 3-7 i s not generab le by any p o l y n o m i a l . 3.8 Lemma. Let k 6 N + , k>1 be g i v e n . Let X = { k " } ^ . Then ( V i X ) J = ( k - D 1 ^ - 1 > 0 . P r o o f . We proceed by i n d u c t i o n on i . For i=0, we have ( V ° X ) j = k J , as r e q u i r e d . Assume the r e s u l t t r u e f o r i -1>0 then Chapter I I I 83 ( V i X ) j = ( V i - 1 X ) j i - 1 j - 1 = ( k - D 1 - 1 ^ - ^ - 1 ) - ( k - D 1 - 1 ^ - 1 - ^ - 1 ) [by i n d u c t i v e hypothes i s ] = ( k - l ) 1 ^ - 1 . i 3.8 3-9 Theorem. Let k 6 N + , k>1 be g i v e n . Def ine f :N->N :n r>k n . Then there does not e x i s t a po lynomia l p(x) such t h a t pjN = f . P r o o f . A p p l i c a t i o n o f theorem 2 .4 to lemma 3-8 b r i n g s us to the d e s i r e d c o n c l u s i o n . B i b l i o g r a p h y 84 [Baker 76] Baker , John L . , Lec tu re n o t e s , Department o f Computer S c i e n c e , U n i v e r s i t y o f B r i t i s h Columbia , Vancouver B. C , Canada, (1976). [Baker 77a] Baker , John L . , Lec ture n o t e s , Department o f Computer S c i e n c e , U n i v e r s i t y o f B r i t i s h Co lumbia , Vancouver B. C , Canada, (1977) . [Baker 77b] Baker , John L . , S i m u l a t i o n i n a Theory o f Programmable Machines, T e c h n i c a l Report 7 7 - 7 , Department of Computer S c i e n c e , U n i v e r s i t y o f B r i t i s h Columbia , Vancouver B. C , Canada, ( J u l y 1 9 7 7 ; . [ G i u l i a n o 70] G u i l i a n o , J . A . , W r i t i n g Stack Automata, IEEE Conference Record o f 1970 E leventh Annual Symposium on Swi tch ing and Automata Theory, (1970) , 181-193. [ H a r r i s o n and I b a r r a 68] H a r r i s o n , M i c h a e l A. and Oscar H. I b a r r a . M u l t i - T a p e and M u l t i - H e a d Pushdown Automata, In fo rmat ion and C o n t r o l 13, (1968), 433 -470 . [ H e n r i c i 64] H e n r i c i , P e t e r , Elements o f Numerical A n a l y s i s , John Wi ley and Sons, I n c . , (1964) . [ R i t c h i e and S p r i n g s t e e l 72] R i t c h i e , R. W. and F. N. S p r i n g s t e e l , Language Recogn i t i on by Marking Automata, In fo rmat ion and C o n t r o l 2 0 , (1972) , 313 -330 . [Rosenberg 64] Rosenberg, Arno ld L . , On n-Tape F i n i t e S t a t e A c c e p t o r s , IEEE Conference Record on Sw i tch ing C i r c u i t Theory and L o g i c a l Des ign , (1964), 7 6 - 8 1 . [Rosenberg 66] Rosenberg, Arno ld L . , On M u l t i - H e a d F i n i t e Automata, IBM J o u r n a l 10 No. 5 , (September 1966) , 388-394. [Rosenberg 67a] Rosenberg, Arno ld L . , A Machine R e a l i z a t i o n o f the L i n e a r Contex t -F ree Languages, In fo rmat ion and C o n t r o l 10 No. 2 , (February 1967), 175-188. [Rosenberg 67b] Rosenberg, Arno ld L . , M u l t i t a p e F i n i t e Automata w i t h Rewind I n s t r u c t i o n s , J o u r n a l o f Computer and System Sc iences 1 No. 3 , (October 1967), 2 9 9 - 3 1 5 . [ S p r i n g s t e e l 67] S p r i n g s t e e l , F. N . , C o n t e x t - F r e e Languages and Marking Automata, Ph.D t h e s i s , U n i v e r s i t y o f Washington, (1967) . [Sudborough 71] Sudborough, I. H . , Computation by M u l t i - H e a d W r i t i n g F i n i t e Automata, Ph.D t h e s i s , Computer Sc ience Department, Pennsy lvan ia S t a t e U n i v e r s i t y , U n i v e r s i t y Park , P A . , (1971) . [Sudborough 74] Sudborough, I. H . , Bounded-Reversal Mu l t ihead Automata Languages, In fo rmat ion and C o n t r o l , (1974) , 317-328. [Sudborough 76] Sudborough, I. H . , One-Way Mu l t ihead W r i t i n g F i n i t e Automata, In fo rmat ion and C o n t r o l 30 , (1976) , 1 -20 .