I am currently browsing the lecture notes on computability/decidability and I have encountered the following exercise I am unable to solve.

Given $M_1$, $M_2$ Turing machines, is it true that for every $x \in \Sigma^*$ $M_1$ performs at least as many steps while working on input $x$ as $M_2$ does with input $x$?

There is also an answer to the excercise and a hint, though it didn't help me that much:

  • Let $M_1$ be a TM which enters an infinite cycle for any input → halting problem (and thus undecidable).

  • Complement of the language is partially decidable, because non-deterministic TM can provide a counter-example.

In particular, I would like to know how can I express these statements formally:

  • How to formally describe the language describing the problem?
  • How to reduce the language to halting problem?
  • How to show that the complement is partially decidable?

The only thing I can decide with a confidence is that the language itself is not even partially decidable, since complement is partially decidable, but the language itself is not decidable, and thus the language is not even partially decidable (Post theorem).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.