# Could the halting problem be computed in GlooP?

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?

• Can you define GlooP? – Noah Schweber Mar 30 at 15:58
• That's not actually a definition. What exactly is GlooP? – Noah Schweber Mar 30 at 16:03
• @NoahSchweber For the purposes of this question, GlooP is any language which has more power than FlooP, and is powerful enough to calculate reddiag. – nph Mar 30 at 16:07
• Is reddiag something specific? – Noah Schweber Mar 30 at 16:09
• Thanks, now your question is clear! – Noah Schweber Mar 30 at 16:12

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?

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.