Page 1 Lecture 6 Page 2 Lecture 6 The Acceptance Problem for TMs A TM = { <M,w> | M is a TM & w ? L(M) } Theorem: A TM is T uring recognizable Pf: It is recognized by a TM U that, on input <M,w>, simulates M on w step by step. U accepts iff M does. ? U is called a Universal Turing Machine (Ancestor of the stored-program computer) Note that U is a recognizer, not a decider. Page 3 Lecture 6 The Acceptance Problem for TMs A TM = { <M,w> | M is a TM & w ? L(M) } Theorem: A TM is T uring recognizable Pf: It is recognized by a TM U that, on input <M,w>, simulates M on w step by step. U accepts iff M does. ? U is called a Universal Turing Machine (Ancestor of the stored-program computer) Note that U is a recognizer, not a decider. A TM is Undecidable A TM = { <M,w> | M is a TM & w ? L(M) } Suppose it’s decidable, say by TM H. Build a new TM D: “on input <M> (a TM), run H on <M,<M>>; when it halts, halt & do the opposite, i.e. accept if H rejects and vice versa” D accepts <M> iff H rejects <M,<M>> (by construction) iff M rejects <M> (H recognizes A TM ) D accepts <D> iff D rejects <D> (special case) Contradiction! Page 4 Lecture 6 The Acceptance Problem for TMs A TM = { <M,w> | M is a TM & w ? L(M) } Theorem: A TM is T uring recognizable Pf: It is recognized by a TM U that, on input <M,w>, simulates M on w step by step. U accepts iff M does. ? U is called a Universal Turing Machine (Ancestor of the stored-program computer) Note that U is a recognizer, not a decider. A TM is Undecidable A TM = { <M,w> | M is a TM & w ? L(M) } Suppose it’s decidable, say by TM H. Build a new TM D: “on input <M> (a TM), run H on <M,<M>>; when it halts, halt & do the opposite, i.e. accept if H rejects and vice versa” D accepts <M> iff H rejects <M,<M>> (by construction) iff M rejects <M> (H recognizes A TM ) D accepts <D> iff D rejects <D> (special case) Contradiction! Let M i be the TM encoded by w i , i.e. <M i > = w i (M i = some default machine, if w i is an illegal code.) i, j entry tells whether M i accepts w j Then L D is not recognized by any TM A speci?c non-T uring- recognizable language w 1 1 w 2 w 3 w 4 w 5 w 6 <M 1 > > <M 2 > <M 3 > <M 4 > <M 5 > <M 6 > 0 0 0 0 0 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 1 L D 1 0 1 1 1 0 ... ... ... ... Note: The above TM D, if it existed, would recognize exactly the language L D de?ned in this diagonalization proof (which we already know is not recognizable) Page 5 Lecture 6 The Acceptance Problem for TMs A TM = { <M,w> | M is a TM & w ? L(M) } Theorem: A TM is T uring recognizable Pf: It is recognized by a TM U that, on input <M,w>, simulates M on w step by step. U accepts iff M does. ? U is called a Universal Turing Machine (Ancestor of the stored-program computer) Note that U is a recognizer, not a decider. A TM is Undecidable A TM = { <M,w> | M is a TM & w ? L(M) } Suppose it’s decidable, say by TM H. Build a new TM D: “on input <M> (a TM), run H on <M,<M>>; when it halts, halt & do the opposite, i.e. accept if H rejects and vice versa” D accepts <M> iff H rejects <M,<M>> (by construction) iff M rejects <M> (H recognizes A TM ) D accepts <D> iff D rejects <D> (special case) Contradiction! Let M i be the TM encoded by w i , i.e. <M i > = w i (M i = some default machine, if w i is an illegal code.) i, j entry tells whether M i accepts w j Then L D is not recognized by any TM A speci?c non-T uring- recognizable language w 1 1 w 2 w 3 w 4 w 5 w 6 <M 1 > > <M 2 > <M 3 > <M 4 > <M 5 > <M 6 > 0 0 0 0 0 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 1 L D 1 0 1 1 1 0 ... ... ... ... Note: The above TM D, if it existed, would recognize exactly the language L D de?ned in this diagonalization proof (which we already know is not recognizable) Decidable Recognizable recognizable decidable co- recognizable ? ? L D L DRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!