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?

$\endgroup$
  • $\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 '14 at 12:24
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.

$\endgroup$

Your Answer

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

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