{{m, x)| m is a turing machine that runs on input x for an even let 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?