-4
$\begingroup$

Excerpt from Rogers, Jr., Theory of Recursive Functions and Effective Compatibility, pp. 496–497

Regarding oracles, might this be a reasonable description of their inner workings (this from Hartley Rogers, Jr.'s text, Theory of Recursive Functions and Effective Computability)?

Why should I ask such a question in the face of majority opinion to the contrary (as expressed in Prof. Bauer's answer)? Well, let me begin at the beginning, with Turing's remarks regarding 'oracles' found in his doctoral thesis, "Systems of Logic Based on Ordinals" (pp. 13–14):

Let us suppose that we are supplied with some unspecified means of solving number theoretic problems; a kind of oracle as it were. We will not go any further into the nature of this oracle than to say that it cannot be a machine….

What sort of 'machine' is Turing talking about? Well, considering that his doctoral thesis was written after the paper that introduced the notion now known as the "Turing Machine", it should be clear from Section 2 of his thesis, "Effective calculability. Abbreviation of treatment", that it is, in fact, the Turing machine he is referring to in his remarks regarding the oracle. As regards the notion of "number theoretic problem", he defines it as follows in Section 3, "Number theoretic theorems":

By a number theoretic theorem we shall mean a theorem of the form '$\theta$ vanishes for infinitely many natural numbers $x$', where $\theta(x)$ is primitive recursive [a primitive recursive function—my comment]. We shall say that a problem is number theoretic if it has been shown that any solution of the problem solution may be put in the form of a proof of one or more number theoretic theorems. More accurately we may say that a class of problems is number theoretic if the solution of any one of them can be transformed (by a uniform method) into the the form of proofs of number theoretic theorems.

It is within this context I proposed that the generalized machines discussed in Hartley Rogers Jr.'s book might act as oracles for a certain class of problems (though not in general).

As regards the notion that oracles are merely 'inputs' or a 'database', I refer the reader of this question to a remark made by Martin Davis in his short paper, "Why there is no such discipline as hypercomputation", Applied Mathematics and Computation 178 (2006) 4-7:

The great day has arrived! The world's first working hypercomputer has been unveiled. Here comes the output—guaranteed by the engineers to be a non-Turing-computable infinite sequence of natural numbers:

23, 5, 1267, 111, 59, 87654, 21, 1729, 88888881, etc.

But wait! No matter how long this goes on, we will see only a finite number of outputs. Moreover, any such finite sequence of natural numbers is the initial part of both computable and non-computable infinite sequences (in fact, infinitely many of each kind). Thus, no finite amount of data will suffice to distinguish the computable from the non-computable, and since we, as finite beings with finite lifetimes will only have access to a finite amount of data, no possible experiment could certify that a device is truly going beyond the Turing computable.

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ What do you mean with "inner workings"? Usually in computability an oracle is merely a certain string of bits (or a subset of $\mathbb N$, or something equivalent to that effect) which the machine is given access to. It doesn't have to be produced by any supercomputer of any sort. $\endgroup$
    – Wojowu
    Commented Oct 7, 2021 at 17:34
  • 1
    $\begingroup$ Clearly not: as Rogers says, these generalized machines have very limited scope (e.g. the partial functions they compute are exactly the $\Pi^1_1$ ones). So there's no way in which we can think of an arbitrary oracle as an instantiation of such a machine. I'm not really sure what this question is getting at, to be honest. $\endgroup$
    – Noah Schweber
    Commented Oct 7, 2021 at 17:35
  • 1
    $\begingroup$ Better to actually go to the effand type the relevant bit... $\endgroup$
    – David Roberts ♦
    Commented Oct 7, 2021 at 18:51
  • $\begingroup$ What is the question? Is it "Might [this quote] be a reasonable description of their [oracles'] inner workings?" I don't understand how that is a well defined mathematical question. $\endgroup$
    – LSpice
    Commented Jan 28, 2022 at 21:26
  • $\begingroup$ @LSpice: Do you believe that an 'oracle' must be an "(infinite) input string" (as Prof. Bauer holds)? Given Prof. Davis' observation as quoted by me in my edit, it must, assuming that Prof. Bauer is correct in his assertion. But the "generalized machine" described by Rogers is as much a 'fiction' as Prof Bauer's 'infinite input string', however, Prof. Rogers' description of the generalized machine allows that a convergent computation of such a machine can be carried out in a finite amount of time ["Let the unit interval (of real numbers) be thought of as a finite interval of time. Take $\endgroup$
    – Thomas Benjamin
    Commented Feb 1, 2022 at 21:47

1 Answer 1

Reset to default
8
$\begingroup$

The notion of "inner working" of an oracle is meaningless, because oracles are not machines. They are (infinite) input strings.

In fact, it would be better to call oracles just input, as that would create less confusion.

Improve this answer
$\endgroup$
10
  • $\begingroup$ I think this answer is very good, both because it does answer the literal question, and indicates a reframing that explains things even better. And I think the question is worth keeping here, since I'd wager that many people would want to know a precise definition of "oracle", e.g., so one could prove something about it? :) $\endgroup$
    – paul garrett
    Commented Oct 7, 2021 at 20:22
  • $\begingroup$ @AndrejBauer: If one was to presume that oracles are just "(infinite) input strings" or "just input", would one need to presume some sort of background set theory in which these infinite input strings exist and also the existence of functions which would allow one access to these infinite input strings for some Turing machine? $\endgroup$
    – Thomas Benjamin
    Commented Oct 9, 2021 at 20:43
  • 4
    $\begingroup$ You are presenting use of "background set theory" as if it were some sort of a problem, which of course it is not. Turing machines themselves are a mathematical concept that requires a mathematical background. It's not like we keep them in the basement and wonder where to put the infinite tapes. If you wish, we can separately discuss how strong a formal system is needed to express Turing machines with oracles, but that discussion is orthogonal to the fact that oracles are not machines. Did you see an explanation somewhere that said otherwise? $\endgroup$
    – Andrej Bauer
    Commented Oct 9, 2021 at 21:23
  • $\begingroup$ I am not so concerned about the necessity of the presumption of a background set theory in order to infer the existence of sets in $\mathcal P$($\omega$) ($\mathcal P$ being the power set) --rather, I am more concerned with the existence of functions necessary to allow one access to the infinite input strings for some Turing machine. If, say, one would represent those functions as special states for some description of a Turing machine, then they are part of the description of the machine and therefore cannot be claimed to be 'non-mechanical'. When Turing (in his thesis) claimed that an $\endgroup$
    – Thomas Benjamin
    Commented Oct 11, 2021 at 21:25
  • $\begingroup$ (cont.) oracle "cannot be a machine", what was his definition of 'machine', anyway? $\endgroup$
    – Thomas Benjamin
    Commented Oct 11, 2021 at 21:30

Not the answer you're looking for? Browse other questions tagged .