ReducibilityThe undecidability of the halting problemDefinition of mapping reducibilityAn example of a mapping reductionUsing mapping reducibility for proving decidability/undecidabilityA mapping reduction of ATM to HALTTMReducibilityReducibilityChapter 5 Giorgi Japaridze Theory of ComputabilityThe undecidability of the halting problem5.1.aGiorgi Japaridze Theory of ComputabilityLet HALTTM = {<M,w> | M is a TM and M halts on input w}HALTTM is called the halting problem. Theorem 5.1: HALTTM is undecidable. Proof idea: Assume, for a contradiction, that HALTTM is decidable. I.e. there is a TM R that decides HALTTM. Construct the following TM S:• If M accepts w, what will S do on input <M,w>?• If M explicitly rejects w, what will S do on <M,w>? Thus, S decides the languageS = “On input <M,w>, an encoding of a TM M and a string w: 1. Run R on input <M,w>. 2. If R rejects, reject. 3. If R accepts, simulate M on w until it halts. 4. If M has accepted, accept; if M has rejected, reject.”But this is impossible (Theorem 4.11)• If M works forever on w, what will S do on <M,w>?Definition of mapping reducibility5.3.aGiorgi Japaridze Theory of Computability We say that A is mapping reducible to B, written AmB, if there is a computable function f: ** such that, for every w*, wA iff f(w)B.The function f is called a mapping reduction of A to B.*A*BffLet A and B be languages over an alphabet  .An example of a mapping reduction5.3.bGiorgi Japaridze Theory of Computability* *Let f be the function computed by the following TMO M:M=“On input <N,w>, where N is an NFA and w is a string, 1. Convert N into an equivalent DFA D using the algorithm we learned; 2. Return <D,w>.”f is then a mapping reduction of what language to what language?<N,w><D,w><N,w><D,w>Using mapping reducibility for proving decidability/undecidability5.3.cGiorgi Japaridze Theory of ComputabilityTheorem 5.22: If AmB and B is decidable, then A is decidable.Proof: Let DB be a decider for B and f be a reduction from A to B.We describe a decider DA for A as follows.DA= “On input w: 1. Compute f(w). 2. Run DB on input f(w) and do whatever DB does.”Corollary 5.23: If AmB and A is undecidable, then B is undecidable.Theorem 5.22 remains valid with “Turing recognizable” instead of “decidable”. So does Corollary 5.23.A mapping reduction of ATM to HALTTM 5.3.dGiorgi Japaridze Theory of Computability For every TM M, let M* be the following TM: M* = “On input x: 1. Run M on x. 2. If M accepts, accept. 3. If M rejects, enter an infinite loop.”Thus, • If M accepts input x, then M*• If M explicitly rejects x, then M*• If M never halts on x, then M*To summarize, M accepts x iff M*Let then f be the function defined by f(<M,w>)=<M*,w>. Obviously <M,w>ATM iff f(<M,w>) i.e. f is a So, since ATM is undecidable, HALTTM is undecidable as well. Is f