Post your solutions to the Feb 8 In-class Exercise to this thread.

Best, Chris

Say we want to build a machine M_{zero} such that M_{zero}(\alpha) = 1 iff M_{\alpha}(x) halts, x is a string containing 0. We can generalize this machine to the M_{HALT} one discussed in class: M_{zero}(\alpha) = M_{HALT}(\alpha, x). As we know that M_{HALT} is uncomputable, so is M_{zero}.

If M(ZERO) computed ZERO then M(ZERO) can be computed using M(HALT). Assume x as a string containing 0 then for MHALT(α,x) it outputs 1 if M(α) halts on input x and MZERO(α), outputs 1 otherwise it outputs 0. If ZERO were computable then MZERO(α) would halt in a finite number of steps and that means M(HALT) would be computable thus contradicting the assumption.

Say M-ZERO is a turning machine that runs Turing Machine ZERO ZERO (eventually) halts on any input that has a 0. NZI = Non-Zero Input (binary string devoid of zeros) If (M-ZERO has input {ZERO, NZI} ), and the encoding of ZERO is not a member of the set of NZIs, then we have a contradiction, as M-ZERO will not halt on a string that has zeros in it.

Suppose ZERO function is computed by MZERO Turing machine. Now if MZERO halts for input α then MZERO(α) = 1.

Since this is a halting problem we can reduce it to MHALT. In that case if MZERO is computable then MHALT needs to be computable. But according to definition of MHALT, it is uncomputable. This makes MZERO also uncomputable.

The function ZERO on input α outputs 1 if and only if the TM Mα halts on all strings containing 0. We can reduce this to the function HALT. Since HALT is not computable, we can say that ZERO is also not computable.

Suppose ZERO was computable by some TM M_{ZERO}. Then there exists a machine M_{HALT} which operates as follows: on input \alpha,x we build a string \beta for a TM which on input y, erases y and writes down \alpha,x & only outputs 1 if \alpha halts on x. If ZERO were computable, then TM_{\alpha} would halt on all strings containing 0, and M_{HALT} would be computable, creating a contradiction.