3 ms·
What does it mean to take a random oracle from all oracles? How do you enumerate oracle-space? Is that something like the space of all problems, where each pro
by SilasX 10y ago
What does it mean to take a random oracle from all oracles? How do you enumerate oracle-space? Is that something like the space of all problems, where each problem corresponds to an oracle for that problem?
- adilparvez 10y agoYes, I think it is like that.
- SilasX 10y agoAnother way to enumerate oracles is to consider the set of terminating Turing machines (and enumerating them is itself uncomputable but whatever). Each TM corresponds to an oracle that computes its result in O(1).
- nialv7 10y agoThis is not true. You can have oracles for uncomputable problems, like oracle for the halting problem.
- nialv7 10y agoYou can choose a random oracle by choose a language by random. Here a language means a set of strings.
- SilasX 10y agoCan you explain that further? A random oracle is a random set of strings...?
- tromp 10y agoFlip a coin for each string to decide its membership in the language. In other words, let the characteristic sequence of the language be an infinite random binary string.
- SilasX 10y agoSo, a language is a mapping from strings to 1/0? And an oracle is a language?
- kosievdmerwe 10y agoA language is a set of strings and an oracle for that language answers whether a certain string is in that language in O(1) time.