How to prove a Turing Machine property is trivial [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

Imagine I have a Turing Machine Property that looks like this:

P = {M | L(M) is accepted by a Turing machine that does not halt in an even number of steps for any input}

How can I prove that this property is trivial? Or, more generally, are there good ways to prove this sort of thing?

Answer 1

As a hint: you can make any TM always halt within an odd number of steps by making two copies of the states - an "odd" copy and an "even" copy - and toggling back and forth between them when transitions occur. Once you've done this, how would you modify this machine so that it never halts in an even number of steps? Given that this construction works for any arbitrary TM, do you see why the above property is trivial?

Hope this helps!