Is my interpretation of this notation correct ? (G.E. Sacks book)

126 Views Asked by At

I am trying to read G.E. Sacks's book on higher recursion theory and he refers to the notation $\{ e \}^{f}$ as the $e$th element in an enumeration of partial recursive functions in $f$, where $f$ is a total function.

Am I right to interpret that $f$ is actually an oracle ? (as commonly referred to in other recursion theory texts)..

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, this is correct, although I don't think he explicitly mentions the notion of oracle anywhere; Sacks does everything formally.

Towards the beginning of the book, in Section 1.1, he defines:

$$\{e\}^f(b) \simeq c\;\text{ iff }\;(\mathrm E y)[T(\bar f(y),e,b,y)\;\;\&\;\;U(y)=c],$$

where $\bar f(y)$ encodes $f$ restricted to the domain $\{i\mid i<y\}.$

$T$ and $U$ are as defined by Kleene in his presentation of recursion theory, so the definition of $\{e\}^f(b)\simeq c$ means that there is some natural number $y$ such that the computation of $\{e\}^f(b)$ halts within y steps using only the first $y$ values of $f,$ and the value produced is $c$ (and if there is no such $y,$ then the computation diverges).

Viewing the computation as using an oracle for $f$ is the natural way of thinking about this. Sacks's definition is just a formalization of that intuitive notion.

I would guess that the motivation behind this formal approach (rather than using an informal notion of oracle) is probably so that you don't need a relativized Church's thesis, but only the original Church's thesis on partial recursive functions (without oracles).

Of course, you don't really need Church's thesis at all for the actual mathematics, but that's what lets you interpret the results as about our informal notion of computability (and relative computability). So letting that intuitive perspective be based on the original (weakest) form of Church's thesis is desirable.

By the way, I found the book available online at: https://projecteuclid.org/eBooks/perspectives-in-logic/Higher-Recursion-Theory/toc/pl/1235422631 (free open access).