Reduction from ATM. Assume that EVEN TM is decidable with decider MT. We now show how to build, given a ⟨M, w⟩ a machine description ⟨M'⟩ that satisfies the following faithfulness condition. If M accepts w then M' accepts every even-length string If M does not accept w then M' does not accept every even-length string M': On input x If x is an **odd-length** string then accept Else simulate M on w and answer what M answered. Obviously M' satisfies the faithfulness condition. Here is a decider for ATM. On input ⟨M, w⟩ 1. Build ⟨M'⟩ 2. Run MT on input ⟨M'⟩ 3. Answer what MT answered.
So I have this solution the the problem, what I don't understand is why ⟨M'⟩ checks for odd length first then accepts right away? this doesnt make sense to me