Let even ={〈m, x〉 |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〈m, x〉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〈m〉if and only if m is a turing machine that runs on input〈m〉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〈m〉for an odd number of steps if d accepts 〈m〉. 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?