1
$\begingroup$

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?

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

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.