Let even = {hm, xi | m is a turing machine that runs on input x for an even number of steps}. of course, a turing machine running for infinitely many steps neither runs for an odd nor an even number of steps. we want to show that even is undecidable by a proof from scratch (i. e., by diagonalization not by a reduction). first we assume even is decidable, i. e., there is a tm h that accepts hm, xi if m is a turing machine that runs on input x for an even number of steps, and rejects otherwise. we want to do the diagonalization in two stages.

(a) first, describe a tm d˜ (based on the supposedly existing tm h) accepting hmi if and only if m is a turing machine that runs on input hmi for an even number of steps. otherwise d˜ rejects. note that you may assume the correctness of the church-turing thesis, i. e., instead of describing a turing machine in detail, you can just describe an algorithm in pseudo–code.

(b) now define a tm d from d˜ that runs on hmi for an odd number of steps if d˜ accepts hmi. otherwise d runs for an even number of steps.

(c) how does the existence of this produce a contradiction?

(d) what does the contradiction prove?