3 ms·

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

• SilasX 10y ago
  Can you explain that further? A random oracle is a random set of strings...?
  • tromp 10y ago
    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 10y ago
      So, a language is a mapping from strings to 1/0? And an oracle is a language?
      • kosievdmerwe 10y ago
        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.