[SilasX]

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?

[nialv7]

You can choose a random oracle by choose a language by random. Here a language means a set of strings.

[SilasX]

Can you explain that further? A random oracle is a random set of strings...?

[tromp]

Flip 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]

So, a language is a mapping from strings to 1/0? And an oracle is a language?

[kosievdmerwe]

A 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.

[adilparvez]

Yes, I think it is like that.

[SilasX]

Another 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]

This is not true. You can have oracles for uncomputable problems, like oracle for the halting problem.