Popular in Course
Popular in Computer Information Technology
verified elite notetaker
This 123 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 Staff in Fall. Since its upload, it has received 9 views. For similar materials see /class/215379/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
63 Recursively Enumerable Sets Consider the set A x E N 901a is de ned Where a E N is any xed natural number By Rice s Theorem A is not recursive check this We claim that A is the range of a recursive function 9 For this we use the T predicate We produce a function which is actually primitive recursive First note that A is nonempty Why and let me be any index in A We de ne g by primitive recursion as follows 07 Since this type of argument is new it is helpful to explain informally What 9 does For every input 05 the function 9 tries nitely many steps of a computation on input a of some partial recursive function The computation is given by lbw and the partial function is given by H1x Since H1 and H2 are projection functions when x ranges over N both H1 and ll x also range over N Such a process is called a dovetailmg computation Therefore all computations on input a for all partial recursive functions Will be tried and the indices of the partial recursive functions converging on input a will be selected De nition 631 A subset X of N is recursively enumerable iff either X 7 or X is the range of some total recursive function Similarly a subset X of 2 is recursively enumerable iff either X 7 or X is the range of some total recursive function For short a recursively enumerable set is also called an re set The following Lemma relates recursive sets and recur sively enumerable sets Lemma 632 A set A is recursive i both A and its comple mentA are recursively enumerable Proof Assume that A is recursive Then it is trivial that its complement is also recursive Hence we only have to show that a recursive set is recursively enumerable The empty set is recursively enumerable by de nition Other wise let 3 E A be any element Then the function f de ned such that i x iffCAx 17 i 3 iff CA05 0 for all x E N is recursive and has range A Conversely assume that both A and A are recursively enu merable If either A or A is empty then A is recursive Otherwise let A fN and A 9N for some recursive functions f and 9 We de ne the function CA as follows OA1 iffminylfym V M frlx 0 otherwise The function CA lists A and A in parallel waiting to see whether 05 turns up in A or in A Note that 05 must eventually turn up either in A or in A so that CA is a total recursive function I Our next goal is to show that the recursively enurnerable sets can be given several equivalent de nitions We will often ab breviate recursively enurnerable as he Lemma 633 For any subset A ofN the following properties are equivalent 1 A is empty or A is the range of a primitive recursive function 2 A is recursively enumerable 3 A is the range of a partial recursive function 4 A is the domain of a partial recursive function More intuitive proofs of the implications 3 gt 4 and 4 gt 1 can be given Assume that A y and that A rangeg where g is a partial recursive function Assume that g is computed by a RAM program P To compute x we start computing the sequence 907917 looking for x If 05 turns up as say 901 then we output 11 Otherwise the computation diverges Hence the domain of f is the range of 9 Assume now that A is the domain of some partial recursive function g and that g is computed by some Turing machine M We construct another Turing machine performing the follow ing steps 0 Do one step of the computation of 90 71 Do 71 1 steps of the computation of 90 Do 71 steps of the computation of 91 Do 2 steps of the computation of 9n 1 Do 1 step of the computation of 9n During this process whenever the computation of some 9m halts we output m In this fashion we will enumerate the domain of g and since we have constructed a Turing machine that halts for every input we have a total recursive function The following Lemma can easily be shown using the proof technique of Lemma 633 Lemma 634 The followlhg propertles hold 1 There ls a recurslue functlon h such that 707194900 d0m10hz for all x E N 2 There ls a recurslue functlon k such that d0mlt rangewkw and 901m ls total recurslue for all x E N such that d0mlt 7W Using Lemma 633 we can prove that K is an re set Indeed we have K d0mf Where punivx7x for all x E N The set K0 95 y 901y converges is also an re set since K0 d0mg Where 92 punivH1Z7 H2Z7 which is partial recursive The sets K and K0 are examples of re sets that are not recursive We can now prove that there are sets that are not re Lemma 635 For any indexing of the partial recursive func tions the complement F of the set K x E N 90105 converges is not recursively ehumerable Proof If F was recursively enurnerable since K is also re cusively enurnerable by Lemma 632 the set K would be recursive a contradiction III The sets F and F0 are examples of sets that are not re This shows that the re sets are not closed under cornplernen tation However we leave it as an exercise to prove that the re sets are closed under union and intersection We will prove later on that TOTAL is not re This is rather unpleasant Indeed this means that there is no way of effectively listing all algorithms all total recursive functions Hence in a certain sense the concept of partial recursive func tion procedure is more natural than the concept of a total recursive function algorithm The next two Lemmas give other characterizations of the re sets and of the recursive sets Lemma 636 The following properties hold I A set A is re i either it is nite or it is the range of an injectiue recursiue function 2 A setA is re if either it is empty or it is the range of a monotonic partial recursiue function 3 A set A is re i there is a Turing machine M such that for all x E N M halts on x i x E A Lemma 637 A set A is recusiue i either it is nite or it is the range of a strictly increasing recursiue function Another important result relating the concept of partial re cursive function and that of an re set is given below Theorem 638 For every unary partial function f the fol lowing properties are equivalent 1 f is partial recursive 2 The set W l If E d0mf is r e Using our indexing of the partial recursive functions and Lemma 633 we obtain an indexing of the re sets De nition 639 For any acceptable indexing 900901 of the partial recursive functions we de ne the enumeration W0 W1 of the re sets by setting WI d0mltpx We now describe a technique for showing that certain sets are re but not recursive or complements of re sets that are not recursive or not re or neither re nor the complement of an re set This technique is known as reducibilz39ty 64 Reducibility and Complete Sets We already used the notion of reducibility in the proof of madmanWand 7 Lemma 625 to show that TOTAL is not recursive De nition 641 A set A is many one reducible to a set B if there is a total recursive function f such that 614 iff fxeB for all x E A We write A S B and for short we say that A is reducible to B Lemma 642 Let ABC be subsets ofN 0r 2 The fol lowing properties hold 1fASB andBSC thenASC 21fA g B thenAS E 3 fA S B and B is re then A is re 4 HA 3 B and A is not re then B is not re 5 HA 3 B and B is recursive then A is recursiue 6 fA S B and A is not recursiue then B is not recursiue Another important concept is the concept of a complete set V Reducibility and De nition 643 An re set A is complete wrt many one reductblllty iff every re set B is reducible to A ie B S A For simplicity we will often say complete for complete wrt many one reductblllty Theorem 644 The following properties hold 1 fA is complete B is re and A S B then B is com plete 2 K0 is complete 3 K0 is reducible to K As a corollary of Theorem 644 the set K is also complete De nition 645 Two sets A and B have the same degree of orare 139 i AgBandBSA I L39l394 7 Since K and K0 are both complete they have the same degree of unsolvability We will now investigate the reducibility and equivalence of various sets Recall that TOTAL x E N pm is total We de ne EMPTY and FlNlTE as follows EMPTY x E N pm is unde ned for all input FlNlTE x E N 901 has a nite domain l7 Refluglziliy king Then FINITE x E N pr has an in nite domain so that EMPTY C FINITE and TOTAL C FINITE Lemma 646 We have K0 3 EMPTY Lemma 647 The following properties hold 1 EMPTY is not he 2 W is we 3 F and EMPTY are equivalent 4 W is complete V Reducibility and Lemma 648 The following properties hold 1 TOTAL and TOTAL are not he 2 FINITE and FINITE are not he Horn Lemma 648 we have TOTAL 3 FINITE It turns out that FINITE 3 TOTAL and TOTAL and FINITE are equivalent Lemma 649 The sets TOTAL and FINITE are equivalent We now turn to the recursion Theorem V Reducibility and 224 CHAPTER 3 CON TEXTFREE LANGUAGES AND PDA S 313 Pushdown Automata We have seen that the regular languages are exactly the languages accepted by DFA s or NFA s The context free languages are exactly the languages accepted by push down autornata for short PDA s However although there are two versions of PDA s deterministic and non deterrninistic contrary to the fact that every NFA can be converted to a DFA nondeterrninistic PDA s are strictly rnore poweful than deterrninistic PDA s DPDA s ln deed there are context free languages that cannot be ac cepted by DPDA s Thus the natural rnachine model for the context free lan guages is nondeterrninistic and for this reason we just use the abbreviation FDA as opposed to NPDA 313 PUSHDOWN AUTOMATA 225 We adopt a de nition of a FDA in which the pushdown store or stack must not be empty for a move to take place Other authors allow PDA s to make move when the stack is empty Novices seem to be confused by such moves and this is why we do not allow moves with an empty stack lntuitively a PDA consists of an input tape a nondeter ministic nite state control and a stack Given any set X possibly in nite let 73fmX be the set of all nite subsets of X 226 CHAPTER 3 CON TEXTFREE LANGUAGES AND PDA S De nition 3131 A pashdown automaton is a 7 tuple M Q ZF6q0 Z0 F where c Q is a nite set of states 0 Z is a nite input alphabet o F is a nite pashdown store or stack alphabet 0 go E Q is the start state or initial state 0 Z0 E F is the initial stack symbol or bottom marker 0 F g Q is the set of nal 07 accepting states 0 6 Q X 2U X F gt 73fmQ X F is the transition function A transition is of the form qy E 6paZ where pq E Q Z E F 7 E F and a E E U A transition of the form qyy E 6p e Z is called an e ti ansition or e move 313 PUSHDOWN AUTOMATA 227 The way a PDA operates is explained in terms of In stantaneous Descriptions for short lD s lntuitively an Instantaneous Description is a snapshot of the PDA An 1D is a triple of the form pu0z E Q X 2 gtltF The idea is that p is the current state u is the remaining input and oz represents the stack It is important to note that we use the convention that the leftmost symbol in oz represents the topmost stack symbol Given a PDA M we de ne a relation l M between pairs of lD s This is very similar to the derivation relation gtG associated with a context free grammar 228 CHAPTER 3 CON TEXTFREE LANGUAGES AND PDA S lntuitively a PDA scans the input tape symbol by symbol from left to right making moves that cause a Change of state an update to the stack but only at the top and either advancing the reading head to the next symbol or not moving the reading head during an e move De nition 3132 Given a PDA M Q7 27 F7 67 qu Z07 F7 the relation l M is de ned as follows 1 For any move qy E 61 a Z where pq E Q Z E F a E Z for every ID of the form new Zoz we have pew Zoz l M qvyoz 2 For any move qy E 61 6 Z where pq E Q Z E F for every ID of the form 19 u Zoz we have 197 U7 Za ZW Q7 U7 As usual l Xi is the transitive Closure of l M and PM is the re exive and transitive Closure of l M 313 PUSHDOWN AUTOMATA 229 A move of the form p cm Zoz l M qu oz where a E E U 6 is called a pop move A move on a real input symbol a E 2 causes this input symbol to be consumed and the reading head advances to the next input symbol On the other hand during an e move the reading head stays put When 197 Oz H14 qav B we say that we have a computation There are several equivalent ways of de ning acceptance by a PDA 230 CHAPTER 3 CONTEXTFREE LANGUAGES AND PDA S De nition 3133 Given a PDA M Q7 27 F7 67 qu Z07 F7 the following languages are de ned 1 TM w E 2 l g0wZ0 H14 fe0z where f E F and oz E F We say that TM is the language accepted by M by nal state 2 NM w E 2 l g0wZ0 H14 gee where q E Q We say that N M is the language accepted by M by empty stack 3 MM w e 2 l w 20gt Hal 1366 where f E F We say that LM is the language accepted by M by nal state and empty stack In all cases note that the input 11 must be consumed entirely 313 PUSHDOWN AUTOMATA 231 The following lemma shows that the acceptance mode does not matter for PDA s As we will see shortly it does matter for DPDAs Lemma 3134 For any language L the following facts hold 1IfL TM for some PDA M then L LM for some PDA M 2 IfL NM for some PDA M then L LM for some PDA M 3 IfL LM for some PDA M then L TM for some PDA M 4 IfL LM for some PDA M then L NM for some PDA M In View of lemma 3134 the three acceptance modes T N L are equivalent 232 CHAPTER 3 CONTEXTFREE LANGUAGES AND PDA S The following PDA accepts the language La bnln21 by empty stack Q 172 F Z070 1aE 61aZ0 Laa E 61aa 6 E 61ba 2 26 E 62ba 313 PUSHDOWN AUTOMATA 233 The following PDA accepts the language La bnln21 by nal state and also by empty stack Q 172737 F Z07 Ava F 1714 E 61CL Z0 1aA E 61aA 234 CHAPTER 3 CONTEXTFREE LANGUAGES AND PDA S DPDA s are de ned as follows De nition 3135 A PDA M Q7 27 F767QO7 Z07 is a deterministic PDA for short DPDA iff the fol lowing conditions hold for all p Z E Q X F either 1 l6paZl1for all a E Z and 6peZ Q or 2 61 a Z Q for all a E Z and l6p e Zl 1 A DPDA operates in realtime iff it has no e transitions 313 PUSHDOWN AUTOMATA 235 It turns out that for DPDA s the most general acceptance mode is by nal state Indeed there are language that can only be accepted deterrninistically as TM The language Lambnlm2n21 is such an example The problem is that W is a pre x of all strings amb with m 2 n 2 2 A language L is a deterministic contervi fi ee language iff L TM for some DPDA M It is easily shown that if L NM or L for some DPDA M then L TM for some DPDA M easily constructed from M 236 CHAPTER 3 CONTEXTFREE LANGUAGES AND PDA S A PDA is unambiguous iff for every 11 E 2 there is at most one computation QO7 wv Z0 IBM where ID is an accepting lD There are context free languages that are not accepted by any DPDA For example it can be shown that the languages L1a bn in Z 1 U anbzn l n 21 and L2 wwR l w E aablikla are not accepted by any DPDA Also note that unambiguous grammars for these languages can be easily given We now show that every context free language is accepted by a PDA 314 FROM CONTEXTFREE GRAMMARS TO PDA S 237 314 From ContextFree Grammars To PDA s We show how a PDA can be easily constructed from a context free grammar Although simple the construction is not practical for parsing purposes since the resulting PDA is horribly nondeterministic Given a context free grammar G V Z P S we de ne a one state PDA M as follows QqOFVqoSZoSF For every rule A gt oz E P there is a transition 90700 E 6q0eA For every a E 2 there is a transition QO7 6 E 6Q07 0397 a The intuition is that a computation of M mimics a left most derivation in G One might say that we have a popexpand PDA 238 CHAPTER 3 CONTEXTFREE LANGUAGES AND PDA S Lemma 3141 Given any contact free grammar G VZPS the PDA M just described accepts LG by empty stack z39e LG Proof The following two claims are proved by induction Claim 1 For all 1b 6 2 and all a 6 NW u e if S uoz then 907167175 H 90711700 Claim 2 For all 1m E 2 and all oz E V if QO7 uvv QO7 vv OK then S l gt uoz D We now Show how a PDA can be converted to a context free grammar 315 FROM PDA S TO CONTEXTFREE GRAMMARS 239 315 From PDA s To ContextFree Grammars The construction of a context free grammar from a PDA is not really dif cult but it is quite messy The construc tion is simpli ed if we rst convert a PDA to an equivalent PDA such that for every move g y E 61 a Z where a E E U 6 we have M S 2 In some sense we form a kind of FDA in Chomsky Norrnal Forrn Lemma 3151 Giuen any PDA M Q727F767QO7Z07F7 another PDA M QC 2 F 6 qt Z67 F can be constructed such that LM LM and the following conditions hold I There is a one to one correspondence between ac cepting computations ofM and M 2 IfM has no e moues then M has no e moues If M is unambiguous then M is unambiguous 3 For allp E Q all a E E U 6 and all Z E F if an E 81 a Z then q 96 and hi 3 2 240 CHAPTER 3 CON TEXTFREE LANGUAGES AND PDA S The crucial point of the construction is that accepting computations of a PDA accepting by empty stack and nal state can be decomposed into subcomputations of the form pew Z04 qvoz where for every intermediate H 811 5 we have 5 yoz for some 7 7A 6 The nonterminals of the grammar constructed from the PDA M are triples of the form 19 Z q such that p7 u Q7 67 for some u E 2 Given a PDA M Q7 27 F767QO7 Z07 satisfying the conditions of lemma 3151 we construct a context free grammar G V Z P S as follows 315 FROM PDA S TO CON TEXTFREE GRAMMARS 241 VlpZ7ql lpQEQZ FUZUS7 where S is a new symbol and the productions are de ned as follows for allp q E Q all a E EU 6 all X Y Z E P we have 1S gteEPifq0EF 2 S gt a E P if f e E 6q0aZoar1d f E F 3S gt apXf E P for every f E F if X E 590707Z0 4 S gt ap X 88Y f E P for every f E F for every 8 E Q if p7XY E 5qo a Z0 5 p7 Z4 E a E P if q 6 E 6p7a Z and p go 6 19 Z 8 gt aqX8 E P for everys E Q ifqX E 519 a Z andpqo pvzvtl gt aleXvsllsvyvtl E Pa for every Sat E Q7 E 6p7avz and 7 QU 242 CHAPTER 3 CONTEXTFREE LANGUAGES AND PDA S Lemma 3152 Giuen any PDA M Q7 27 F7 67 QO7 Z07 satisfying the conditions of lemma 315 the conterct free grammar G V 213 S constructed as aboue generates MM ie LG Furthermore G is unambiguous ijj M is unambiguous Proof We have to prove that LGwez l qovwvzo 067676 U QOEF For this the following claim is proved by induction 315 FROM PDA S TO CON TEXTFREE GRAMMARS 243 Claim For all pq E Q all Z E F all k 2 1 and all in E 2 rial gtw iff p7w7Ztqe6 Using the claim it is possible to prove that LG El In view of lemmas 3141 and 3152 the family of context free languages is exactly the family of languages accepted by PDA s It is harder to give a grammatical character ization of the deterministic context free languages One method is to use Knuth LRk grammars Another characterization can be given in terms of strict deterministic grammars due to Harrison and Havel 244 CHAPTER 3 CON TEXTFREE LANGUAGES AND PDA S 316 The ChomskySchutzenberger Theorem Unfortunately there is no Characterization of the context free languages analogous to the Characterization of the regular languages in terms of Closure properties However there is a famous theorern due to Chomsky and Sehutzenberger showing that every context free language can be obtained from a special language the Dyck set in terms of hornornorphisrns inverse hornornorphisrns and intersection with the regular languages De nition 3161 Given the alphabet 22 a b j de ne the relation 2 on E as follows For all 1m E 2 use iff Engezg uca5y 1vy or u mbhy v 33y Let 2 be the reflexive and transitive Closure of 2 and let D2 w E E l w 2 6 This is the Dyck set on two letters It is not hard to prove that D2 is context free 316 THE CHOMSKYSCHUTZENBERGER THEOREM 245 Theorem 3162 Chomsky Schatzcnbcrgcr For every PDA M Q ZF6qo Z0 F there is a regular language R and two homomorphisms g h such that we fag1a m R Observe that Theorem 3162 yields another proof of the fact that the language accepted a PDA is context free Indeed the context free languages are closed under ho rnornorphisrns inverse hornornorphisrns intersection with the regular languages and D2 is context free From the characterization of a transducers in terms of ho rnornorphisrns inverse hornornorphisrns and intersection with regular languages we deduce that every context free language is the image of D2 under some a transduction Chapter 4 RAM Programs Turing Machines and the Partial Recursive Functions 41 Partial Functions and RAM Programs We de ne an abstract machine model for computing functions f2gtltgtltE gtE TL Where E a1ak is some input alphabet Numerical functions f N gt N can be Viewed as functions de ned over the one letter alphabet a1 using the bijection m n gt a3 Let us recall the de nition of a partial function A binary relation R Q A x B between two sets A and B is functional iff for all x E A and y z E B xy E R and 052 6 R implies that y z A partial function is a triple f A G B Where A and B are arbitrary sets possibly empty and G is a functional relation possibly empty between A and B called the graph of f Hence a partial function is a functional relation such that every argument has at most one image under f The graph of a function f is denoted as graph When no confusion can arise a function f and its graph are usually identi ed A partial function f A G B is often denoted as f A gt B artial Fun The domain d0mf of a partial function f A G B is the set d0mfxEAElyEB 133 6G For every element x E domf the unique element 3 E B such that my E graphf is denoted as We say that converges also denoted as i If x E A and 05 domf we say that diverges also denoted as T lntuitively if a function is partial it does not return any out put for any input not in its domain This corresponds to an in nite cornputation A partial function f A gt B is a total function iff d0mf A It is customary to call a total function simply a function artial Fun We now de ne a model of computation know as the RAM programs or Post machines RAM programs are written in a sort of assembly language involving simple instructions ma nipulating strings stored into registers Every RAM program uses a xed and nite number of registers denoted as R1 7 RP with no limitation on the size of strings held in the registers RAM programs can be de ned either in owchart form or in linear form Since the linear form is more convenient for coding purposes we present RAM programs in linear form A RAM program P in linear form consists of a nite se quence of instructions using a nite number of registers R1 7 Rp Functions Instructions may optionally be labeled with line numbers de noted by N1 Nq It is neither mandatory to label all instructions nor to use distinct line numbersl Thus the same line number can be used in more than one line As we will see later on this makes it easier to concatenate two different programs without performing a renumbering of line numbers Every instruction has four elds not necessarily all used The main eld is the opcode Functions De nition 411 RAM programs are constructed from seven types of instructions shown below N addj Y 2 N tail Y 3 N clr Y 4 N Y lt X 5a N Jmp Nla 5b N jmp Nlb 61a N Y jmp Nla 6jb N Y jmp Nlb 7 N continue An instruction of type 1 concatenates the letter aj to the right of the string held by register Y 1 S j S The effect is the assignment Y Ya An instruction of type 2 deletes the leftmost letter of the string held by the register Y This corresponds to the function tail de ned such that mike e tailaju u The effect is the assignment Y tailY An instruction of type 3 clears register Y ie sets its value to the empty string 6 The effect is the assignment Ye An instruction of type 4 assigns the value of register X to register Y The effect is the assignment YX An instruction of type 5a or 5b is an unconditional jump The effect of 5a is to jump to the closest line number N 1 occurring above the instruction being executed and the effect of 5b is to jump to the closest line number N1 occurring below the instruction being executed An instruction of type Gja or Gjb is a conditional jump Let head be the function de ned as follows heade e7 headmju aj The effect of Gja is to jump to the closest line number N1 occurring above the instruction being executed iff headY aj else to execute the next instruction the one immediately following the instruction being executed The effect of Gjb is to jump to the closest line number N1 occurring below the instruction being executed iff headY aj else to execute the next instruction When computing over N instructions of type Gjb jump to the closest N1 above or below iff Y is nonnull artial Fun An instruction of type 7 is a no op ie the registers are unaffected If there is a next instruction then it is executed else the program stops Obviously a program is syntactically correct only if certain conditions hold De nition 412 A RAM program P is a nite sequence of instructions as in De nition 411 and satisfying the following conditions 1 For every jump instruction conditional or not the line number to he jumped to must exist in P 2 The last instruction of a RAM program is a continue The reason for allowing multiple occurences of line numbers is to make it easier to concatenate programs without having to perform a renaming of line numbers The technical choice of jumping to the closest address N 1 above or below comes from the fact that it is easy to search up or down using primitive recursion as we will see later on It is fairly obvious that linear RAM programs can be repre sented in owchart form and that the two models are equiv alent We will not worry about this in this Chapter For the purpose of computing a function f 2 x x 2 gt 2 using a RAM program P we assume that P has at least 71 registers called input registers and that these registers R1 7 Rn are initialized with the input values of the function f We also assume that the output is returned in register R1 The following RAM program oonoatenates two strings x1 and x2 held in registers R1 and R2 R3 lt R1 R4 lt R2 N 0 R4 jmpa N 1b R4 jmpb N 2b jmp N 3b N 1 adda R3 tail R4 jmp N Go N2 add R3 tail R4 jmp N Go N3 R1 lt R3 continue Since 2 a b for more clarity we wrote jmpa instead of jmpl jmpb instead of jmp27 adda instead of add17 and add instead of addgi De nition 413 A RAM program P computes the partial function 0 27 gt 2 if the following conditions hold For every in put xl xn E 23 having initialized the input registers R1 Rn with x1 xn the program eventually halts iff 90051 xn converges and if and when P halts the value of R1 is equal to 90051 xn A partial function 0 is RAM computable iff it is computed by some RAM program For example the following program computes the erase func tion E de ned such that E u e for all u E 2 clr R1 continue artial Fun 39alFuncth 39 The following program computes the jth successor function Sj de ned such that Sju no for all u E 2 addj continue The following program with n input variables computes the projection function de ned such that B u1un ui wheren217and1 i nz R1 lt 1 continue Note that Pl1 is the identity function Having a programming language we would like to know how powerful it is that is we would like to know what kind of functions are RAM computable At rst glance RAM programs don t do much but this is not so Indeed we will see shortly that the class of RAM computable functions is quite extensive One way of getting new programs from previous ones is via composition Another one is by primitive recursion We will investigate these constructions after introducing another model of computation Turing machines Remarkably the classes of partial functions computed by RAM programs and by Turing machines are identical This is the class of partial recursiue function This class can be given several other de nitions We will present the de nition of the so called a recursiue functions due to Kleene artial Fun The following Lemma will be needed to simplify the encoding of RAM programs as numbers Lemma 414 Every RAM program can be converted to an equivalent program only using the following type of instruc tions N addj Y 2 N tail Y 61a N Y jmpj Nla Gjb N Y jmp Nlb 7 N continue The proof is fairly simple For example instructions of the form Rt lt Rj can be eliminated by tranferring the contents of Rj in reverse order into an auxiliary register Rk and then by transferring the contents of Rk in reverse order into Ri 42 De nition of a Turing Machine We de ne a Turing machine model for computing functions 152 x xE gtE z where E a1 aN is some input alphabet We only consider deterministic Turing machines A Turing machine also uses a tape alphabet P such that E Q P The tape alphabet contains some special symbol B E the blank In this model a Turing machine uses a single tape This tape can be Viewed as a string over F The tape is both an input tape and a storage mechanism Symbols on the tape can be overwritten and the tape can grow either on the left or on the right There is a read write head pointing to some symbol on the tape Unlike Pushdown autornata or NFA s the readwrite head can move left or right De nition 421 A deterministic Turing machine or TM M is a sextuple M K EFLR6q0 Where 0 K is a nite set of states 0 E is a nite input alphabet o F is a nite tape alphabet st 2 Q P K m P and with blank B g E 0 go 6 K is the start state or initial state 0 6 is the transition function a nite set of quintuples 6QKgtltFgtltPgtltLRgtltK such that for all p a E K x F there is at most one triple bmq E F x LR x K such that pabmq E 6 l Definition ufa A quintuple p7a7b7m7q E 6 is called an instruction It is also denoted as 1w gt b m7 q The effect of an instruction is to switch from state p to state q overwrite the symbol currently scanned a with b and move the read write head either left or right according to m 43 Computations of Turing Machines To explain how a Turing machine works we describe its action on Instantaneous descriptions We take advantage of the fact that K m P to de ne instantaneous descriptions De nition 431 Given a Turing machine M K727 P7 L7 R767q07 an instantaneous description for short an ID is a nonempty string in WKI that is a string of the form upav Where u7v E Fp K andaE F The intuition is that an ID upav describes a snapshot of a TM in the current state p Whose tape contains the string uav and with the read write head pointing to the symbol a Thus in upav the state p is just to the left of the symbol presently scanned by the read write head We explain how a TM works by showing how it acts on lD s De nition 432 Given a Turing machine M K727 P7 L7 R767q07 the yield relation or compute relation l is a binary relation de ned on the set of lD s as follows For any two ID s ID1 and IDg we have ID1 I IDg iff either 1 pa b R7q E 6 and either mpu ta tiun a ID1 upacv c E F and IDg uchv or b ID1 upa and IDg uqu or 2 pa b Lg G 6 and either a ID1 ucpav c E F and IDg uqcbv or b ID1pav and IDg quv Note how the tape is extended by one blank after the rightmost symbol in case 1b and by one blank before the leftmost symbol in case As usual7 we let l denote the transitive closure of l and we let l denote the re exive and transitive closure of l We can now explain how a Turing function computes a partial function 152 x XXV gt3 TL Since we allow functions taking 71 Z 1 input strings we as surne that F contains the special delirniter not in 27 used to separate the various input strings It is convenient to assume that a Turing machine cleans up 7 its tape when it halts before returning its output For this we will de ne proper lD s umpu ta tiuns De nition 433 Given a Turing machine M K727 P7 L7 R767q07 Where F contains some delimiter not in E in addition to the blank B a starting D is of the form q0w17w27 7wn Where w17wn E 2 and n 2 2 or qow with w 6 2 or JOB A blocking 0r halting D is an ID upav such that there are no instructions p7a b7m7 q E 6 for any b7m7q E F x LR x K A proper D is a halting ID of the form kawBl Where w E 2 and lat Z 0 with 12 1 when w e Computation sequences are de ned as follows De nition 434 Given a Turing machine M K727 P7 L7 R767q07 a computation sequence or computation is a nite or in nite sequence of lD s ID071D17IDi71Di1 such that ID2 l DZ1 for all t Z 0 A computation sequence halts i it is a nite sequence of lD s7 so that Do l IDn and IDn is a halting ID A computation sequence dtuerges if it is an in nite sequence of lD s We now explain how a Turing machine computes a partial function De nition 435 A Turing machine M K727FLR76q0 computes the partial function 152 x gtltE gtE iff the following conditions hold 1 For every wl wn E 2 given the starting lD DO 1010171027 7wn or qow with w 6 2 or qoB the computation sequence of M from Do halts in a proper lD iff fw1 71071 is de ned 2 If fw1 71071 is de ned then M halts in a proper ID of the form IDn kafwl7 7wnBh7 which means that it computes the right value A function f over 2 is Turing computable iff it is computed by some Turing machine M Note that by l the TM M may halt in an improper ID in Which case fw1 wn must be unde ned This corresponds to the fact that we only accept to retrieve the output of a computation if the TM has cleaned up its tape ie7 produced a proper lD In particular interrnediate calculations have to be erased before halting Example K q07Q17Q27Q3 E Cub F a719 B The instructions in 6 are 107B gtB7R7CI37 107a gtb7R7CI17 107b W7R7q17 Q17a gtbR7q17 Q17b W7R7917 Q17B gtB7L7q27 Q27a gta7L7CI27 I27b gtbL7Q27 q2B gtBRq3 The reader can easily verify that this machine exchanges the as and b s in a string For example on input w aaababb the output is bbbabaa 44 RAMcomputable functions are Turing computable Turing machines can simulate RAM programs and as a result we have the following Theorem Theorem 441 Every RAM computable function is Turing computable Furthermore given a RAM program P we can e ecttuely construct a Turing machine M computing the same function The idea of the proof is to represent the contents of the regis ters R1 Rp on the Turing machine tape by the string r1r2 rp7 Where is a special marker and rt represents the string held by Rt We also use Lemma 414 to reduce the number of instructions to be dealt with The Turing machine M is built of blocks each block sirnu lating the effect of some instruction of the program P The details are a bit tedious and can be found in the notes or in Machtey and Young 45 Turingcomputable functions are RAM computable RAM programs can also simulate Turing machines Theorem 451 Every Turing computable function is RAM computable Furthermore given a Turing machine M one can e ectiuely construct a RAM program P computing the some function The idea of the proof is to design a RAM program containing an encoding of the current ID of the Turing machine M in register R1 and to use other registers R2 R3 to simulate the effect of executing an instruction of M by updating the ID of M in R1 The details are tedious and can be found in the notes Another proof can be obtained by proving that the class of Turing computable functions coincides with the class of par tial recursive functions Indeed it turns out that both RAM programs and Turing machines compute precisely the class of partial recursive functions First we de ne the primitive recursive functions 46 The Primitive Recursive Functions The class of primitive recursive functions is de ned in terms of base functions and closure operations De nition 461 Let E a1 aN The base functions over X are the following functions 1 The emse function E de ned such that e for all w E 2 2 For every j7 l S j 3 N7 the j successor function 317 de ned such that 31 way7 for all w E 2 3 The projection functions Pi de ned such that DZ 101 wn wi I for everyn Z 1 everyz39 1 S 139 S nandfora117o017wn E 2 Note that Pl1 is the identity function on 2 Projection func tions can be used to perrnute the arguments of another func tion A crucial closure operation is extended composition De nition 462 Let 2 a1 aN For any function 922 x gtlt2 gt2 1 and any m functions hi2 gtlt x 2 gt2 z the composition of g and the h2 is the function f2 gtlt x2 gt2 denoted as g o h hm such that fw1wn gh1w1wnhmw1wn for all w17wn E 2 As an example f g 0 P2271312 is such that 1017102 9w27w1 Another crucial closure operation is primitive recursion De nition 463 Let E a1 aN For any function 922 x XE gtE mil Where m 2 2 and any N functions hi22 gtlt x 2 gtE m1 the function f2 gtlt xE gtE z is de ned by primitive recursion from g and h hN if flt 7w27 710771 gltw27 7wm7 fua17w27 7wm h1u7fu7w27 7wm7w27 7wm7 fuaN7w27 710771 hNu7fu7w27 7wm7w27 7wm7 for all u7w27wm E 2 When m l for some xed w E 2 we have fltua1 h1u7 fu7 fua N hNu7 fu7 for all u E 2 For numerical functions ie when E a1 the scheme of primitive recursion is simpler flt07x27 7xm gx27 7xm7 fxlx2xm h1xfxx27xmx2795m for all x7x27xm E N The successor function S is the function 305 xl Addition multiplication exponentiation and super exponentiation can be de ned by primitive recursion as follows being a bit loose we should use some projections rexp0 m l add0 n n addm 171 Saddm 11 mult0 n 0 multm 171 addmultm n n rexpm 171 multrexpm n n expm n Temp 0 13221312 supexp0 n l supexpm 171 6951901 supexpmn As an example over a b the following function g 2 x 2 gt 2 is de ned by primitive recursion 96711 1311007 901 v Sl 0 1323017 gu 1071 J39Theprimmw quot Where 1 S 139 S N It is easily veri ed that guv vu Then f g 0 computes the concatenation function ie fuv uv De nition 464 Let E a1 aN The class of primi tive recursive functions is the smallest class of functions over 2 which contains the base functions and is closed under com position and primitive recursion We leave as an exercise to show that every primitive recursive function is a total function The class of primitive recursive functions may not seem very big but it contains all the total functions that we would ever want to compute Although it is rather tedious to prove the following theorem can be shown Theorem 465 For an alphabetZ a1 aN euery prim itiue recursiue function is Turing computable The best way to prove the above theorem is to use the com putation model of RAM programs Indeed it was shown in Theorem 441 that every Turing machine can simulate a RAM program It is also rather easy to show that the primitive recursive func tions are RAM computable In order to de ne new functions it is also useful to use predi cates De nition 466 An n ary predicate P over 2 is any sub set of We write that a tuple x1 xn satis es P as 051705 E P or as Px1xn The characteristic function of a predicate P is the function Op 23 gt a1 de ned by 7 a1 iffP0517795n Cp177n 6 not Pltx177n A predicate P is primitive recursive iff its characteristic func tion C p is primitive recursive We leave to the reader the obvious adaptation of the the notion of primitive recursive predicate to functions de ned over N In this case7 0 plays the role of e and 1 plays the role of a1 It is easily shown that if P and Q are primitive recursive predi cates over 27 then PVQ PAQ and P are also primitive recursive As an exercise the reader may want to prove that the predi cate de ned over N primen iff n is a prime number is a primitive recursive pred icate For any xed k 2 l the function ordk n exponent of the kth prime in the prime factoriza tion of n is a primitive recursive function We can also de ne functions by cases Lemma 467 If P1 7 Pn are pairwise disjoint primitive re cursive predicates which means that B Q Pj for all i y j and f1 7 fn1 are primitive recursive functions the function 9 de ned below is also primitive recursive f1 E 0 P1 T 9 m a 237 Pn fn1 otherwise writing T for x17 It is also useful to have bounded quanti cation and bounded minimization De nition 468 If P is an n l ary predicate then the bounded existential predicate Ely0513 y 7 holds iff some pre x y of 05 makes Py true The bounded uniuersal predicate VyxPy holds iff every pre x y of 05 makes Py true Lemma 469 fP is an n l ary primitive recursiue pred icate then EIyxPy and VyxPy are also primitive re cursiue predicates As an application we can show that the equality predicate u 11 is primitive recursive De nition 4610 If P is an n 1 ary predicate then the bounded minimization of P min yxPy is the function de ned such that min yxPy is the shortest pre x of x such that Py if such a 3 exists anal otherwise The bounded maximization of P max yx P 32 is the func tion de ned such that max yx P 32 is the longest pre x of x such that Py if such a 3 exists xal otherwise Lemma 4611 If P is an n 1 ary primitive recursive predicate then min yx Py and max ysc Py are prim itive recursive functions So far the primitive recursive functions do not yield all the Turing computable functions In order to get a larger class of functions we need the closure operation known as minimiza tion 47 The Partial Recursive Functions The operation of minimization sometimes called minimaliza tion is de ned as follows De nition 471 Let E a1 aN For any function 922 x XXV gtE ml Where m 2 0 for every j 1 S j S N the function 192 x gtltE gtE7 z is de ned by minimization over aj from 9 if the following conditions hold for all wl wm E 2 1 fw1 wm is de ned iff there is some n 2 0 such that ga w1 wm is de ned for all p 0 S p S n and 9ay7w17 u7wm 6 2 When fw1 wm is de ned fw1 wm a7 Where n is such that 9a7j77w1 wm e and 9ag7w17 7wm for everyp 0 3193 n 1 We also write fw1wm mmjuguw1wm e Note When fw1 wm is de ned fw1 wm a Where n is the smallest integer such that condition 1 holds It is very important to require that all the values gm wl wm be de ned for all p 0 S p S 11 when de ning fw1 wm Failure to do so allows non computable functions Minimization can be viewed as an abstract version of a While loop u z 6 While guw1 wm y e do u uaj endwhile let fw17 wm u Remark Kleene used the u notation fltwl7 7wm lu julgu7wl7 7wm 47 actually its numerical form fltx17 7mIl l xgx7x17quot 7xm07 The class of partial computable functions is de ned as follows De nition 472 Let E a1 aN The class of partial recursive functions is the smallest class of functions over 2 Which contains the base functions and is closed under corn position primitive recursion7 and minimization The class of recursive functions is the subset of the class of partial recursive functions consisting of functions de ned for every input One of the major results of computability theory is the follow ing theorem Theorem 473 For an alphabetE a1 aN every par tial recursive function is Turing computable Conversely ev ery Turing computable function is a partial recursive function Similarly the class of recursive functions is equal to the class of Turing computable functions that halt in a proper ID for every input To prove that every partial recursive function is indeed Turing computable since by Theorem 441 every Turing machine can simulate a RAM program7 the simplest thing to do is to show that every partial recursive function is RAM computable For the converse one can show that given a Turing machine there is a primitive recursive function describing how to go from one ID to the next Then minimization is used to guess whether a computation halts The proof shows that every partial recursive function needs minimization at most once The characterization of the recursive functions in terms of TM s follows easily There are recursive functions that are not primitive recursive Such an example is given by Ackermann s function Ackermann s function A recursive function which is not prirn itive recursive A07 y y 1 Am 10Altx71gt Ax 1 y 1 1405 Ax 173 It can be shown that 140 95 x 1 1411 95 x 27 A2 x 7 n3 A3 05 21 3 and with A4 0 16 3 13 1 For example A4 1 216 3 1443 2215 3 Actually it is not so obvious that A is a total function This can be shown by induction using the lexicographic ordering j on N x N which is de ned as follows m7n j mh iff either mm andnn or m lt m or mmandnltnl We write mm lt m v when mm j m and mn7 m We prove that Amn is de ned for all mm 6 N x N by complete induction over the lexicographic ordering on N x N 1n the base case mn 00 and since A0n n 1 we have A0 0 1 and A0 0 is de ned For m n y 0 0 the induction hypothesis is that Am 71 is de ned for all m 71 lt m We need to conclude that Am n is de ned The Partial If m 0 since A0n 71 1 A0n is de ned Ifm y 0 and n 0 since m 17 lt m7 07 by the induction hypothesis Am 1 1 is de ned but Am 0 Am 11 and thus Am 0 is de ned lfm y 0 and n y 0 since mn 1 lt 77171 by the induction hypothesis Am n 1 is de ned Since m 1Amn 1 lt mn by the induction hypothesis Am 1 Am n 1 is de ned But Am n Am 1 Am n 1 and thus Am n is de ned Thus Am n is de ned for all m n E N x N It is possible to show that A is a recursive function although the quickest way to prove it requires some fancy Inachinery the recursion theorern Proving that A is not prirnitive recursive is harder We can also deal with languages 48 Recursively Enumerable Languages and Recursive Languages We de ne the recursively enumerable languages and the recur sive languages We assume that the TM s under consideration have a tape alphabet containing the special symbols 0 and 1 De nition 481 Let E a1 aN A language L Q 2 is recursively enumerable for short an re set iff there is some TM M such that for every w E L M halts in a proper ID with the output 1 and for every w E L either M halts in a proper ID with the output 0 or it runs forever A language L Q 2 is recursive iff there is some TM M such that for every w E L M halts in a proper ID with the output 1 and for every w L M halts in a proper ID with the output 0 Thus given a recursively enurnerable language L for some w E L it is possible that a TM accepting L runs forever on input w On the other hand for a recursive language L a TM accepting L always halts in a proper lD When dealing with languages it is often useful to consider nondetermmistic Turing machines Such machines are de ned just like deterrninistic Turing rnachines except that their transition function 6 is just a nite set of quintuples 6 KgtltFgtltPgtltLRgtltK with no particular extra condition l Recursivey It can be shown that every nondeterministic Turing machine can be simulated by a deterministic Turing machine and thus nondeterministic Turing machines also accept the class of re sets It can be shown that a recursively enumerable language is the range of some recursive function It can also be shown that a language L is recursive iff both L and its complement are recursively enumerable There are recursively enumerable languages that are not recursive Turing machines were invented by Turing around 1935 The primitive recursive functions were known to Hilbert circa 1890 Godel formalized their de nition in 1929 The partial recursive functions were de ned by Kleene around 1934 Church also introduced the A calculus as a model of computation around 1934 Other models Post systems Markov systems The equivalence of the various models of computation was shown around 193536 RAM programs were only de ned around 1963 A further study of the partial recursive functions requires the notions of pairing functions and of universal functions or uni versal Turing machines First we prove the following lemma showing that restricting ourselves to total functions is too limiting Let f be any set of total functions that contains the base func tions and is closed under composition and primitive recursion and thus 7 contains all the primitive recursive functions We say that a function f 2 x 2 gt 2 is universal for the one argument functions in 7 iff for every function g 2 gt 2 in 7 there is some n E N such that a u 9W for all u E 2 Lemma 482 For any countable set of total functions con taining the base functions and closed under composition and primitive recursion if f is a universal function for the func tions 922 gt 2 in 7 then f 7 Thus either a universal function for J is partial or it is not in f Proof Assume that the universal function f is in 7 Let g be the function such that m fltaluhugta1 for all u E 2 We claim that g E 7 It it enough to prove that the function h such that W all is primitive recursive which is easily shown Then because f is universal there is some m such that 90 Nil u for all u E 2 Letting u a3 we get 9W1 a al faf7afa17 a contradiction D 68 The Post Correspondence Problem The Post correspondence problem due to Emil Post is another undecid able problem that turns out to be a very helpful tool for proving problems in logic or in formal language theory to be undecidable Let E be an alphabet with at least two letters An instance of the Post Correspondence problem for short7 PCP is given by two sequences U 1117 7um and V 11 mm of strings uhoi E 2 The problem is to nd whether there is a nite sequence 23917 7 with 23 E 17 7771 for j1o7 sothat uilui2 uip Wily 1 Equivalently7 an instance of the PCP is a sequence of pairs For example7 consider the following problem abab aaabbb aab ba ab aa ababaaa 7 bb 7 baab 7 baa 7 ba 7 a 39 There is a solution for the string 1234556 abab aaabbb aab ba ab ab aa ababaaa bb baab baa ba ba 1 We are beginning to suspect that this is a hard problem lndleedl7 it is undecidablel Theorem 681 Emil Post 1946 The Post correspondence problem is ahdeeldable provided that the alphabet E has at least two symbols There are several ways of proving Theorem 6817 but the strategy is more or less the same Reduce the halting problem to the PCP7 by encoding sequences of lD7s as partial solutions of the PCP For instance7 this can be done for RAM programs The rst step is to show that every RAM program can be simulated by a single register RAM program Then7 the halting problem for RAM programs with one register is reduced to the PCP using the fact that only four kinds of instructions are needed A proof along these lines was given by Dana Scott As an application7 we prove the following result Theorem 682 It is undecidable whether a contact free grammar is am biguous Proof We reduce the PCP to the ambiguity problem for CFG7S Given any instance U 1117um and V 1117vm of the PCP7 let 017 cm be m new symbols7 and consider the following languages LUui1 uipCip Ci1 l1 32537717 13739 31071021 LVUi1quot39UipCipquot Cill1 j m71 j 1071021h and LUV LUULv We can easily construct a CFG7 Gav generating LUy The productions are l The Post S SU S gt SV SU uiSUCi SU gt uici SV gt UiSVCi SV 150139 It is easily seen that the PCP for U7 V has a solution iff LU LV 7E Q iff G is ambiguous Remark As a corollary7 we also obtain the following result It is unde cidable for arbitrary context free grammars G1 and G2 whether LG1 LG2 U see also Theorem 692 69 Undecidable Properties of Languages Greibach s Theorem Recall that the computations of a Turing Machine M can be described in terms of instantaneous descriptions upav We can encode computations IDOhIDlh FIB halting in a proper ID as the language LM consisting all of strings w0wfw2w 39 39 w2kw klv or wowfw2w 39 39 w2k72w k71w2k7 where k 2 0 we is a starting 1D w F w for all 2 with 0 S 2 lt 2k 1 and 202k is proper halting ID in the rst case 0 S 2 lt 2k and 20 is proper halting ID in the second case The language LM turns out to be the intersection of two context free lan guages LR and L de ned as follows 1 The strings in L0 are of the form M w0w w2w 39 39 39w2kw k1 or R R R wow1 w2w3 39 39 w2k72w2k71w2k7 where LUgl39 h rum1 for all 239 2 07 and Lng is a proper halting ID in the second case A D V The strings in IllI are of the form w0w w2w 39 39 w2kw k1 or w0wfw2w 39 39 w2k72w k1w2k7 where rum1 h rum2 for all 239 2 07 we is a starting lD7 and w2kl is a proper halting 1D in the rst case Theorem 691 Given any Turing machine M the languages Lg arzd L are eorztert free arzd LM Lg IllI Proof We can construct PDA7s accepting LR and Lil It is easily checked that LM L34 7 Lid 1 As a corollary7 we obtain the following undecidability result Theorem 692 It is undecidable for arbitrary eorzteCUt free grammars G1 arzd G2 whether LG1 LG2 Q Proof We can reduce the problem of deciding whether a partial recursive function is unde ned everywhere to the above problem By Rice7s theorem7 the rst problem is undecidable However7 this problem is equivalent to deciding whether a Turing machine never halts in a proper lD By Theorem 6917 the languages L and Lil are context free Thus7 we can construct context free grammars G1 and G2 so that L LG1 and Lil LG2 Then7 M never halts in a proper 1D iff LM Q iff by Theorem 6917 LM LG1 LG2 Q I Given a Turing machine M7 the language LM is de ned over the alphabet A TU Q U The following fact is also useful to prove undecidability Theorem 693 Given my Turing machine M the language A iLM is eontemt free Proof One can easily check that the conditions for not belonging to LM can be checked by a PDA El As a corollary we obtain Theorem 694 Given my contest free grammar G V E P S it is undecidable whether LG 2 Proof We can reduce the problem of deciding whether a Turing machine never halts in a proper 1D to the above problem lndeed given M by Theorem 693 the language A 7 LM is context free Thus there is a CFG G so that LG A 7 LM However M never halts in a proper lD iff LM Q iff LG A El As a consequence we also obtain the following Theorem 695 Given my two contact free grammar G1 and G2 and my regular language R the following facts hold 1 LG1 2 LG1 Q LltG2gt is undecidable 3 UGO 4 R Q LG2 is undecidable LG2 is undecidable R is undecidable In contrast to 47 the property LG1 Q R is decidable We conclude with a nice theorem of S Greibach7 which is a sort of version of Rice7s theorem for families of languages Let L be a countable family of languages We assume that there is a coding function 0 gt N and that this function can be extended to code the regular languages all alphabets are subsets of some given countably in nite set We also assume that is effectively closed under union and concatenation with regular languages This means that given any two languages L1 and L2 in L we have L1UL2 6 L and CLl U L2 is given by a recursive function of CLl and CLg7 and that for every regular language R7 we have L1R 6 RL1 6 and CRLl and CLlR are recursive functions of CR and C14 Given any language L Q 2 and any string to E 2 we de ne Lw by Lwu 2 lquL Theorem 696 Greibach Let be a countable family of languages that is e ectiuely closed under union and concatenation with the regular lan guages and assume that the problem L 2 is undecidable for L 6 and any given su ciently large alphabet 2 Let P be any nontrivial property of languages that is true for the regular languages and so that if PL holds then PLa also holds for any letter a Then P is undecidable for A Proof Since P is nontrivial for there is some L0 6 so that PL0 is false Let 2 be large enough so that LO Q 2 and the problem L 2 is undecidable for L E L We show that given any L 6 with L Q 2 we can construct a language L1 6 so that L 2 iff PL1 holds Thus the problem L 2 for L 6 reduces to property P for and since for 2 big enough the rst problem is undecidable so is the second For any L 6 with L Q 2 let L1 L02 U 2L Since is effectively closed under union and concatenation with the regular languages we have L1 6 L If L 2 then L1 22 a regular language and thus PL1 holds since P holds for the regular languages Conversely we would like to prove that if L 7E 2 then PL1 is false Since L 31 2 there is some w L But then L1 LU L0 Since P is preserved under quotient by a single letter by a trivial induction if PL1 holds then PL0 also holds However PL0 is false so PL1 must be false Thus we proved that L 2 iff PL1 holds as claimed El Greibach7s theorern can be used to show that it is undecidable whether a context free grammar generates a regular language It can also be used to show that it is undecidable whether a context free language is inherently arnbiguous
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'