Timeline for What is an oracle, really?
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 14, 2021 at 6:12 | comment | added | Andrej Bauer | Roger's book has such a description of oracles. The sequence of approximations is not computable, unless the oracle itself is. The $n$-th approximation receives the first $n$ bits of the oracle input, and if it ever atempts to access bits beyond that it diverges. So the machine is always the same, the changing part is the approximation of the oracle input. | |
| Oct 13, 2021 at 22:38 | comment | added | Thomas Benjamin | (cont.) approximation of the oracle in the sequence would be c.e.) with the set of Godel numbers of the sequence of computable functions in question not being c.e. . How is such "non-mechanical"? | |
| Oct 13, 2021 at 22:27 | comment | added | Thomas Benjamin | Are the characterizations given in the last two comments equivalent? The characterization you give in the last comment is particularly interesting to me in that since "...the oracle computation is seen as a (non-computable) limit of a sequence of computations, each of which has access to a finite approximation of the oracle", it would seem to infer that "the oracle computation...seen as a (non-computable) limit of a sequence of of computations, each of which has access to a finite approximation of the oracle", can be represented as a sequence of computable functions (since each finite | |
| Oct 11, 2021 at 21:46 | comment | added | Andrej Bauer | There are also ways of describing computations relative to an oracle that do not involve any infinite input tapes. Instead, the oracle computation is seen as a (non-computable) limit of a sequence of computations, each of which has acess to a finite approximation of the oracle. | |
| Oct 11, 2021 at 21:44 | comment | added | Andrej Bauer | One common way of having a machine access to an oracle is to have a special read-only "oracle tape" which contains the infinite sequence. The machine may then access the cells on that machine by moving the head around and reading the contents. So we don't have to extend Turing machines with any new concepts, we just give it one more tape. The quesion of where the oracle input comes from or how it is generated is not part of the description of a machine with an access to an oracle. | |
| Oct 11, 2021 at 21:30 | comment | added | Thomas Benjamin | (cont.) oracle "cannot be a machine", what was his definition of 'machine', anyway? | |
| Oct 11, 2021 at 21:25 | comment | added | Thomas Benjamin | 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 | |
| Oct 9, 2021 at 21:23 | comment | added | Andrej Bauer | 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? | |
| Oct 9, 2021 at 20:43 | comment | added | Thomas Benjamin | @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? | |
| Oct 7, 2021 at 20:22 | comment | added | paul garrett | 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? :) | |
| Oct 7, 2021 at 20:19 | history | answered | Andrej Bauer | CC BY-SA 4.0 |