Is being able to decide which program stop first equivalent to the halting problem?

Question

Here is the "halting first" problem: given two programs $P$ and $Q$, return 0 if $P$ stops after less steps than $Q$, return $1$ if $Q$ stops after less steps than $P$, and otherwise output $0$ or $1$. (So if neither problem halts, or if both halts in the same number of steps, the oracle may output either $0$ or $1$ freely.)

Is the "halting first" problem equivalent to the halting problem? If we have an oracle for the halting problem, we can solve it by checking if $P$ and $Q$ will halt, and if they do, just run them until they halt and compare the number of steps.

This problem is also undecidable, because we can use an oracle $O$ for this problem to compute a complete and consistent theory extending Peano's arithmetic in the following way: let $(f_n)$ be a sequence of all formulas, and you have $T_n$ your theory at step $n$, then you define $T_{n+1} := T_n \cup \{f\}$, where $f := f_{n+1}$ if $O$ outputs 0 given a program searching for a proof of $f_{n+1}$ given $T_n$ and a program searching for a disproof, and $f := \neg f_{n+1}$ otherwise. Sadly this is not sufficient to get an oracle for the halting problem, because this theory doesn't have to be sound.

I thought of this problem while searching how to get a computable binary tree with no computable infinite branch but one noncomputable infinite branch. There's no real purpose, but I could not stop thinking about it.

Answer 1

This task is in fact strictly weaker than the halting problem, although still non-computable.

Let $P_i$ denote the $i$th program in some reasonable enumeration, and let $l,r$ be the projection functions corresponding to the Cantor pairing function. Let $T$ be the binary tree where a string $\sigma$ of length $n$ is on $T$ iff for each $i<n$ we have

• if $\sigma(i)=0$ and $P_{r(i)}$ halts in $x<n$ stages then $P_{l(i)}$ halts in $<x$ stages; and

• if $\sigma(i)=1$ and $P_{l(i)}$halts in $x<n$ stages then $P_{r(i)}$ halts in $<x$ stages.

Basically, a $\sigma\in T$ consists of a "guess" at a solution to the problem you describe, with the $i$th bit being $0$ meaning "I think $P_{l(i)}$ halts before $P_{r(i)}$" and dually for $1$.

This is an infinite binary tree, paths through which represent solutions to your problem in the appropriate sense; moreover, it is computable, since the defining condition for $T$ only involves bounded searches. By the low basis theorem, then, $T$ has an infinite path which is much simpler than the halting problem.

You may also be interested in Diamondstone/Dzhafarov/Soare's survey paper.