Timeline for What is an oracle, really? [closed]
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 1, 2022 at 22:05 | comment | added | Thomas Benjamin | (cont.) considered as a "well-defined mathematical question" (at least from the point of view of mathematical philosophy). Hope this helps. | |
| Feb 1, 2022 at 22:03 | comment | added | Thomas Benjamin | (cont.) an order-preserving mapping of the Kleene-Brouwer ordering (of our computation) into this interval. The resulting points may be thought of as moments of time at which steps of the generalized computation occur. Thus, for example, the generalized machine which solves the ordinary halting problem might, for a given input, perform its steps at times 1/2, 3/4, 7/8,...,1."]. If this quote from Rogers would be deemed a well-defined mathematical description (at least from the point of view of mathematical philosophy), then my question (you got it right in your comment) should be | |
| Feb 1, 2022 at 21:47 | comment | added | Thomas Benjamin | @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 | |
| Jan 29, 2022 at 15:26 | history | left closed in review |
Alex M. Michael Albanese András Bátkai |
Original close reason(s) were not resolved | |
| Jan 28, 2022 at 21:26 | comment | added | LSpice | 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. | |
| Jan 28, 2022 at 21:25 | history | edited | LSpice | CC BY-SA 4.0 |
Proofreading (I am not claiming that this edit resolves the original close reason, but the box is checked and I cannot uncheck it)
|
| S Jan 28, 2022 at 21:12 | review | Reopen votes | |||
| Jan 29, 2022 at 15:26 | |||||
| S Jan 28, 2022 at 21:12 | history | edited | Thomas Benjamin | CC BY-SA 4.0 |
added 2959 characters in body
Added to review
|
| Oct 7, 2021 at 21:15 | history | closed |
Noah Schweber Wojowu Ryan Budney LSpice Dima Pasechnik |
Needs details or clarity | |
| Oct 7, 2021 at 20:19 | answer | added | Andrej Bauer | timeline score: 8 | |
| Oct 7, 2021 at 18:51 | comment | added | David Roberts♦ | Better to actually go to the effand type the relevant bit... | |
| Oct 7, 2021 at 18:50 | history | edited | David Roberts♦ | CC BY-SA 4.0 |
image
|
| Oct 7, 2021 at 18:02 | review | Close votes | |||
| Oct 7, 2021 at 21:17 | |||||
| Oct 7, 2021 at 17:35 | comment | added | Noah Schweber | 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. | |
| Oct 7, 2021 at 17:34 | comment | added | Wojowu | 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. | |
| Oct 7, 2021 at 17:22 | history | asked | Thomas Benjamin | CC BY-SA 4.0 |