Hacker News new | ask | show | jobs
by SilasX 3513 days ago
Can you explain that further? A random oracle is a random set of strings...?
1 comments
tromp 3513 days 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.

link
SilasX 3513 days ago
So, a language is a mapping from strings to 1/0? And an oracle is a language?
link
kosievdmerwe 3513 days 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.
link