Did Gödel know about Turing degrees in 1946?

Question

A much quoted passage from Gödel is the opening section of his Remarks before the Princeton bicentennial conference on problems in mathematics (1946) where he praises Turing's Turing machine model of computation as being philosophically well founded:

Tarski has stressed in his lecture (and I think justly) the great importance of the concept of general recursiveness (or Turing's computability). It seems to me that this importance is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute definition of an interesting epistemological notion, i.e., one not depending on the formalism chosen. In all other cases treated previously, such as demonstrability or definability, one has been able to define them only relative to a given language, and for each individual language it is clear that the one thus obtained is not the one looked for. For the concept of computability, however, although it is merely a special kind of demonstrability or decidability, the situation is different. By a kind of miracle it is not necessary to distinguish orders, and the diagonal procedure does not lead outside the defined notion.

What strikes me as confusing is that Post published in 1944 his paper Recursively enumerable sets of positive integers and their decision problems where he introduced the idea of Turing degrees which seem (to me) to distinguish exactly the type of orders of non-recursiveness that Gödel was arguing do not exist.

To compound my confusion even further, the introduction to Gödel's paper provided by Parsons in Collected Works Vol. II seems to also ignore Turing degrees:

Gödel refers here not primarily to the equivalence of different formulations such as Turing computability, λ-definability and Herbrand-Gödel general recursiveness, but to the absence of the sort of relativity to a given language that leads to stratification of the notion, such as (in the case of definability in a formalized language) into definability in languages of greater and greater expressive power. Such stratification is driven by diagonal arguments. But, since a function enumerating the recursive functions is not recursive and there is no reason to think it computable, the diagonal function it gives rise to is simply non-recursive, rather than "recursive at the next level".

The way Parsons phrases "But, since a function enumerating the recursive functions is not recursive and there is no reason to think it computable, the diagonal function it gives rise to is simply non-recursive, rather than 'recursive at the next level'." sounds like a direct contradiction to the definition of Turing degree, and it surprises me greatly that he wrote this in (or at least it was published by) 1990. It also seems perfectly sensible to me to make a comparison to the stratification of Turing degrees and the stratification between $PA < ZFC < ZFC+Con(ZFC) < etc.$ which is what Gödel was originally talking about.

Was Gödel not aware of Turing degrees in 1946? Or am I misunderstanding what Gödel and Parsons are arguing for?

Answer 1

I do not believe that degrees of computability were directly relevant to the topic of Gödel's 1946 lecture because they do not relativize computability in the relevant language dependent sense that Gödel stressed, and Parsons after him.

Stillwell gives a lucid explanation of the difference in this regard between Turing computability (solvability, recursiveness) and things like definability and decidability in his Emil Post and His Anticipation of Gödel and Turing, and indicates that both Post and Gödel were aware of it:

"As we have seen, Post's starting point was the concept of computation, which he believed could be formalized and made subject to the diagonal argument. Diagonalization yields problems that are absolutely unsolvable, in the sense that no computation can solve them. In turn, this leads to relatively undecidable propositions, for example, propositions of the form $n\notin S_n$. No consistent formal system $F$ can prove all true propositions of this form, hence any such $F$ must fail to prove some true proposition $n_o\notin S_{n_0}$. But this proposition is only relatively undecidable, not absolutely, because $F$ can be consistently extended by adding it as an axiom.

Gödel did not at first believe in absolutely unsolvable problems, because he did not believe that computation is a mathematical concept. Instead, he proved the existence of relatively undecidable propositions directly, by constructing a kind of diagonal argument inside Principia Mathematica".

What of "degrees of computability"? Turing hints at them in passing in a 1939 paper where he introduces oracles, but the first clear exposition is indeed Post's 1944 paper. However, it does not relativize recursiveness to a language, but introduces a new notion of recursive reducibility, which can be formalized in terms of consulting Turing oracles. As Post explains in his paper:

"At certain times the otherwise machine determined process raises the question is a certain positive integer in a given recursively enumerable set $S_2$ of positive integers, and that the machine is so constructed that were the correct answer to this question supplied on every occasion that arises, the process would automatically continue to its eventual correct conclusion. We could then say that the machine effectively reduces the decision problem of $S_1$ to that of $S_2$."

But we do not get a larger class of recursive functions by extending the formalism, consulting an oracle is no such extension. Once we get into the Peano arithmetic the recursive is fixed, moving to ZFC or further changes nothing, non-recursive remains non-recursive. That some problems are recursively reducible to some other problems and not vice versa does establish a hierarchy, but it is not based on a hierarchy of languages. More expressive languages alter decidability and definability but they do not make uncomputable computable, that is absolute.

Was Gödel aware of Post's paper in 1946 (not that it mattered for his praise of Turing)? Soare's Turing-Post Relativized Computability and Interactive Computing gives a detailed historical account of the developments from 1936 to 1954. Unfortunately, there is no direct answer. Post had a knack for being overlooked. In a sense, he proved the incompleteness theorem before Gödel, and described the Turing machine before Turing, but got little recognition for either (see Stillwell). Hao Wong, Gödel's closest fried and colleague who spent countless hours interviewing him, suggests that Gödel overlooked him too (unlike Church, he is not even mentioned):

"Over the years G habitually credited A.M. Turing’s paper of 1936 as the definitive work in capturing the intuitive concept [of computability], and did not mention Church or E. Post in this connection. He must have felt that Turing was the only one who gave persuasive arguments to show the adequacy of the precise concept... In particular, he had probably been aware of the arguments offered by Church for his “thesis” and decided that they were inadequate. It is clear that G and Turing (1912–1954) had great admiration for each other..."

This would be particularly not surprising given the topic of 1946 lecture and the fact that earlier "Post did not attempt to prove that his formalism coincided with any other formalism, such as general recursiveness, but merely expressed the expectation that this would turn out to be true". On the other hand, "it was only during the next phase from 1940 to 1954 that Post’s remarkable influence was fully felt. As Turing left the subject of pure computability theory in 1939, his mantle fell on the shoulders of Post". It is certainly likely that Gödel became aware of Post's and Kleene's work on recursive reducibility at least in 1950-s.