Godel on recursion-theoretic hierarchies

Question

At the end of his excellent article, "The Emergence of Descriptive Set Theory" (http://math.bu.edu/people/aki/2.pdf), Kanamori writes:

"Another mathematical eternal return: Toward the end of his life, Godel regarded the question of whether there is a linear hierarchy for the recursive sets as one of the big open problems of mathematical logic. Intuitively, given two decision procedures, one can often be seen to be simpler than the other. Now a set of integers is recursive iff both it and its complement are recursively enumerable. The pivotal result of classical descriptive set theory is Suslin's that a set is Borel iff both it and its complement are analytic. But before that, a hierarchy for the Borel sets was in place. In an ultimate inversion, as we look back into the recursive sets, there is no known hierarchy."

I have two questions regarding this.

1) Can anyone provide a citation for this? I was unaware that Godel turned to this question at any point, and I'd be curious reading anything he had to say about it.

2) What work has been done on this question? In particular, is there any reason to believe there is such a hierarchy, beyond the (in my opinion, unconvincing) analogy with the Borel sets Kanamori gives?

Some observations around the second question: there are known, natural linear hierarchies for proper subsets of the recursive sets; for example, the Grzegorczyk hierarchy (http://en.wikipedia.org/wiki/Grzegorczyk_hierarchy) gives a hierarchy of the primitive recursive sets with order type $\omega$. However, it's not clear to me that any of these hierarchies have a chance of being extendible to all of the recursive sets in any nice way. In particular, one barrier faced would be that the naturally-occurring hierarchies enumerate those computable functions which are provably total in some corresponding recursive theory of arithmetic (or set theory), and no such theory can prove the totality of all total recursive functions. But maybe I'm wrong about some of this?

ADDED: I want to clarify that the connection between hierarchies and provable totality - which here is an obstacle - is usually incredibly useful (and if I have my history right, many of these hierarchies were developed precisely to understand what functions were provably total in certain systems).

Answer 1

I don't mean to give this as a complete answer, but regarding question 2, there have been a great deal of negative results surrounding this problem.

In fact, most of them take the form of showing that any ''reasonably constructive'' (read ''effectively generated'') subrecursive hierarchy of computable functions indexed by paths through Kleene's $\mathcal O$ suffer from definability issues. At the core of each argument, these negative results exploit some variation of Spector's $\Sigma^1_1$-boundedness principle. To illustrate an example, Sacks (located in his Higher Recursion Theory) explored an effective version of this principle as follows:

There is a computable function $\varphi$ such that, for every $x \in 2^{\omega}$, we have that

$x \subseteq \mathcal O \iff \varphi(x) \in \mathcal O$ and $x \subseteq \mathcal O_{\varphi(x)}$

where $\mathcal O_{\varphi(x)} := \left\{ y \in \mathcal O : rnk(y) \leq rnk(\varphi(x))\right\}$, and $rnk(x)$ denotes the rank of $x$, and is measured as an ordinal.

Applying this to our problem (or some variation thereof), any inductive classification of the computable functions on some $\Pi^1_1$-path $\mathcal P \subseteq \mathcal O$ will ultimately "collapse" before all the computable functions have been exhausted at some countable level, which is typically measured as the ordinal height of $\mathcal P$.

As an aside, I think it's interesting to note that Sacks himself gave a lecture where he recalls his conversations with Godel toward the end of his life. In particular, he mentioned a conversation where Godel outlined a list of outstanding problems in mathematical logic which he thought would enliven the subject as a whole. On the list, he suggested the problem of proving the existence of an exhuastive hierarchy of computable functions, and believed that such a hierarchy should exist.

Sacks then goes on to conclude that there is not a lot of evidence supporting Goedel's belief, in view of the negative partial results hinted above. However, Sacks did go on to say that no one has been able to give a real proof that no such hierarchy exists, and so one is left with the feeling that a final solution of this problem is out of reach with current methods.