3 ms·
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 sequenc
by joe_the_user 12y ago
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#Kolmogorov_randomness http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogoro...
- Retra 12y agoHow 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.
- TheLoneWolfling 12y agoKolmogorov complexity is not a single value - it's more of a function f(universal computer, string) -> <minimal length of program to output that string>.
- mherrmann 12y agoIt 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.