Lecture notes for Theory of computation pdf

what is theory of computation in computer science and theory of computation context free grammar pdf free download
JackBrown Profile Pic
JackBrown,Georgia,Professional
Published Date:12-07-2017
Your Website URL(Optional)
Comment
Theory of Computation S. Arun-Kumar February 18, 2009Chapter 1 Basics: Prerequisites and Notation 1.1 Sets and Operations on Sets We assume the usual notions and notations of set theory including those of relations. We will generally use the following notation for sets. N The set of Natural numbers (including 0) P The set of Positive integers R The set of Real numbers Z The set of Integers ∅ The empty set ⊆ The (infix) subset relation between sets ⊂ The (infix) proper subset relation between sets ∪ The infix union operation on sets ∩ The infix intersection operation on sets ∼ The prefix complementation operation on sets − The infix set difference operation on sets × The infix cartesian product of sets n A The postfix n-fold cartesian product of A, i.e.A×···×A z n-times A 2 The powerset of A The usual notations will be used for arithmetic operations on numbers. This includes the operation of subtraction (denoted by the infix operator−) which is also the set difference operation. Similarly we may use the symbol× for bothcartesian product and multiplication of numbers. Usuallythecontextwilldeterminewhichoperationisintended. Someoperationssuch as multiplication may be denoted by., or no symbol at all as is usual in mathematics. Further P Q the usual prefix operations for sum ( ) and product ( ) of sets or sequences of numbers will be used. 78 CHAPTER 1. BASICS: PREREQUISITES AND NOTATION Convention 1.1.1 0 • A will be identified with the empty set∅. 1 • A will be identiifed with the set A • A 1-tuple (a) will be identified with a. 1.2 Relations, Functions and Predicates Definition 1.1 An-aryrelation forn 0 on setsA , ...,A is any subset ofA ×···×A . 1 n 1 n Definition 1.2 Given two sets A and B and a binary relation f⊆A×B, −1 −1 • Then f ⊆B×A the converse of f is the relation defined by (b,a)∈f if and only if (a,b)∈f. • f is called a partial function of type A−7→ B, if f satisfies the image uniqueness property viz. that for each element a∈ A there is at most one element b∈ B such that (a,b)∈f. b is called the image of a under f. • f is said to be defined at a∈A if a has an image under f. • f is said to be undefined at a if it has no image under f. • f is called a total function of type A→B if f is a partial function of type A−7→B and every element of A has an image under f. r⊆A ×···×A A n-ary (for n0) relation on sets A ,...,A 1 n 1 n f :A+→B A partial function from set A to set B f :A→B A total function from set A to set B f(a) =b b is the image of a under f f(a) =⊥ f is undefined at a Dom(f) The subset of values for which f is defined Ran(f) The subset of values which are images of elements in Dom(f) Notes.1.2. RELATIONS, FUNCTIONS AND PREDICATES 9 1. A constant (e.g. a natural number) will be regarded as a total function from the empty set to the set that constant belongs to (e.g. N). This is to be regarded as being different from a constant function such as f : R→ N defined as f(x) = 5 which is a unary total function defined on the reals and which yields the natural number 5 for every real argument. 2. The notation we use for functions may also be used for relations. In fact every relation r⊆ A ×···×A may be thought of as a total function of type r : A ×···×A → 1 n 1 k A ×···×A n k+1 2 , for eachk with 1≤kn. Hence for any (a ,...,a )∈A ×···×A , where 1 k 1 k 1≤kn, then r(a ,...,a )=(a ,...,a ) (a ,...,a ,a ,...,a )∈r (1.1) 1 k k+1 n 1 k k+1 n 3. When r(a ,...,a ) is a singleton set we omit the set braces. Further, each such relation 1 k may also be thought of as a partial function of type r :A ×···×A +→A ×···×A (1.2) 1 k k+1 n where (a ,...,a )∈Dom(r) if and only if r(a ,...,a )=6 ∅ in 1.1 1 k 1 k Facts 1.1 1. Every total function is also a partial function. 2. f :A→B implies Dom(f)=A. Definition 1.3 Twopartial functionsf,g :A+→B areequal ifandonly ifDom(f)=Dom(g) and for each a∈Dom(f), f(a)=g(a). Definition 1.4 Let f :A+→B be a partial function. ′ ′ ′ • f is injective if for each a,a ∈ Dom(f), a =6 a implies f(a)6= f(a). f is also said to be an injection. −1 −1 • If f is injective then f :B−7→A the inverse of f, with Dom(f ) =Ran(f)⊆B and −1 −1 for every b∈Dom(f ), f (b) =a iff f(a)=b. • f is surjective if Ran(f) =B. f is also said to be a surjection. • f is bijective (or is a bijection) if it is both injective and surjective.10 CHAPTER 1. BASICS: PREREQUISITES AND NOTATION Facts 1.2 −1 1. If f :A−7→B is injective then for every a∈Dom(f), f (f(a)) =a. −1 2. If f : A−7→ B is bijective then f is total (of type B → A) and for every b∈ B, −1 f(f (b)) =b. Definition 1.5 Let g :A−7→ B and f :B−7→ C be partial functions. The composition of g and f (denoted g;f or f◦g) is the partial function h :A−7→C such that • Dom(h) =a∈Dom(g) g(a)∈Dom(f) and • for each a∈Dom(h), h(a)= g;f(a)=f◦g(a)=f(g(a)). Notation. The notation f◦g is preferred by mathematicians generally, though the notation g;f more closely represents the sequential composition of functions in programming. We will use either of them. Note that composition is strict in the sense that for any a, a6∈ Dom(g) or a∈ Dom(g) but g(a)6∈Dom(f) implies a6∈Dom(h) and hence h(a) =⊥. If we were to regardf andg as transducers which take an input from its domain and transform it into an output in its co-domain, thenh is a composite transducer which transforms an input froma∈A into an output c∈C in a two step process by first transforming a to b =g(a) and then transforming b to c = f(b) = f(g(a)). The two step transformation may be pictured as follows.   f(g(a)) g(a) a - - - g f Figure 1.1: Composition of unary functions Notation. Weusuallyabbreviatesequencesofvaluessuchasa ,...,a (whicharethearguments 1 k ⇀ a ofafunction)by ,wherethelengthofthesequenceiseitherunderstoodorimmaterial. Where ⇀ k the length of the sequence is important we may write it as a . We will be interested in a generalised composition as defined below. m Definition 1.6 Assumef :B −7→C is anm-ary function andg ,···,g arek-ary functions 1 m k k of the typeg ,··· ,g :A−7→B. Then thek-ary functionh :A−7→C obtained bycomposing 1 m the m functions g ,...,g with f (as shown in the figure below) is such that 1 m1.2. RELATIONS, FUNCTIONS AND PREDICATES 11 ⇀ ⇀ ⇀ ⇀ k k k k k a a a a • Dom(h) = ∈A (∀i : 1≤i≤m : ∈Dom(g ))∧(g ( ),···,g ( ))∈Dom(f) i 1 m and ⇀ ⇀ ⇀ k k k • h( a ) =f(g ( a ),···,g ( a )). 1 m Notation. The same notationforsequences ofvalues may beextended tosequences offunctions which are themselves arguments of ahigher-order function. Forexample, the tuple of functions ⇀ g g ,···,g (which are arguments of the generalised composition operator) may be denoted . 1 m Extending the notation for the composition of unary functions to generalised composition we ⇀ ⇀ g g have h = ;f = f◦ . Where the length of the tuple is important we may write the above ⇀ ⇀ ⇀ ⇀ m m m k g g g a tuples as and respectively. Then h = ;f =f◦ .  a 1 - b u 1 u g 1 u - a k  a 1 - b 2 u u g 2 u -  - a k - w c u - u f w u - w  a 1 - u g u k b m u - a k Figure 1.2: Generalised Composition of functions Definition 1.7 Given an n-ary relation r ⊆ A ×···×A , its characteristic function 1 n ⇀ denotedχ , is thetotal functionχ :A×···×A →0,1 such that for each a∈A×···×A , r r 1 n 1 n ( ⇀ ⇀ 1 if a∈r a χ ( )= r ⇀ 0 if a6∈r12 CHAPTER 1. BASICS: PREREQUISITES AND NOTATION 1 Definition 1.8 An atomic predicate is a relation . The class of (first-order) predicates is the smallest class containing the atomic predicates and closed under the following logical operations. 1. the unary (prefix) negation operation (denoted¬) 2. the binary (infix) operation and (denoted∧) 3. the binary (infix) operation or (denoted∨) 4. the unary (prefix) universal quantifier (denoted∀) 5. the unary (prefix) existential quantifier (denoted∃) The usual notions of free and bound variables apply to the predicates and quantified formulae. Further the usual meaning of these predicates is as defined in any text on first order logic. Further the usual rules of scope of variables apply here. To denote the scope of variables in quantified predicates we write the body of the quantified formula within brackets. ⇀ ⇀ ⇀ ⇀ ⇀ y y y Example 1.2.1 Consider the first order predicate q( ) defined as q( ) =∀ x p(x, ) ⇀ ⇀ ⇀ ⇀ y y x x where p( , ) is a first order predicate in which the variables in and may occur free. ⇀ ⇀ y p(x, ) may itself be a compound predicate defined in terms of other predicates. The quantifier ⇀ ⇀ ⇀ ⇀ ⇀ y y x x x “∀ ” in q( ) however, binds all occurrences of variables in that occur free in p( , ). The scope of the binding is indicated by the matching brackets “ ” and “ ” in the definition of ⇀ ⇀ ⇀ ⇀ y y y x q( ). The variables that are free in q are precisely those from whixh occur free in p( , ) ⇀ y and this fact is indicated by the notation “q( )”. ⇀ ⇀ ⇀ Definition 1.9 Let p and q be predicates with free variables drawn from x and let x=y, z . The characteristic functions of compound predicates is defined in terms of the characteristic functions of their components as follows. ⇀ ⇀ • χ (x) =1−χ (x) ¬p p ⇀ ⇀ ⇀ x x x • χ ( ) =χ ( ).χ ( ) p∧q p q ⇀ ⇀ ⇀ x x x • χ ( ) =1−(χ ( ).χ ( )) p∨q ¬p ¬q ( ⇀ ⇀ 0 if χ (a, z ) = 0 for some a p z • χ ( )= ∀yp 1 otherwise 1 Hence we use the same notation for atomic predicates as we use for relations1.3. EQUALITY 13 ( ⇀ ⇀ z 1 if χ (a, ) = 1 for some a p • χ (z )= ∀yp 0 otherwise We use some derived operators such as⇒ and⇔ defined as follows: (p⇒q) = (¬p)∨q (p⇔q) = (p⇒q)∧(q⇒p) The usualequationallaws ofFirst-orderlogichold. Wewillalsohave occasiontousebounded quantification – operations derived from the quantifiers and used in the context of the natu- rals. They are defined as follows. ⇀ ⇀ ∀yzp(x,y) = ∀y(0≤yz)⇒p(x,y) ⇀ ⇀ ∃yzp(x,y) = ∃y(0≤yz)∧p(x,y) Note that bounded quantification obeys the De Morgan laws making each bounded quantifier the dual of the other. That is ⇀ ⇀ x x ∀yzp( ,y) = ¬(∃y z¬p( ,y)) ⇀ ⇀ x x ∃yzp( ,y) = ¬(∀y z¬p( ,y)) 1.3 Equality In the course of these notes we shall use various kinds of equality. Most of these notions of equality share the property ofbeing congruences i.e. they are equivalence (reflexive, symmetric and transitive) relations and the two sides of the equality are mutually replaceable under all contexts. However, it is necessary to emphasize that there are differences between the various kinds of equality. Most mathematics texts often ignore these differences, (and we may have been guilty too in the course of writing these notes) but we feel that they are important for various logical reasons and the reader should be aware of the differences. We briefly describe them below andwe hope the differences that we have made explicit will be useful forthe reader in understanding not just these notes but mathematics texts in general. Definitional Equality. This is an equality by definition, and we use the symbol, to denote this. This is most often used in the following situations. 1. to abbreviate a complex expression by giving it a name, 2. to name a complex expression because it or its form is somehow considered impor- tant.14 CHAPTER 1. BASICS: PREREQUISITES AND NOTATION 2 3 2 Hence when we writep(x),x −9 orq(x),x +3x +3x+1,we are either abbreviating or naming the expression on the right hand side by the expression on the left hand side 3 of,. Given another definition r(x), (x+1) , even in the context of polynomials over the reals or integers it is incorrect to write “q(x) , r(x)” because the two expressions q(x) and r(x) define syntactically distinct expressions. Instantiated Equality. Continuing with the previous examples we would often write expres- 2 sions like p(4) = 4 −9 = 7. Note here that p(4) is an instance of p(x) defined above. 2 The equality symbol “=”(between “p(4)”and the expression “4 −9”) here is overloaded 2 2 to imply that p(4) is a particluar instance of the definition p(x) , x − 9 Note that 2 2 “p(y)=y −9” is also a form of instantiated equality and so is p(x+1)= (x+1) −9. Syntactic Identity This is a peculiar notion of equality we will use more in the context of languages or programs rather than in the case of mathematical expressions. Consider 3 3 the two expressions r(x) , (x + 1) and s(y) , y . It is clear that by appropriate 3 3 instantiations, we getr(z) = (z+1) ands(z+1) =(z+1) . Thereforer(z) =s(z+1). However, this equality between r(z) and s(z +1) is stronger than just provable equality — they are in fact, syntactically identical as expressions. This syntactic identity depends only on the form of the original definitions and is independent of the context or the interpretationoftheseexpressionsinanymathematicaldomain. Weemphasizethisaspect by writing r(z)≡s(z+1). As in the case of definitional equality, syntactic identity also implies provably equality. Also definitional equality implies syntactic identity. 2 ′ 2 α-Equality. Consider the two definitionsp(x),x −9 andp(y),y −9. It is clear thatp(y) 2 ′ may be regarded as an instance of the definitionp(x),x −9 andp(y)≡p(y). Equally ′ ′ 2 well mayp(x) be regarded as an instance of the definitionp(y),y −9 yielding p(x)≡ ′ p(x). However the two definitions themselves are not syntactically identical because 3 ′ of the use of different names x and y to express each definition. Hence p(x)6≡ p(y). ′ 2 2 Howeverthereisasenseinwhichboththedefinitionsp(y),y−9andp(x),x−9may be regarded as being the same (or equal) in that the variables x and y used to give the definition its form are only “place-holders” whose name is of no consequence whatsover except when replacement of one name by the other causes a name clash. In the absence of such name clashes the uniform replacement of one name by the other causes neither any confusion nor any change in the intended meaning of the definition. We call this ′ α-equality and we denote this fact by writing p(x) = p(y). As with other equalities, α since α-equality is also a reflexive relation, it follows that any two syntactically identical expressions are also α-equal. We will come across this later in the λ-calculus. Provable Equality. This is the most commonly used (and abused) equality and is denoted by the usual “=” symbol. In the foregoing examples even though it is incorrect to write q(x),r(x),inthecontextofpolynomialsoverrealnumbersitisperfectlycorrecttowrite 3 3 2 3 2 (x+1) = x +3x +3x+1, because the equality of the expressions x +3x +3x+1 3 and (x+1) can be provenusing the laws ofreal number arithmetic. Any two expressions that are equal by definition are also provably equal (by invoking the definition). Hence 2 2 However the equality symbol “=” between the expressions “4 −9” and “7” is provable equality. 3 ′ The fact that we have used two different names “p” and “p ” does not count1.4. OTHER NOTATIONAL DEVICES 15 2 p(x) =x−9andwecouldreplacealloccurrencesoftheexpressionp(x)bytheexpression 2 2 2 x−9andvice-versa. Itisalsoperfectlycorrecttowrite“p(x) =x−9”or“x−9=p(x)”. To continue with our examples in the context of polynomials, it follows therefore that q(x) = r(x) since the expressions they denote are provably equal. But note that even in the context of polynomials over reals, q(x)6= r(x) and q(x)6≡r(x). α To summarize, we have that for any two (mathematical or formal) expressions E and F 1. E,F implies E≡F and 2. E≡F implies E = F which in turn implies E =F. Hence E,F also impliesE = F α α and E =F. 3. None of the above implications may however, be reversed in general i.e., it is not true in general that ifE =F then E = F orE≡F would hold, nor doesE≡F implyE,F α or F ,E holds. 4. Further while all forms of equality may be instantiated, no form of instantiated equality may imply any other form of equality unless it can be proven. 1.4 Other Notational Devices We generally follow the practice ofsplitting longproofs oftheorems into claims and using these claims. In most cases the proofs of claims are distinguished from the main proof by the use of the bracketing symbols “⊢” and “⊣” to enclose the proof of the claim and separate it from the proof of the main theorem.16 CHAPTER 1. BASICS: PREREQUISITES AND NOTATIONChapter 2 The RAM Model 2.1 The Unlimited Register Machine (URM) Assume the following about the machine. • A countably infinite number of discrete storage elements called registers each of which can store an arbitrarily large natural number. The registers R ,R ,R ,··· are indexed 1 2 3 by the set P of positive integers. These registers form the memory. • The contents of R , i∈P are denoted respectively by R ∈N. Equivalently M :P→N i i the memory map may be regarded as a total function from the positive integers to the natural numbers so that M(i) =R for each i∈P. i • We will usually ensure that only finitely many registers contain non-zero values i.e. M is 0 almost everywhere. • A URM program P is a sequence I ,I ,...,I of instructions. 1 2 p • The instruction set has opcodes 0,1,2,3 respectively, and each instruction I , 1≤j≤p, j is typically of one of the following forms where i,m,n∈P. opcode instruction semantics Verbal description 0 Z(n) R := 0 Clear register R n n 1 S(n) R :=R +1 Increment the contents of register R n n n 2 C(m,n) R :=R Copy the contents of register R into R n m m n Jump to instruction i if the contents of the 3 J(m,n,i) R =R ?i :j +1 registers R and R are the same. m n m n Otherwise execute the next instruction 1718 CHAPTER 2. THE RAM MODEL We have used the syntax of the imperative fragment of SML to describe the effect of each instruction on the appropriate register. The semantics of the jump instruction mixes pidgin SML with the notation for conditional expressions used in languages like C and Perl. The verbal description describes the semantics informally in English. • Given a URM program P = I ,I ,...,I , register contents r ,r ,... respectively and a 1 2 p 1 2 program counterPC∈P denoting the next instruction to be executed, aconfiguration of the URM is a 3-tuplehP,M,PCi where M(n) =r . n • Given an initial memory M and a program P = I ,I ,··· ,I , with p≥ 1, the initial 0 1 2 p configuration of the URM is γ =hP,M ,1i 0 0 • Let γ =hP,M,ji be any configuration of the URM. The URM is said to halt if j p. Such a configuration is also called the halting configuration and the result of the computation is M(1) the contents of the register R . If 0 j≤ p, then a step of the 1 ′ ′ ′ ′ ′ ′ computation fromγ is given byγ7→γ whereγ =hP,M ,ji andM andj are as given by the following table: ′ ′ I = M = j = j Z(n) 0/nM j +1 S(n) M(n)+1/nM j +1 C(m,n) M(m)/n j +1 J(m,n,i) M i if M(m) =M(n) M j +1 if M(m)6=M(n) ′ ′ where M =a/nM denotes that M is identical to M for all values other than n and ′ M (n) =a regardless of whatever M(n) might be. • Unconditional jumps are described by instructions such as J(n,n,j) since M(n) = M(n) always. Similarly skip instructions (or no-op as they are referred to in hardware) may be implemented using instructions such as C(n,n) or by jumping unconditionally to the next instruction. • The URM executes instructions in sequence (unless it executes a jump instruction, when the sequence is altered) till the instruction referred to by PC does not exist. Then the URM is said to halt. Definition 2.1 A memory map M of the URM is said to be finite if there are only a finite number of registers containing non-zero values i.e. the setM(n) M(n) 0 is finite. If the (initial) memory M in the initial configuration is such thatM (n) M (n) 0 is 0 0 0 ′ finite, then the result of executing each instruction results in a new memory stateM such that ′ ′ M (n)M (n) 0 is also finite. In other words, at no stage of the execution of the program does the URM require more than a finite number of registers to be used.2.1. THE UNLIMITED REGISTER MACHINE (URM) 19 Lemma 2.1 1. Each URM instruction preserves finite memory maps. 2. The only registers whose contents may modified by a URM program are those that are explicitly named in the program. Every instruction has a deterministic effect on the URM machine. In other words, given a memory mapM each of the instructions Z(n), S(n) and C(m,n) when executed, would yield a ′ unique memory state M in all programs and under all execution conditions. The instruction J(m,n,i)toohastheeffectofuniquelydetermining thenextinstruction (ifany)tobeexecuted. Lemma 2.2 . ′ 1. Every non-halting configuration of the URM has a unique successor. That is, γ7→γ and ′′ ′ ′′ γ7→γ implies γ =γ . 2. If Γ is the set of all URM configurations with finite memory maps then7→ is a partial function from Γ to Γ. 7→ is a partial function on the configurations of the URM because it is undefined for halt- ing configurations. It suffices for us to consider only configurations with finite memory maps, since we are interested in the notion of computability which requires for each task only a finite amount of resources such as storage and program length. However, we do need to consider the availability of unlimited storage. If we did fix storage limits to some fixed number then our theoretical development suffers when technology improves to provide more storage than our limit. A theory such as ours would have long term applicability only if it does not artificially constrain the solutions to problems. Similarly while we consider the executions of URM pro- grams of arbitrary length our fniteness constraints are limited to specifying that the program may not be of infinite length. The reader could ask whether the limitation tojust fourkinds ofinstructions is notanartificial constraint. Our answer to that would be two-fold viz. 1. that only the kinds of operations are being fixed and that any reasonable mechanical device (going by the history of mechanical devices) would be capable of performing only a fixed finite set of different kinds of operations, and 2. the actual parameters that these operations may take is actually infinite. Definition 2.2 Let γ be an initial configuration of the URM. A (finite or infinite) sequence 0 of the form γ 7→γ 7→··· is called an execution sequence from γ . A computation of the 0 1 0 URM is a maximal execution sequence from an initial configuration.20 CHAPTER 2. THE RAM MODEL Lemma 2.3 Let γ 7→ γ 7→ γ 7→··· be an execution of the URM with the corresponding 0 1 2 memory mapsM ,M ,M ,.... IfM is a finite memory map, then so are each of the succeeding 0 1 2 0 memory maps M , M , etc. 1 2 Definition 2.3 1. AURMprogramP convergesoninput(a ,a ,...,a )ifitbeginsexecutionfromtheinitial 1 2 k memory state M = a ,a ,...,a ,0,0,... and PC = 1 and halts after a finite number of 0 1 2 k steps of computation. Notation. P(a ,a ,...,a )↓ denotes that P converges on input (a ,a ,...,a ) 1 2 k 1 2 k 2. Otherwise P is said to diverge on the input. Notation. P(a ,a ,...,a )↑. 1 2 k 3. P is said to converge to b∈ N on the input (a ,a ,...,a ) if it converges on the input 1 2 k and reaches a configuration in which M(1) =b. Notation. P(a ,a ,...,a )↓b denotes that P converges on input (a ,a ,...,a ) to b. 1 2 k 1 2 k k Definition 2.4 A URM program P URM-computes a partial function f :N−7→N, if and only if • for each (a ,...,a )∈Dom(f), P(a ,...,a )↓f(a ,...,a ) and 1 k 1 k 1 k • P(a ,...,a )↑ for all (a ,...,a )6∈Dom(f) 1 k 1 k Definition 2.5 A partial function f is URM-computable if and only if there is a URM programP which computesf. A predicatep is URM-decidable if and only if there is a URM program which computes its characteristic function χ . p (k) k Foreachk≥ 0,everyURMprogramP computesapartialfunctionφ :N +→N. Givenanin- P put (a ,a ,...,a ) it begins execution from the initial memory stateM =a ,a ,...,a ,0,0,... 1 2 k 0 1 2 k (k) and PC = 1 and if and when it halts φ (a ,...,a ) =R , i.e. the final result is the value 1 n 1 P (k) in register R . If it does not halt for the given input then φ (a ,...,a ) =⊥. In the case 1 1 n P decidability however, if p is an m-ary relation for some m 0, note that the characteristic function is always total and hence a URM program that implements it should halt for every m-tuple input. But it is quite possible that the program does not halt on some (m+1)-tuple input.2.2. EXAMPLES 21 2.2 Examples In the following examples we illustrate programming the URM. Since the actual programs can be quite tedious and confusing to read and understand, we also provide flow-charts to explain the working of the programs. The language of flow charts consists of boxes, circles, diamonds andarrowsconnecting them toformaflow-chart program. Wefollowtheusual convention that boxes denote actions that could change the memory state. Boxes enclose actions which may change the state of the memory. We use a notation drawn from pidgin SML for this purpose. The same notation has been used earlier in the tables defining the semantics of the instruction set. Each box may enclose a sequence of instructions. Diamonds indicate decisions to be taken depending on the evaluation of the condition in the ? diamond. Each diamond encloses a condition of the form R =R whose truth in the m n memory state requires a different flow of control. The letters “Y” and “N” on the arrows emanating from a diamond indicate the flow of control when the condition is true or false respectively. Circles usually enclose the single word “STOP” and indicate that a halting configuration has been reached and no further execution is possible or necessary. In each case the initial memory map is also indicated Example 2.2.1 The addition function x+y. R R R 1 2 3 x y 0 . . . . ? H H   H  H  1. J ( 2, 3, 5 ) H Y  - ? H - R =R STOP 2. S ( 3 ) 2 3 b P 1 b 3. S ( 1 ) b  4. J ( 1, 1, 1) b b N ? R :=R +1 3 3 R :=R +1 1 1 ( 1 x if x is even 2 Example 2.2.2 f(x)= ⊥ otherwise22 CHAPTER 2. THE RAM MODEL R R R 1 2 3 x 2k k 0 . . . ? H H  H  H 1. J( 2,1,6 )  H Y 2. S ( 3 ) - ? H P 2 b R2 =R1 3. S ( 2 ) b 4. S( 2 ) b 5. J ( 1, 1, 1) b ? b 6. C ( 3, 1 ) N R :=R 1 3 ? R :=R +1 3 3 R2 :=R2 +1  ? R :=R +1 2 2 STOP  Further notes, notations and terminology • Every instruction of theURM is deterministic (in the sense that the effect ofthe instruc- tion on the state of the program is unique). Therefore every URM-program is computes partial of the initial state to the final state • Sinceweareinterested onlyinthecontents ofR1whenaprogramP halts, every program is a partial function whose range is contained in N. ⇀ a Notation. Given a program P and a tuple of inputs = (a ,...,a ), P(a ,...,a ) 1 k 1 k ⇀ denotes the result of executing P with the input a • The type of the function determined by a program P depends entirely on the vector of inputs that we consider. 1. The addition program P in the example does not necessarily represent only the 1 binary operation ofaddition. 2. If there are no inputs it implements the constant function 0. 3. If the initial configuration has only asingle input,x thenP implements the identity 1 function f(x)=x. 4. Iftheinitialcofigurationconsists of3values thenP implements thepartialfunction 1 ( x+y−z if x≥ 0 f(x,y,z)= ⊥ otherwise Hence for any URM program P and for any k≥ 0, P implments a unique partial function k k φ : N +→ N i.e the arity of the function implemented by a program is not pre-determined P and is dependent entirely on the length of the input vector. k k Definition 2.6 A URM-program P implements a function g :N +→N iff φ =g. P2.2. EXAMPLES 23 Example 2.2.3 Consider program P . The following are the functions it implements for for 2 the arities 1,2 and 3 respectively. ( 1 x if x is even (1) 2 φ (x) = P 2 ⊥ otherwise ( 1 (x−y) if x is even(x-y) (2) 2 φ (x,y)= P 2 ⊥ otherwise ( 1 z+ (x−y) if x is even (3) 2 φ (x,y,z)= P 2 ⊥ otherwise Notes. 1. Each program P implements an infinite number of distinct functions and exactly one function of each arity. k 2. Foreachfunctionf :N +→NthathasanimplementationP,thereareaninfinitenumber of distinct programs that implement the same function. Example 2.2.4 Add to program P the following instruction 2 J(1,1,8) ′ This produces a new program P , which implements exactly the same function as P. We 2 could similarly add more instructions and keep getting syntactically distinct programs which all implement the same function. URM -Decidability m Definition 2.7 A predicate (or a relation) p ⊆ N is URM-decidable if its characteristic m (total) function χ :N →0,1 is URM-computable. p Example 2.2.5 The following predicates are URM-decidable. 1. x =y is implemented by24 CHAPTER 2. THE RAM MODEL ? 1 a  1. J ( 1, 2, 4) a  a a  2. Z ( 1 ) a Y N  ? a  R =R 1 2  3. J ( 1, 1, 6 ) H  H  H 4. Z ( 1 )  H  cmrmn. H H  5. S ( 1 ) 2 ? ? R := 0 1 R := 0 1 R1 :=R1 +1 '  - STOP &% 2. odd(x) is implemented by incrementing R and toggling R to reflect the evenness or 2 3 oddness of R . Let T(3) denote toggle R . Initially R = 0 and R = 0. The final flow 2 3 2 3 chart including T(3) looks as follows. ? H H H H ? Y - R =R H 1 2 a  a  a  a  a a  cmrmn. N ? R :=R 1 3 ? ? S(2) T(3) STOP " cmrmn. The final program is then as follows.2.2. EXAMPLES 25 ? H H H H H H ? H b R =R H Y 3 4 b b b b ? b b b N S(3) ? ' ? - STOP &% Z(3) Figure 2.1: Implementing T(3) 1. J (1,2,8) 2. S (2) 3. J (3,4,6) 4. Z (3) 5. J (1,1,1) 6. S (3) 7. J (1,1,1) 8. C (3,1) Composing URM-Programs Function composition in URM is simply the catenation of the component programs. However we cannot catenate two programs to produce a composition unless the termination or halting of the first is tackled in a meaningful fashion – clearly then jump instructions have to be standardized. Definition 2.8 A programP =I ,...,I is instandardform provided every jump instruction 1 r J(m,n,p) is such that 1≤p≤r+1. ⋆ Lemma 2.4 For any programP there is a programP in standard form such that for all input ⇀ ⇀ ⇀ ∗ vectors a, P(a)↓b iff P (a)↓b.

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.