Popular in Course
Popular in Computer Information Technology
verified elite notetaker
This 104 page Class Notes was uploaded by Kathleen Cartwright on Monday September 28, 2015. The Class Notes belongs to CIS511 at University of Pennsylvania taught by J.Gallier in Fall. Since its upload, it has received 25 views. For similar materials see /class/215368/cis511-university-of-pennsylvania in Computer Information Technology at University of Pennsylvania.
Reviews for THEORYOFCOMPUTATION
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/28/15
Chapter 7 Computational Complexity 71 The Class 73 In the previous two chapters we clari ed what it means for a problem to be decidable or undecidable In principle if a problem is decidable then there is an algo rithm ie a procedure that halts for every input that decides every instance of the problem However from a practical point of view knowing that a prob lem is decidable may be useless if the number of steps time complexity required by the algorithm is excessive for exam ple exponential in the size of the input or worse For instance consider the traveling salesman problem which can be formulated as follows We have a set 01 cn of cities and an n x 71 matrix dzj of nonnegative integers the distance matrix where dij denotes the distance between c and c which means that diz 0 and dij dji for all 7g The problem is to nd a shortest tour of the cities that is a permutation 7T of 1 n so that the cost CW d 1 2 d 2 3 39 39 39 dmimm d7rn7rl is as small as possible minimal One way to solve the problem is to consider all possible tours ie nl permutations Actually since the starting point is irrelevant we need only consider n l tours but this still grows very fast For example when n 40 it turns out that 39 exceeds 1045 a huge number Thus to capture the essence of practically feasible algorithms we must limit our computational devices to run only for a number of steps that is bounded by a polynomial in the length of the input We are led to the de nition of polynomially bounded compu tational models De nition 711 A deterministic Turing machine M is said to be polynomially bounded if there is a polynomial pX so that the following holds For every input 05 E 2 there is no lD IDn so that Do l IDm with n gt px7 Where Do gem is the starting ID A language L Q 2 is polynomially decidable if there is a polynomially bounded Turing machine that accepts L The family of all polynomially decidable languages is denoted by 73 Remark Even though De nition 711 is formulated for Tur ing machines it can also be formulated for other models such as RAM programs The reason is that the conversion of a Turing machine into a RAM program and vice versa produces a program or a machine Whose size is polynomial in the original device The following lemma although trivial is useful Lemma 712 The class 73 is closed under complementation Of course many languages do not belong to 73 One way to obtain such languages is to use a diagonal argument But there are also many natural languages that are not in 73 although this may be very hard to prove for some of these languages 72 More Problems Let us consider a few more problems in order to get a better feeling for the family 73 Recall that a directed graph G is a pair G V E where E Q V x V A pair uv E E is called an edge of G note that u v is allowed Given any two nodes uv E V a path from u to v is any sequence of n 1 edges n 2 0 U7 v17 v17v27 7 M U If n 1 a path from u to v is simply a single edge u A graph G is strongly connected if for every pair u v E V x V there is a path from u to v A closed path or cycle is a path from some node n to itself We will restrict out attention to nite graphs ie graphs V E where V is a nite set De nition 721 Given a graph G an Enlerian cycle is a cycle in G that passes through all the nodes possibly more than once and every edge of G exactly once A Hamiltonian cycle is a cycle that passes through all the nodes exactly once note some edges may not be traversed at all Enlerian Cycle Problem Given a graph G is there an Eulerian cycle in G Hamiltonian Cycle Problem Given a graph G is there an Hamiltonian cycle in G It may come as a surprise that the Eulerian Cycle Problem does have a polynomial time algorithm but that so far not such algorithm is known for the Hamiltonian Cycle Problem The reason Why the Eulerian Cycle Problem is decidable in polynomial time is the following theorem due to Euler Theorem 722 A graph G V7E has an Enlerlan cycle l the following propertles hold 1 The graph G ls strongly connected 2 Every node has the same number of lncomlng and outgo lng edges Proving that properties 1 and 2 hold if G has an Eulerian cycle is fairly easy The converse is harder but not that bad tryl Theorem 722 shows that it is necessary to check Whether a graph is strongly connected This can be done by computing the transitive closure of E 7 which can be done in polynomial time in fact 0n3 Checking property 2 can clearly be done in polynomial time Thus the Eulerian cycle problem is in 73 Unfortunately no theorem analogous to Theorem 722 is know for Hamiltonian cycles Remark We talked about problems being decidable in poly nomial time Obviously this is equivalent to deciding some property of a certain class of objects for example nite graphs Our framework requires that we rst encode these classes of objects as strings or numbers since 73 consists of languages Thus when we say that a property is decidable in polynomial time we are really talking about the encoding of this prop erty as a language Thus we have to be careful about these encodings but it is rare that encodings cause problems 73 Propositional Logic and Satis ability We de ne the syntax and the semantics of propositions in conjunctive normal form CNF The syntax has to do with the legal form of propositions in CNF Such propositions are interpreted as truth functions by assigning truth values to their variables We begin by de ning propositions in CNF Such propositions are constructed from a countable set PV of propositional or boolean variables say PV5L 17952777 using the connectives and or and u negation We de ne a literal or atomlc proposition L as L x or L we also denoted by E Where x 6 PV A clause C is a disjunction of pairwise distinct literals CL1L2Lm Thus a clause may also be Viewed as a nonempty set C L1L2 Lm We also have a special clause the empty clause denoted J or D or lt corresponds to the truth value false A proposition in CNF or boolean formula P is a conjunc tion of pairwise distinct clauses PClCgCn Thus a boolean formula may also be Viewed as a nonempty set PCl7 70n7 but this time the comma is interpreted as conjunction We also allow the proposition J and sometimes the proposition T corresponding to the truth value true For example here is a boolean formula P 951V952V9537 TN952 95 2V9537 EA951 05 1V05 2V95 3 In order to interpret boolean formulae we use truth assign ments We let BOOL FT the set of truth values Where F stands for false and T stands for true A truth assignment or valuation u is any function 1 PV gt BOOL Given a truth assignrnent 11sz gt BOOL we de ne the truth ualue 3X of a literal clause and boolean formula X using the following recursive de nition 1 an F am T 2 W06 3 WE 1105 if 05 6 PV where F if 1195 T and 1105 T if 1105 F ux ifx 6 PV 4 00 F if C is a clause and iff F for all literals L in C otherwise T 5 WP T if P is a boolean formula and iff 301 T for all clauses C in P otherwise F De nition 731 We say that a truth assignment 1 satis es a boolean formula P if WP T In this case we also write vP A boolean formula P is satis able if U l P for some truth assignment 1 otherwise it is unsatis able A boolean formula P is valid or a tautology if U l P for all truth assignments 11 in which case we write EP One should check that the boolean formula P 951V952V9537EV27EV37EV17EVEVEH is unsatis ablei One may think that it is easy to test Whether a proposition is satis able or not Try it it is not that easyl As a matter of fact the satis ability problem testing Whether a boolean formula is satis able also denoted SAT is not known to be in 73 Moreover it is an NP oomplete problem Most people believe that the satis ability problem is not in 73 but a proof still eludes usl Before we explain What is the class N73 let us remark that the satis ability problem for olauses containing at most two literals 2 satis abihty or 2 SAT is solvable in polynomial time The rst step consists in observing that if every clause in P contains at most two literals then we can reduce the prob lem to testing satis ability when every clause has exactly two literals Indeed if P contains some clause 95 then any valuation sat isfying P must make as true Then all clauses containing 05 will be true and we can delete them whereas we can delete T from every clause containing it since T is false Similarly if P contains some clause E then any valuation satisfying P must make 05 false Thus in a nite number of steps either we get the empty clause and P is unsatis able or we get a set of clauses with exactly two literals The number of steps is clearly linear in the number of literals in P For the second step we construct a directed graph from P The nodes of this graph are the literals in P and edges are de ned as follows 1 For every clause TV 3 there is an edge from x to y and an edge from y to T 2 For every clause 95 3 there is an edge from f to y and an edge from y to x 3 For every clause Evy there is an edge from x to y and an edge from y to E Then it can be shown that P is unsatis able iff there is some 05 so that there is a cycle containing 05 and E As a consequence 2 satis ability is in 73 74 The Class N73 Polynomial Reducibil ity ANDCompleteness One will observe that the hard part in trying to solve either the Hamiltonian cycle problem or the satis ability problem SAT is to nd a solution but that checking that a candidate solution is indeed a solution can be done easily in polynomial time This is the essence of problems that can be solved nondeter mistically in polynomial time A solution can be guessed and then checked in polynomial time De nition 741 A nondeterministic Turing machine M is said to be polynomially bounded if there is a polynomial pX so that the following holds For every input 05 E 2 there is no lD IDn so that Do l IDn with n gt px Where Do god is the starting lD A language L Q 2 is mnmdet llllotle p 73 39 quoty decidable if there is a polynomially bounded nondeterministic Turing machine that accepts L The family of all nondeterministic polynomially decidable languages is denoted by N73 Of course we have the inclusion 73 Q N737 but Whether or not we have equality is one of the most famous open problems of theoretical computer science and mathemat ics In fact the question 73 7 N73 is one of the open problems listed by the CLAY lnstitute together with the Poincare con jecture and the Riemann hypothesis among other problems and for Which one mllllon dollar is offered as a rewardl It is easy to check that SAT is in N73 and so is the Hamilto nian cycle problem As we saw in recursion theory where we introduced the notion of many one reducibility in order to compare the degree of dif culty 7 of problems it is useful to introduce the notion of reducibility and the notion of a complete set De nition 742 A function f2 gt 2 is polynomial tlme computable if there is a polynomial pX so that the following holds There is a deterministic Turing machine M computing it so that for every input 05 E 2 there is no 1D 1D so that Do l IDn with n gt px where Do goal is the starting lD Given two languages L1 L2 Q 2 a polynomial reduction from L1 to L2 is a polynomial time computable function f 2 gt 2 so that for all u E 2 u 6 L1 6 L2 For example one can construct a polynomial reduction from the Hamiltonian cycle problem to SAT Remarkably every language in N73 can be reduced to SAT lntuitively if L1 is a hard problem and L1 can be reduced to L2 then L2 is also a hard problem Thus SAT is a hardest problem in N73 Since it is in N73 De nition 743 A language L is AND hard if there is a poly nomial reduction from every language L1 6 N73 to L A lan guage L is AND complete if L 6 N73 and L is NP hard Thus an NP hard language is as hard to decide as any lan guage in N73 The importance of NP oomplete problems stems from the fol lowing theorem Theorem 744 Let L be an AND complete language Then 73 N73 z L e 73 Next we prove a famous theorem of Steve Cook SAT is N73 complete 75 Cook s Theorem SAT is AND Complete Instead of showing directly that SAT is NP complete which is rather complicated we proceed in two steps as suggested by Lewis and Papadimitriou 1 First we de ne a tiling problem adapted from H Wang 1961 by Harry Lewis and we prove that it is N73 complete 2 We show that the tiling problem can be reduced to SAT We are given a nite set 7 t1 tp of tile patterns for short tiles Copies of these tile patterns may be used to tile a rectangle of predetermined size 2s x s s gt 1 However there are constraints on the way that these tiles may be adjacent horizontally and vertically The horizontal constraints are given by a relation H Q T x T and the vertical constraints are given by a relation V Q T x T Thus a tiling system is a triple T T V H as above The problem is then as follows Given any tiling system 7 V H any integer 5 gt 1 and any initial row of tiles 00 of length 25 00 5 5 1 115 15 gtT nd a 25 x s tiling 0 extending 00 ie a function a 5 5 1 115 15gtlt15 gtT so that 1 0m 1 00m for all m y 0 with 5 S m S 5 2 amnam 1n E H for all m y 0 with 5 m 5 1andallnwith1 n s 3 amnamn 1 E V for all m y 0 with 5 m 5andallnwith1 n s 1 For example consider the following tile patterns a a d e 07 C7 079 979 b b C d e c d7c d7d e79 979 b c d e c d ec d7d e79 979 b c d e The horizontal and the vertical constraints are that the letters on adjacent edges rnatch For 5 3 given the bottom row J Cook 395 Theorem Theorem 751 The tiling problem de ned earlier is NP complete Proof Let L Q 2 be any language in N73 and let u be any string in 2 Assume that L is accepted in polynomial time bounded by We show how to construct an instance of the tiling problem TL 5700 Where 5 max2pu and Where the bottom row encodes the starting ID so that u E L iff the tiling prob lem TL 5700 has a solution First note that the problem is indeed in N73 since we have to guess a rectangle of size 252 and that checking that a tiling is legal can indeed be done in 052 Where 5 is the size of the input The idea behind the de nition of the tiles is that in a solu tion of the tiling problem the labels on the horizontal edges between two adjacent rows represent a legal lD upav In a given row the labels on vertical edges of adjacent tiles keep track of the change of state and direction Let F be the tape alphabet of the TM M As before we assume that M signals that it accepts u by halting with the output 1 true Horn M we create the following tiles 1 For every a E F tiles 2 For every a E F the bottom row uses tiles a 1070 Where go is the start state 3 For every instruction p7a7b g 6 6 for every 0 E F tiles LR7 LLB 4 For every instruction p7a7b7L7q E 6 for every 0 E F tiles q7L7 LLL 5 For every halting state p tiles p71 p71 The purpose of tiles of type 5 is to ll the 25 x 5 rectangle if and when M accepts u in strictly less than 5 steps The vertical and the horizontal constraints are that adjacent edges have the same label or no label If u ul uk the initial bottom row 00 of length 25 is B 107 U1 k B Where the tile labeled qo u1 is in position 1 The example below illustrates the construction B B f1 B R R B 10 1 B B 10 1 B 11 11 B 0 pa B B 0 pa B p7R p7R B nb a B It is not hard to check that u ul uk is accepted by M i the tiling problem just constructed has a solution I Remarks 1 The problem becomes harder if we only specify a single tile as input instead of a row of length 25 If 5 is speci ed in binary or any other base but not in tally notation then this tiling problem is actually NEXP completel 2 If we relax the niteness condition and require that the entire upper half plane be tiled ie for every 5 gt 1 there is a solution to the 25 x s tiling problem then the problem is undecidable We nally prove Cook s theorem Theorem 752 Cook 197 The satis ability problem SAT 239s AND complete Proof We reduce the tiling problem to SAT Given a tiling problem7 T7 5 00 we introduce boolean variables xmnh for all m 0 with 5 S m S 5 all n with l S n S 5 and all tiles t E T The intuition is that 05mm T iff tile t occurs in some tiling a so that 0m7n t We de ne the following clauses 1 For all m n in the correct range as above mmntl V mmntg V 39 39 39 V xmntp7 for all p tiles in T This clause states that every position in a is tiled 2 For any two distinct tiles t y t E T for all m n in the correct range7 as above7 Emmi V Emmy This clause states that a position may not be occupied by more than one tile 3 For every pair of tiles 1517 6 T x T H for all m 0 with 5 m 5 1 andalln withl 713 5 Emmi V fml nt This clause enforces the horizontal adjacency constraints 4 For every pair of tiles 1517 6 T x T V for all m 0 with 5 m 5 andallnwithl n s l Emmi V Em n1 7 This clause enforces the vertical adjacency constraints 5 For all m y 0 with 5 S m S 5 mmlaom This clause states that the bottom row is correctly tiled with 00 It is easily checked that the tiling problem has a solution iff the conjunction of the clauses just de ned is satis able Thus SAT is AND complete I We sharpen Theorem 752 to prove that 3 SAT is also N73 cornpletei This is the satis ability problem for clauses con taining at most three literals We know that we can t go further and retain NP cornpleteteness since 2 SAT is in 73 Theorem 753 Cook 197 The satis ability problem 3 SAT 239s AND complete Proof We have to break long clauses 7 OL1vva ie clauses containing k 2 4 literals into clauses with at most three literals in such a way that satis ability is preserved For every long clause create k 3 new boolean variables yl yk3 and the k 3 clauses L1VL2 Vy17MVL3V327 EV L4V337quot397 3H V LH V weigh 673 V L1H V Lie Let C be the conjunction of these clauses We claim that C is satis able iff C is Assume that C is satis able but that C is not Then for every truth assignment 1 we have 111 F for 139 1 k However 0 is satis ed by some 1 and the only way this can happen is that vy1 T to satisfy the rst clause Then 14 F and we must have vy2 T to satisfy the second clause By induction we must have vyk3 T to satisfy the next to the last clause However the last clause is now false a contradiction Thus if C is satis able then so is C Conversely assume that C is satis able If so there is some truth assignment 11 so that 110 T and thus there is a smallest index 139 With 1 S 139 S k so that 11Li T and so 111 F for allj lt Let 11 be the assignment extending 11 de ned so that 11yj F if maxl139 1 S j S k 3 and 11yj T otherwise It is easily checked that 11C T El Another version of 3 SAT can be considered in Which every clause has exactly three literals We will call this the problem exact 3 SAT Theorem 754 Cook 197 The satis ability problem for exact 3 SAT is NP complete Proof A clause of the form L is satis able iff the following four clauses are satis able LVuvUMLvuvULVuvaLvuvv A clause of the form L1 L2 is satis able iff the following two clauses are satis able L1 V L2 VuL1L2 VU Thus we have a reduction of 3 SAT to exact 3 SAT D We now make some remarks on the conversion of propositions to CNF Recall that the set of propositions over the connectives and u is de ned inductively as follows 1 Every propositional letter 05 6 PV is a proposition an atomic proposition 2 If A is a proposition then A is a proposition 3 If A and B are propositions then A B is a proposition 4 If A and B are propositions then A B is a proposition Two propositions A and B are equivalent denoted A E B if U l A iff U l B for all truth assignments 11 It is easy to show that A E B iff the proposition A v B B v A is valid Every proposition A is equivalent to a proposition A in CNF There are several ways of proving this fact One method is algebraic and consists in using the algebraic laws of boolean algebra First one may convert a proposition to negation normal form or nnf A proposition is in nnf if occurrences of u only ap pear in front of propositional variables but not in front of compound propositions Any proposition can be converted to an equivalent one in nnf by using the de Morgan laws IAVB E IAA IB IAB E IAV IB IA E Then a proposition in nnf can be converted to CNF but the question of uniqueness of the CNF is a bit tricky For example the proposition AuAVyV uAmV2 A1 quVyuuxy A2 uVuumy A3 xVy as equivalent propositions in CNFl We can get a unique CNF equivalent to a given proposition if we do the following 1 Let VarA x17 795m be the set of variables occur ring in A 2 De ne a maxterm un t VarA as any disjunction of m pairwise distinct literals formed from VarA and not containing both sorne variable mi and its negation xi 3 Then it can be shown that for any proposition A that is not a tautology there is a unique proposition in CNF equivalent to A whose clauses consist of rnaxterrns formed from VarA The above de nition can yield strange results For instance the CNF of any unsatis able proposition with m distinct vari ables is the conjunction of all of its 2m rnaxterrnsl The above notion does not cope well with rninirnality For example according to the above the CNF of A u mVy uxy should be A1uxyuuxy There are also propositions such that any equivalent propo sition in CNF has size exponential in terms of the original proposition Here is such an example A 1 2 V 3 4 V V2n1 27 Observe that it is in DNF We will prove a little later that any CNF for A contains 2 occurrences of variables A nice method to convert a proposition in nnf to CNF is to construct a tree Whose nodes are labeled with sets of proposi tions using the following Gentzen style rules RA QA PAQLA and HQA PVQLA Where A stands for any set of propositions even empty and the comma stands for union Thus it is assumed that P Q E A in the rst case and that P Q A in the second case Since we interpret a set P of propositions as a disjunction a valuation 1 satis es F iff it satis es some proposition in F Observe that a valuation 1 satis es the conclusion of a rule i it sastis es both premises in the rst case and the single premise in the second case Using these rules we can build a nite tree whose leaves are labeled with sets of literals By the above observation a valuation 1 satis es the proposi tion labeling the root of the tree i it satis es all the proposi tions labeling the leaves of the tree But then a CNF for the original proposition A in nnf at the root of the tree is the conjunction of the clauses appearing as the leaves of the tree We may exclude the clauses that are tautologies and we may discover in the process that A is a tautology when all leaves are tautologies Going back to our bad 7 proposition A by induction we see that any tree for A has 2 leaves However it should be noted that for any proposition A we can construct in polynomial time a formula 141 in CNF so that A is satis able iff A is satis able by creating new vari ables We proceed recursively The trick is that we replace C1ACmD1Dn by 01VyCmVyDlvyDny where the Ci s and the Dj s are clauses and y is a new variable It can be shown that the number of new variables required is at most quadratic in the size of A Warning In general the proposition A is not equivalent to the proposition A Rules for dealing for u can also be created In this case we work with pairs of sets of propositions F gt A where the propositions in F are interpreted oonjunotively and the propositions in A are interpreted disjunctively We obtain a sound and complete proof system for propo sitional logio a Gentzen style 7 proof system see Gallier s Logic for Computer Science 65 The Recursion Theorem The recursion Theorem due to Kleene is a fundamental result in recursion theory Theorem 651 Recursion Theorem Version 1 Let p0ltp1 be any acceptable indeccing of the partial recursive functions For every total re cursive function f there is some n such that Pn pfn39 The recursion Theorem can be strengthened as follows Theorem 652 Recursion Theorem Version 2 Let p0ltp1 be any acceptable indeccing of the partial recursive functions There is a total recursive function h such that for all z E N if pm is total then Pwth WWW A third version of the recursion Theorem is given below Theorem 653 Recursion Theorem Version 3 For all n 2 1 there is a total recursive function h ofn 1 arguments such that for all z E N if pm is a total recursive function ofn 1 arguments then pLPachCZEC1217 13n5121513n phmm1mmn7 for all1n N As a rst application of the recursion theorem we can show that there is an index n such that on is the constant function with output n Loosely speaking on prints its own name Let f be the recursive function such that ay I for all my 6 N By the s rn n Theorern7 there is a recursive function 9 such that pgmy f 9571 96 for all Ly E N By the recursion Theorern 6517 there is some n such that Pym Pm the constant function with value 71 As a second application7 we get a very short proof of Rice7s Theorem Let C be such that PC 7amp0 and PC N and letj 6 PC and k E NiPC De ne the function f as follows 7 lf Pc f k ifzePC lf PC is recursive then f is recursive By the recursion Theorem 651 there is some n such that WW ltan But then we have HEPC iff 130 by de nition of f and thus ltpfm 7g pru a contradiction Hence PC is not recursive As a third application we have the following Lemma Lemma 654 Let C be a set of partial recurser functions and let A Nlltpz O The set A is not reducible to its complement Z The recursion Theorem can also be used to show that functions de ned by recursive de nitions other than primitive recursion are partial recursive This is the case for the function known as Aekermarm s function7 de ned recursively as follows f07yy17 fz170fltz717 f961iy 1 f967f96 179 lt can be shown that this function is not primitive recursive lntuitively7 it outgrows all primitive recursive functions However f is recursive but this is not so obvious We can use the recursion Theorem to prove that f is recursive Consider the following de nition by cases 90170711 11 17 977397z 17 puni39uolv 7 17 977397z 17y puni39uOly 7 punivn7 Clearly g is partial recursive By the s m n Theorem there is a recursive function h such that mmww 90179679 By the recursion Theorem there is an m such that won ltPm Therefore the partial recursive function ltpmzy satis es the de nition of Ackermann7s function We showed in a previous Section that pmzy is a total function and thus Ackermann7s function is a total recursive function Hence the recursion Theorem justi es the use of certain recursive de ni tions However note that there are some recursive de nition that are only satis ed by the completely unde ned function In the next Section we prove the extended Rice Theorem 66 Extended Rice Theorem The extended Rice Theorem characterizes the sets of partial recursive func 1 Extended Rice tions 0 such that PC is re First7 we need to discuss a way of indexing the partial recursive functions that have a nite domain Using the uniform projection function l l7 we de ne the primitive recursive function F such that FWW H 17H1 17H2gtv We also de ne the sequence of partial functions P071317 as follows Fy71 if0ltFy andy ltl l1z17 Pmy l unde ned otherw1se Lemma 661 Every P1 is a partial recursive function with nite domain and every partial recursive function with nite domain is equal to some Pm The easy part of the extended Rice Theorem is the following lemma Recall that given any two partial functions f A a B and gA a B7 we say that g eatends f iff f Q 97 which means that 9a is de ned Whenever u is de ned7 and if so7 9a Lemma 662 Let C be a set ofpartial recursive functions If there is an re set A such that pm 6 C i there is some y E A such that pm ecctends Py then PC x l pm 6 C is re Proof Lemma 662 can be restated as PC 6 A7 Py g Extended Rice If A is ernpty7 so is PC and PC is re Otherwise7 let f be a recursive function such that A rangef Let 7 be the following partial recursive function 102 1112 if PfltH2ltzgtgt H1ltzgtv unde ned otherwise It is clear that PC rangew TQ see that z is partial recursive write1M2 as follow 39H z if V10 g HICfCHZ CZD W5 FUCMJW gt 0 13 unde ned otherwise To establish the converse of Lemma 6627 we need two Lemmas Lemma 663 If PC is 7quot6 and p E C then there is some Py Q p such that Pg 6 0 As a corollary of Lemma 6637 we note that TOTAL is not re Lemma 664 If PC is re p E C and p Q 7 where 7 is a partial recursive function then 7 E 0 Observe that Lemma 664 yields a new proof that TOTAL is not re Finally7 we can prove the extended Rice Theorem Theorem 665 Ea tended Rice Theorem The set PC is 7quot6 i there is Extended Rio in its set A such that mEC i 3y APyQltpm Proof Let PC d0mltpi Using the s rn n Theorern7 there is a recursive function k such that My Py for all y E N De ne the re set A such that A d0mltpi o 96A iff saiky39gti iii 13960 Next using Lemma 61 and Lemma 164 in is easy to see that W e 0 HT 3y 6 APy g m 67 Creative and Productive Sets In this section7 we discuss some special sets that have important applica tions in logic creative and productive sets We and The concepts to be described are illustrated by the following situation Assume that i Wm Q K for some z E N We claim that z E F 7 Wm lndeed7 if z E lVm7 then MW is de ned7 and by de nition of K we get z F a contradiction Therefore7 pmz must be unde ned7 that is7 xefin The above situation can be generalized as follows De nition 671 A set A is productive iff there is a total recursive func tion f such that if ngA then f AilVm for all m E N The function f is called the productive function of A A set A is creative if it is re and if its complement A is productive As we just showed7 K is creative and F is productive The following facts are immediate conequences of the de nition 1 A productive set is not re 2 A creative set is not recursive Creative and productive sets arise in logic The set of theorems of a logical theory is often creative For example7 the set of theorems in Peano7s arithmetic is creative This yields incomplete ness results Lemma 672 If a set A is productive then it has an in nite 7quot6 subset Another important property of productive sets is the following Lemma 673 If a set A is productive then F S A Using Lemma 673 the following results can be ShoWn Lemma 674 The following factshold I IfA is productive and A g B then B is pmdu ctiua A is amatiize A is equivalent to K 3 A is creative i 39A is camplete Chapter 5 Universal RAM Programs and Undecidability 0f the Halting Problem 51 Pairing Functions Pairing functions are used to encode pairs of integers into sin gle integers or more generally nite sequences of integers into single integers We begin by exhibiting a bijective pairing function J N2 gt N The function J has the graph partially showed below g 3 7 1 4 8 The function J corresponds to a certain way of enumerating pairs of integers Note that the value of 05 is constant along each diagonal and consequently we have Jm7y12myx7 xyxy12x2 xy23xygt27 that is May 05 y2 3m y2 Let K N gt N and L N gt N be the projection functions onto the axes that is the unique functions such that KJab a and LJab b for all a b E N Clearly J is primitive recursive since it is given by a polyno mial It is not hard to prove that J is injective and surjective and that it is strictly monotonic in each argument which means that for all xxyy E N if x lt 05 then Jxy lt Jxy and ify lt y then Jmy lt Jxy The projection functions can be computed explicitly although this is a bit tricky We only need to observe that by monotonicity of J x 3 1015711 and y S May and thus Inina g zEy g zJx7y z and 132 niny S zEx S zJxy The pairing function J x y is also denoted as x y and K and L are also denoted as H1 and H2 By induction we can de ne bijeotions between N and N for all n 2 1 We let 21 Z7 95171 2l2 lt95172gt7 and x17 7xn7 mnlgtnl 17 7 xru xnlgtgtn Note that 9517 7n7xnlgtnl 9517 9527 in1gtngt We can de ne a uniform projection function H with the fol lowing property if z x1 xngt with n 2 2 then HQ 11 z x for all 239 where l g 239 S n The function H is de ned by cases as follows HO 2 0 for alliZO z forallz39ZO z ingz39gl HQ 73 H2z for alli22 Hinz if0 iltn Hin1z H1Hnnz ifz39n H2Hnn ifz39 gt n 7 By a previous exercise this is a legitimate primitive recursive de nition Some basic properties of H are given as exercises In particular the following properties are easily shown a lt00gtn0 ltx0gtltx7070gtn b H07n7z Hl7n7z and Hz nz iZnand alln726N 11017172 for all c ltHlnz nnzgtn z for all n 2 1 and all z E N d Hz nz S 2 for all 71172 E N e There is a primitive recursive function Large such that Hin 1Largen 1 z for 71172 E N As a rst application we observe that we need only consider partial recursive functions of a single argument lndeed let 0 N gt N be a partial recursive function of n 2 2 arguments Let n7 Z7 39 39 39 7n7 n7 for all z E N Then is a partial recursive function of a single argument and 0 can be recovered from E since 90x1xn Eaxl Thus using lt gt and H as coding and decoding functions we can restrict our attention to functions of a single argument It can be shown that there exist coding and decoding func tions between 2 and a1 and that partial recursive func tions over 2 can be recoded as partial recursive functions over 01 Since a1 is isomorphic to N this shows that we can restrict out attention to functions de ned over N 52 Coding of RAM Programs In this Section we present a speci c encoding of RAM pro grams which allows us to treat programs as integers Encoding programs as integers also allows us to have programs that take other programs as input and we obtain a universal program Universal programs have the property that given two inputs the rst one being the code of a program and the second one an input data the universal program simulates the actions of the encoded program on the input data A coding scheme is also called an indexing or a Godel num bering in honor to Godel who invented this technique Fiom results of the previous Chapter without loss of general ity we can restrict out attention to RAM programs computing partial functions of one argument over N Furthermore we only need the following kinds of instructions each instruction being coded as shown below Because we are only considering functions over N there is only one kind of instruction of the form add and jmp and add increments by l the contents of the speci ed register Rj Ni add Rj code 1 i 30 Ni tail Rj code lt2 ij 0 Ni continue code lt3i10gt Ni Rj jmp de code lt4ij k Ni Rj jmp Nkb code 5 i jkgt Recall that a conditional jump causes a jump to the closest address N k above or below i Rj is nonzero and if Rj is null the next instruction is executed We assume that all lines in a RAM program are numbered This is always feasible by labeling unnamed instructions with a new and unused line number The code of an instruction I is denoted as 1 To simplify the notation we introduce the following decoding primitive recur sive functions Typ Nam Reg and Jmp de ned as follows Typx H17 47 x7 Namx H2 4 x Regm H3 4 05 Jmpx H4 4 The functions yield the type line number register name and line number jumped to if any for an instruction coded by x We can de ne the primitive recursive predicate INST such that lNSTx holds iff 05 codes an instruction First we need the connective 2 implies de ned such that P 3 Q iff P v Q Then lNSTx holds iff 1 S Typ 95 S 5l A l1 S Pnegt lA lTpr S 3 D Jmpm lA lTypm 3 D RegCr 1l VA Program are coded as follows If P is a RAM program corn posed of the n instructions 1 In the code of P denoted as P is P n111ngt Recall from a previous exercise that n7 117 n7 117 7 We de ne the primitive recursive functions Ln Pg and Line such that Lnx H12x Pgx H27 27 x7 Linez39x HQ Lnx Pgx The function Ln yields the length of the program the number of instructions Pg yields the sequence of instructions in the program really a code for the sequence and Linez39 05 yields the code of the 2th instruction in the program If 05 does not code a program there is no need to interpret these functions The primitive recursive predicate FROG is de ned such that PROGQ holds iff 05 codes a program Thus PROGQ holds if each line codes an instruction each jump has an instruction to jump to and the last instruction is a continue Thus PROGQ holds iff W 3 Lnxz39 Z 1 I INSTLinez39 TypLineLnxx 3 TypLinez39 4 I Elj S 139 1U Z 1 NarnLinejx JmpLinez39x TypLinez39x 5 I Elj S Lnxj gt z39NarnLinejx JrnpLinez39xm Note that we have used the fact proved as an exercise that if f is a primitive recursive function and P is a primitive recursive predicate then Elm S fyPx is prirnitive recursive We are now ready to prove a fundamental result in the theory of algorithms This result points out some of the limitations of the notion of algorithm Theorem 521 Undecidability of the halting problem There is no RAM program P which halts for all inputs and has the following property when started with input as in register R1 and with input i in register R2 the other registers being set to zero 1 P halts with output 1 i i codes a program that eventually halts when started on input as all other registers set to zero 2 P halts with output 0 in R1 i i codes a program that runs foreuer when started on input as in R1 all other registers set to zero 3 If i does not code a program then P halts with output 2 in R2 Proof Assume that P is such a RAM program and let Q be the following program R2 lt R1 P N1 continue R1 jmp Nla continue The program Q can be translated into a program using only instructions of type 1 2 3 4 5 described previously and let q be the code of this program Let us see What happens if we run this program on input q in R1 all other registers set to zero Just after execution of the assignment R2 lt R1 the program P is started with q in both R1 and R2 Since P is supposed to halt for all inputs it eventually halts with output 0 or 1 in R1 If P halts with output 1 in R1 then Q goes into an in nite loop while if P halts with output 0 in R1 then Q halts But then because of the de nition of P we see that P says that Q halts when started on input q iff Q loops forever on input q and that Q loops forever on input q iff Q halts on input q a contradiction Therefore P cannot exist I If we identify the notion of algorithm with that of a RAM pro gram which halts for all inputs the above theorem says that there is no algorithm for deciding whether a RAM program eventually halts for a given input We say that the halting problem for RAM programs is unde cidable or unsolvable The above theorem also implies that the halting problem for Turing machines is undecidable Indeed if we had an algorithm for solving the halting problem for Turing machines we could solve the halting problem for RAM programs as follows rst apply the algorithm for trans lating a RAM program into an equivalent Turing machine and then apply the algorithm solving the halting problem for Tur ing machines The argument if typical in computability theory and is called a reducibility argumen 77 Our next goal is to de ne a primitive recursive function that describes the computation of RAM programs Assume that we have a RAM program P using 71 registers R17 7 Rn Whose contents are denoted as 717 7731 We can code 71 rn into a single integer T17 7 Conversely every integer x can be viewed as coding the con tents of R1 Rn by taking the sequence H1nx Hnn Actually it is not necessary to know 11 the number of registers if we make the following observation RegLinez39x S Linez39x S Pgx for all 205 6 N Then if 05 codes a program then R1 R05 certainly include all the registers in the program Also note that from a previous exercise T1rn00gtT1rn0gt We now de ne the primitive recursive functions Nextline Nextcont and Comp describing the computation of RAM programs De nition 522 Let 01 code a program and let 1 be such that l S 1 S Lnx The following functions are de ned 1 Nextline139 x y is the number of the next instruction to be executed after executing the 1th instruction in the pro gram coded by 05 Where the contents of the registers is coded by y 2 Nextcont17x7y is the code of the contents of the reg isters after executing the 1th instruction in the program coded by 05 Where the contents of the registers is coded by y 3 Compxy7m 17z7 Where 1 and z are de ned such that after running the program coded by x for 171 steps Where the initial contents of the program registers are coded by y the next instruction to be executed has line number 17 and z is the code of the current contents of the registers Lemma 523 The functions Nextline Nextcont and Comp are primitive recursive We can now reprove that every RAM computable function is partial recursive Indeed assume that 05 codes a program P We de ne the partial function End so that for all x y Where 05 codes a program and 3 codes the contents of its registers Endm y is the number of steps for which the computation runs before halting if it halts If the program does not halt then Endx y is unde ned Since Endx y minmH1Compx y m Lnx End is a partial recursive function However in general End is not a total function If 0 is the partial recursive function computed by the program P coded by x then we have 9011 H1H2Comp957 17 0 EDdW 17 0W Observe that 0 is written in the form 0 g 0 min f for some primitive recursive functions f and g We can also exhibit a partial recursive function which enumer ates all the unary partial recursive functions It is a universal function Abusing the notation slightly we will write 90957 y for 90ltx ygt7 viewing 0 as a function of two arguments however 0 is really a function of a single argument We de ne the function 901mm as follows H1ltH2Comprr7 y 0gt EndCr y 0gtgtgtgtgt 9017140621 ifPROGx unde ned otherwise The function 901mm is a partial recursive function with the fol lowing property For every x coding a RAM prograrn P for every input 3 Wunivltx7 101 the value of the partial recursive function 90 computed by the RAM program P coded by x If 05 does not code a program then goumvx y is unde ned for all 3 By Lemma 482 901mm is not recursive lndeed being an enumerating function for the partial recursive functions it is an enumerating function for the total recursive functions and thus it cannot be recursive Being a partial function saves us from a contradiction The existence of the function 907mm leads us to the notion of an indexing of the RAM programs We can de ne a listing of the RAM programs as follows If 05 codes a program that is if PROGQ holds and P is the program that 05 codes we call this program P the 05th RAM program and denote it as PI If 05 does not code a program we let PI be the program that diverges for every input N1 add R1 N1 R1 jmp N1a N1 continue Therefore in all cases PI stands for the 05th RAM program Thus we have a listing of RAM programs P0 P1 132133 such that every RAM program of the re stricted type considered here appears in the list exactly once except for the in nite loop 7 program In particular note that 907mm being a partial recursive func tion it is computed by some RAM program UNIV that has a code um v and is the program Puniv in the list Having an indexing of the RAM programs we also have an indexing of the partial recursive functions De nition 524 For every integer as Z 0 we let PI be the RAM program coded by x as de ned earlier and 90 be the partial recursive function computed by P1 Remark Kleene used the notation for the partial recursive function coded by 05 Due to the potential confusion with singleton sets we follow Rogers and use the notation pm The existence of the universal function scumv is suf ciently important to be recorded in the following Lemma Lemma 525 For the indexing ofRAMprograms de ned ear lier there is a universal partial recursiue function 907mm such that for all 053 6 N if 90 is the partial recursiue function computed by P1 then 901y Wunivltltm7 The program UNIV computing 901mm can be Viewed as an m terpreter for RAM programs By giving the universal program UNIV the program 7 05 and the data 7 3 we get the result of executing program PI on input 3 We can View the RAM model as a stored program computer By Theorem 521 and Lemma 525 the halting problem for the single program UNIV is undecidable Otherwise the halt ing problem for RAM programs would be decidable a contra diction It should be noted that the program UNIV can actually be written with a certain amount of pain The object of the next Section is to show the existence of Kleene s T predicate This will yield another important nor mal form In addition the T predicate is a basic tool in re cursion theory 53 Kleene s TPredicate In Section 52 we have encoded programs The idea of this Section is to also encode computations of RAM programs Assume that 05 codes a program that y is some input not a code and that 2 codes a computation of PI on input 3 The predicate Tm y z is de ned as follows Tx y 2 holds iff 05 codes a RAM program 3 is an input and 2 codes a halting computation of PI on input 3 We will show that T is primitive recursive First we need to encode computations We say that 2 codes a computation of length n 2 1 if z 11 2717y0gt7lt 17y1gt7 7ltln7yngtgt7 Where each i is the physical location not the line number of the next instruction to be executed and each 3 codes the contents of the registers just before execution of the instruc tion at the location z39j Thus 111 Lnx and in is irrele vant Writing the de nition of T is a little simpler if we let in Lnx 1 Also yo codes the initial contents of the registers that is yo y 0 for some input 3 We let Lnz 1112 De nition 531 The T predicate is the primitive recursive predicate de ned as follows Tmyz iff PROGQ and Lnz Z 3 and W s Lnltzgt 30 s j 3 Nextline 1Hj 2 Lnz 27057 H2Hj 27Lnz7 H1ltHltj 3 Lnltzgt7 2 and Nextcont 1 j 27L11Z7Z77H2Hj 2Lnz H2010 3 Lnltzgt7 2 and H1HLnz 1Lnz Lnm and H1H2Lnz 1 and y H1H2H27 Lnz7 and H2H2H2Lnz 0 The reader can verify that Tx y 2 holds iff 05 codes a RAM program 3 is an input and 2 codes a halting computation of PI on input 3 In order to extract the output of PI from Z we de ne the primitive recursive function Res as follows Resz H1H2HLnz Lnz Using the T predicate we get the so called Kleene normal form Theorem 532 Kleene Normal Form Using the indexing of the partial recursive functions de ned earlier we have my Resimin 2Tm7 17 2 where Tmyz and Res are primitive recursive TePredica re Note that the universal function 901mm can be de ned by goumvm y Resmin 2Tx y There is another important property of the partial recursive functions namely that composition is effective We need two auxiliary primitive recursive functions The function Conprogs creates the code of the program obtained by concatenating the programs PI and Py and for 139 Z 2 Cumclrz39 is the code of the program which clears registers R2 7 Rd To get Cumclr we can use the function c1rz39 such that c1rz39 is the code of the program N1 tail Rz39 N1 Rz jmp Nla N continue We leave it as an exercise to prove that Cir Conprogs and Cumclr are primitive recursive Theorem 533 There is a primitive recursive function e such that 10017y 101 O
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'