# Is this problem decidable? (computation of $M_1$ longer than $M_2$ on every input)

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?

• 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. Oct 23, 2014 at 12:24

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.