Se o far some language {ab"n≥0} decidable all languages regular languages context free anquages RE {a"bcn|n≥0} We will show a natural undecidable l next
So far… ◼ We will show a natural undecidable L next. regular languages context free languages all languages decidable RE {a nb n | n ≥ 0} {a nb nc n | n ≥ 0} some language
The halting problem Definition of the Halting Problem hALT=<M, x> TM M halts on input x ■ Is halt decidable?
The Halting Problem ◼ Definition of the “Halting Problem” : HALT = { <M, x> | TM M halts on input x } ◼ Is HALT decidable?
The halting problem Theorem: HALT is not decidable(undecidable) Proof: o Suppose TM h decides halt if M halts on x, H accept if M does not halt on x, H reject o Define new TM H: on input <M> if H accepts <M, <M>>, then loop if H rejects <M, <M>>, then halt o consider H on input <H> if it halts, then H rejects <H, <H>>, which implies it cannot halt if it loops, then H accepts <H, <H>>, which implies it must halt o contradiction. Thus neither h nor h can exist
The Halting Problem Theorem: HALT is not decidable (undecidable). Proof: Suppose TM H decides HALT ◼ if M halts on x, H accept ◼ if M does not halt on x, H reject Define new TM H’: on input <M> ◼ if H accepts <M, <M>>, then loop ◼ if H rejects <M, <M>>, then halt consider H’ on input <H’>: ◼ if it halts, then H rejects <H’, <H’>>, which implies it cannot halt ◼ if it loops, then H accepts <H’, <H’>>, which implies it must halt contradiction. Thus neither H nor H’ can exist
Where's the Diagonalization? 5 Entry ii is the value of h on input <M <M>> A=Accept, r= Reject <Ml><M2><M3><M4> A R A R M2 AA AA M3 RR RR M4AA RR
Where’s the Diagonalization? ◼ Entry i,j is the value of H on input <Mi , <Mj>> <M1> <M2> <M3> <M4> … M1 A R A R M2 A A A A M3 R R R R M4 A A R R … A = Accept, R = Reject
OH' is the opposite of the diagonals t Entry ij is the value of H on input <M;> <Mi>> <M1><M2><M3><M4><H> M1△RA M2AAA M3R RR M4A A R RARRA H R R A
H’ is the opposite of the diagonals: ◼ Entry i,j is the value of H on input <Mi , <Mj>> <M1> <M2> <M3> <M4> … <H’> M1 A R A R M2 A A A A M3 R R R R M4 A A R R … H’ R R A A ?