Could the halting problem be computed in GlooP?

Question

In Douglas Hofstadter's book Gödel, Escher, Bach, he uses 3 theoretical programming languages to describe computation.

• BlooP represents primitive recursive programs.
• FlooP represents general or partial recursive programs.
• GlooP represents a theoretical language with more power than FlooP.

For the first two, see Wikipedia's "BlooP and FlooP" entry.

He gives an example of a program (called reddiag) which is not computable in FlooP and is not general or partial recursive.

reddiag [n] returns one plus the value of n inputed into the nth program of the list of halting FlooP programs in alphabetical order. Hofstadter shows that this function is not FlooP-computable, using Cantor's diagonal argument.

My question is:

Would the halting problem be computable in the theoretical language GlooP?

Answer 1

For what it's worth, I'm not actually a fan of GBH as far as topics beyond the basics go; if you're interested in the broader structure of non-computable sets, I recommend something like Soare's Recursively enumerable sets and degrees.

---

Rather than talking about languages, this question is more snappily phrased in terms of Turing reductions:

Is the halting problem computable relative to reddiag?

The answer is yes.

Write "$\varphi_e$" for the $e$th partial computable unary function according to some appropriate scheme (e.g. via FlooP programs alphabetically listed). Additionally, I'll use the following definition of the halting problem: $K=\{e: \varphi_e(e)$ halts$\}$. (There are many variations on this, all Turing-equivalent to $K$.)

First, we modify reddiag slightly:

Let $REDDIAG(n)=\sum_{i\le n}reddiag(n)$.

Clearly $REDDIAG$ is computable from $reddiag$, so it's enough to show that we can compute $K$ from $REDDIAG$.

Why do we prefer $REDDIAG$ to $reddiag$? Well, the former has the nice property that $REDDIAG(n)>\varphi_n(n)$ if $\varphi_n$ is total. By contrast, that's not guaranteed for $reddiag(n)$ since $\varphi_n$ won't in general be the $n$th total computable function. This lets us use $REDDIAG$ to get runtime upper bounds - the point is that from an upper bound on the runtime of $\varphi_e(e)$ if it halts at all, we can determine whether $e\in K$ (just run $\varphi_e(e)$ for that amount of time and see what happens).

So here's how we do that. There is a computable function $Time$ such that $Time(e)$ is an index for a program $\varphi_{Time(e)}$ which, on input $i$, completely ignores that input and runs $\varphi_e(e)$ until it halts - at which point (if ever) it halts and outputs the running time of $\varphi_e(e)$, and otherwise runs forever.

(A bit of clarification: $Time$ is a total computable function, but $\varphi_{Time(e)}$ will not be in general.)

The key point now is that $\varphi_e(e)$ halts iff $\varphi_{Time(e)}$ is total. Moreover, $REDDIAG(Time(e))>\varphi_{Time(e)}(Time(e))$ as observed above. Putting this all together we have:

If $\varphi_e(e)$ halts, then $\varphi_e(e)$ halts in at most $REDDIAG(Time(e))$-many steps.

Consequently, from $REDDIAG$ (and hence from $reddiag$) we can compute the halting problem as follows: simply run $\varphi_e(e)$ for $REDDIAG(Time(e))$-many steps. We have that $e\in K$ iff $\varphi_e(e)$ has halting in that time, and otherwise $e\not\in K$.

---

Let me end with a brief "further topics" coda:

A natural question at this point is how the set $Tot$ of indices for total computable functions compares with $K$. It turns out that $Tot$ is to $K$ as $K$ is to the computable sets. Specifically, we have a notion of "relativized halting problem" - the Turing jump - and just as $K\equiv_T\emptyset'$ we have $Tot\equiv_TK'$. Note the "$\equiv_T$" instead of "$=$." We do have $K=\emptyset'$, but $Tot$ is not literally the same set as $K'$, it's just Turing equivalent to it.

While the Turing jump may at first feel like a "successor operation" on Turing degrees, it's very much not:

• There are infinitely many noncomputable sets strictly weaker than the halting problem.

• There are $2^{\aleph_0}$-many noncomputable sets which don't compute the halting problem. (Indeed, almost all sets - in both senses of category and measure - are Turing-incomparable with $K$.)

The overall structure of the Turing degrees turns out to be surprisingly intricate, and there are still lots of open questions around it.