Theory of computation Mapping reductions

(4 points) Consider the computational problem DECTM M) | M is a Turing machine and M is a decider) Consider the computable function on * specified by the algorithm (Turing mlachine): F "On input , 1. Type check if x-(M) for some Turing machine M 2. If not, output 3. If so, build the new Turing machineM-"On input y 1. Run M on y. If it accepts, loop; if it rejects, accept." 4 Output (M" (a) True or False: For all strings x E *, if x E ETM then Fi(x) DECTM (b) True or False: For all strings x E *, if x ETM then F,(x) DECTM (c) True or False: For all strings x E *, if x E DECTM then F4(x) E ETM. (d) True or False: For all strings x E *, if x DECTM then F4(x) ETM