3
$\begingroup$

Is this problem decidable?

Given two representations of Turing machines $R(M_1), R(M_2)$, is the length of the computation of $M_1$ longer than the length of the computation of $M_2$ on every input?

My guess is not decidable. I am not sure, however, how to justify it.

I tried this: Lets enumarate all possible words from $\{0,1\}^*$ and run $M_1$ and $M_2$ simultaenously. If $M_1$ accepts/rejects and $M_2$ is still running, output NO. If $M_2$ stops and $M_1$ is still running, check next word. However, if neither $M_1$, nor $M_2$ do not halt on the word, I am stuck and cannot decide it (because I will get an instance of the halting problem for each combination of word and Turing machine).

Is this reasonable or is it a wrong assumption?

Improve this question
$\endgroup$
1
  • $\begingroup$ Actually, this is already undecidable if some input is fixed. Undecidability of your original problem then follows from the fact that M1 and M2 can be modified to check if the input is the fixed one and if not accept at the same time. $\endgroup$
    – DCTLib
    Oct 23, 2014 at 12:24

1 Answer 1

Reset to default
1
$\begingroup$

Hint: Let $M_2$ be a machine that on input $n$ runs for $n$ steps roughly, and only consider machines $M_1$ that don't depend on their input. If you could solve your task then you could determine whether a given input-less machine ever halts.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.