Hacker News Reader

Comment by skissane | Hacker News Reader

I'm struggling to understand the concept of a "random oracle". I assume any oracle is just an infinite string of bits, or natural numbers, or suchnot, and thus is countably infinite (and has order omega), so there would be uncountably many (2^aleph-null) such oracles - how does one pick one at random, such that they are (I assume) equally likely? How does one pick a random element from an uncountable set?

And then, if I pick any oracle at random, then isn't there an infinitesimal (yet non-zero) chance I could pick one which has a special structure which makes their result false?

View on HN

An oracle would be a sequence that give you a correct answer to a problem (or set of problems).

You could use Kolmogorov randomness to say whether this sequence is also random: "Kolmogorov randomness – also called algorithmic randomness – defines a string (usually of bits) as being random if and only if it is shorter than any computer program that can produce that string."

http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogoro...

How do you identify the length of a program to determine that? If I had a presumably random string and an assembly dialect that had a command that outputs that exact string, the 'program' has been deferred to the hardware or the brain of its inventor. I can understand how that is still a long program, but I can't understand how that would be measured.

Kolmogorov complexity is not a single value - it's more of a function f(universal computer, string) -> <minimal length of program to output that string>.

It of course depends on the "assembly dialect". But given any two "assembly dialects" A1 and A2 their respective "length functions" f1 and f2 produce the same result, up to a constant. The idea is that you can write an emulator of A2 in A1 - code of constant length.

>And then, if I pick any oracle at random, then isn't there an infinitesimal (yet non-zero) chance I could pick one which has a special structure which makes their result false?

No, the probability is zero. Which, note, does not mean it's impossible. That's a common misunderstanding of probabilities. E.g., if space is infinitely divisible, then for any particular point on a dartboard, the odds you'll hit that point are 0, and yet this doesn't imply it's impossible to hit the dartboard

Theorems 1 and 3 are finitary and easier to physically interpret. As for Theorem 2, "With probably p a random foo has property bar" intends no interpretation of "random foo"; it merely claims that the set of foo's with property bar has measure p with respect to some probability measure. In this case, the probability measure is the Bernoulli measure.

http://www.encyclopediaofmath.org/index.php/Bernoulli_measur...

>And then, if I pick any oracle at random, then isn't there an infinitesimal (yet non-zero) chance I could pick one which has a special structure which makes their result false?

Almost surely not

So then, their result isn't certainly true, only almost surely true?

"with probability 1" is a fairly standard phrasing that is equivalent to infinitesimally-small probability (e.g., a more precise statement might be: the set of oracles where the result is not true has "zero Lebesgue measure" -- I haven't checked to see exactly what formal statement they use).

Reply on news.ycombinator.com