Fix E = {0, 1} for this question. For each part below, you can choose sets...

 

Transcribed Image Text:

Fix E = {0, 1} for this question. For each part below, you can choose sets from the following list: Arat, ArM: HALTrM, HALTTM, ETM,ETM; EQTM, EQTM E* You may use each set from the list at most once in the examples below. In particular, you can't choose A = B = C = D= X =Y = E*. (c) Find sets X, Y for which the computable function H = "On input a 1. Check if r = (M, w) for M a Turing machine and w a string. If so, go to step 3. gae 2. If not, output ( 3. Construct the Turing machine M= "On input y, 1. If y # w, reject. 2. Otherwise, run M on w. 3. If M accepts, accept. If M rejects, accept." 4. Output (M)." witnesses a mapping reduction X <m Y. Justify your answer by proving that, for all strings r, rE X iff H(x) E Y. Fix E = {0, 1} for this question. For each part below, you can choose sets from the following list: Arat, ArM: HALTrM, HALTTM, ETM,ETM; EQTM, EQTM E* You may use each set from the list at most once in the examples below. In particular, you can't choose A = B = C = D= X =Y = E*. (c) Find sets X, Y for which the computable function H = "On input a 1. Check if r = (M, w) for M a Turing machine and w a string. If so, go to step 3. gae 2. If not, output ( 3. Construct the Turing machine M= "On input y, 1. If y # w, reject. 2. Otherwise, run M on w. 3. If M accepts, accept. If M rejects, accept." 4. Output (M)." witnesses a mapping reduction X <m Y. Justify your answer by proving that, for all strings r, rE X iff H(x) E Y.