Undecidability of language involving two TMs

Question

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).

Answer 1

1. The language is the set of all strings $M_1\#M_2$ where $M_1$ and $M_2$ are descriptions of Turing machines, and those machines have the property that $M_1(x)$ runs for more steps than $M_2(x)$ on every input $x$.

2. Given a string $M_1\#M_2$, it is undecidable whether the string is in the language; that is, whether $M_1$ and $M_2$ are machines such that $M_1(x)$ runs for more steps than $M_2(x)$ for all inputs $x$.

To show that it's undecidable, assume you have a decider $f(M_1, M_2)$ which accurately reports YES if $M_1$ runs for more steps than $M_2$ on every input, or NO otherwise. Then you can use this decider as a subroutine to solve the halting problem (which is impossible, so $f$ can't exist).

3. Here's the algorithm for solving the halting problem: Given a machine $M$ and a word $w$, you want to know whether $M$ halts on input $w$. Let $L$ be a special machine that loops forever on every input. Let $M_w$ be a machine that just simulates $M$ on $w$ no matter what its actual input is. Compute $f(L, M_w)$. If $M$ halts on input $w$, then this function will return YES. If $M$ loops forever on input $w$, then this function will return NO—because both $L$ and $M_w$ just loop forever no matter what input they're given. So this subroutine $f$ solves the halting problem—which we know is impossible.

4. A language $\mathscr{L}$ is partially decidable if there's a machine $M(x)$ that always halts and answers YES when $x\in \mathscr{L}$, but which is allowed to halt and answer NO or even just loop forever when $x\notin \mathscr{L}$.

   The complement of the language described in (1) is the language $M_1\# M_2$ where $M_1$ and $M_2$ describe Turing machines, where $M_1(x)$ runs for fewer steps than $M_2(x)$ on some input $x$.

   I figured this out by interpreting the language in (1) formally: $$\{M_1\#M_2: \forall x\in \Sigma^*, \mathsf{steps}(M_1(x)) \geq \mathsf{steps}(M_2(x))\}$$

   so its complement (by deMorgan's law) is $$\{M_1\#M_2: \exists x\in \Sigma^*, \mathsf{steps}(M_1(x)) < \mathsf{steps}(M_2(x))\}.$$

   This language is semi-decidable. It is semi-decidable because whenever the answer is YES (whenever $M_1$ and $M_2$ are machines such that $M_1(x)$ runs in fewer steps than $M_2(x)$ on at least one string), you can use a Turing machine to prove it.

   The algorithm is: Given two machines $M_1$ and $M_2$, nondeterministically pick a random string $x\in\Sigma^*$. Simulate the computation of $M_1(x)$ and $M_2(x)$. If $M_1(x)$ halts before $M_2(x)$, return YES. If the machines really belong to the language, then one of the nondeterministic guesses will halt and say YES. (If the machines don't belong to the language, then the simulations might loop forever, which is allowable for semi-decidable.)