5 ms·

Would it be considered cheating if you found a pseudo random generator that took a small seed and expanded to the executable of the current first place winner?

nabla9 13y ago
No. It would just mean that you are a God. I mean, if there would be God and he would want to prove that he really is all powerful, he would have to be able to pull that kind of trick to convince me.
- Eliezer 13y ago
  I think that's a bit strict. The Judeo-Christian God, if functioning exactly as advertised, shouldn't be able to do that.
  - tedks 13y ago
    That depends on the advertising you decide to accept as valid; I'm sure none of my Christian friends would agree with you, assuming I could explain the scenario to them.
    - gatehouse 13y ago
      If you take it for granted that the pretext of the question is an analogy of the creation of the universe, and the consequence of the ability is the knowledge of all that occurs, then that isn't how omniscience was explained to me because a key aspect of Catholicism is free will, and that would allow God to sort out the sinners without running the "experiment", viz. the universe. I have to mention that this is only according to my meagre and disinterested understanding.
deleted 13y ago
[deleted]
klodolph 13y ago
It is a common misconception among people designing compression algorithms that such a technique is possible at all in general, or feasible for specific cases (it is neither). As an illustration, consider a shuffled deck of playing cards, and you want to find a seed for your random number generator so you can just store the seed instead of the entire deck. If your seed is a 64-bit number, then the chance that you can represent the deck using a seed is about 1 in 4x10^48, or basically zero. Or phrased the opposite way, if you use a random number generator with a 64-bit state to shuffle a deck, then the vast majority of possible decks will never be output by your shuffling program.
RoboTeddy 13y ago
It's true that a given small seed can generate a long sequence. Sequences like these have low http://en.wikipedia.org/wiki/Kolmogorov_complexity http://en.wikipedia.org/wiki/Kolmogorov_complexity, since it's possible to write a short program that generates the comparatively long sequence. A pseudo-random number generator with a seed length of 64 bits is capable of generating about 2^64 possible sequences (roughly one for each possible seed). Given a random long sequence, though, it's quite unlikely that there's a short seed that will generate it; given a seed size of 64 bits and a random sequence of 100 bits, for example, the chance that there's a seed that will generate the sequence is roughly (2^64)/(2^100), or about 1 in 100 billion. A theoretically optimal solution to Hutter's challenge would somehow notice whenever this happens to be the case, across all possible seeds and all possible sequence-generating functions, and provide the seed and function as the solution! So, no: it wouldn't be cheating. But, it's statistically likely to be impossible.
mapt 13y ago
No, this would be precisely the sort of optimization that they are seeking. But... It's hard. To do this over large numbers of high-entropy bits with a small seed (varying) and some simple algorithm (varying) rapidly requires a search space of a scale implying more computation than might plausibly be made to exist in our observable universe. There has to be a minimum-message-length compression solution for any arbitrary message and decoder environment (whether their code or the uncompressed text), but good luck provably finding it for messages even as long as this post. "You would have to be a god" is a reasonable response if it's talking about using computation capability outside of our observable universe and the physical rules we understand it by.

nabla9 13y ago

No. It would just mean that you are a God. I mean, if there would be God and he would want to prove that he really is all powerful, he would have to be able to pull that kind of trick to convince me.

Eliezer 13y ago
I think that's a bit strict. The Judeo-Christian God, if functioning exactly as advertised, shouldn't be able to do that.
- tedks 13y ago
  That depends on the advertising you decide to accept as valid; I'm sure none of my Christian friends would agree with you, assuming I could explain the scenario to them.
  - gatehouse 13y ago
    If you take it for granted that the pretext of the question is an analogy of the creation of the universe, and the consequence of the ability is the knowledge of all that occurs, then that isn't how omniscience was explained to me because a key aspect of Catholicism is free will, and that would allow God to sort out the sinners without running the "experiment", viz. the universe. I have to mention that this is only according to my meagre and disinterested understanding.

deleted 13y ago

[deleted]

klodolph 13y ago

It is a common misconception among people designing compression algorithms that such a technique is possible at all in general, or feasible for specific cases (it is neither). As an illustration, consider a shuffled deck of playing cards, and you want to find a seed for your random number generator so you can just store the seed instead of the entire deck. If your seed is a 64-bit number, then the chance that you can represent the deck using a seed is about 1 in 4x10^48, or basically zero. Or phrased the opposite way, if you use a random number generator with a 64-bit state to shuffle a deck, then the vast majority of possible decks will never be output by your shuffling program.

RoboTeddy 13y ago

It's true that a given small seed can generate a long sequence. Sequences like these have low http://en.wikipedia.org/wiki/Kolmogorov_complexity http://en.wikipedia.org/wiki/Kolmogorov_complexity, since it's possible to write a short program that generates the comparatively long sequence. A pseudo-random number generator with a seed length of 64 bits is capable of generating about 2^64 possible sequences (roughly one for each possible seed). Given a random long sequence, though, it's quite unlikely that there's a short seed that will generate it; given a seed size of 64 bits and a random sequence of 100 bits, for example, the chance that there's a seed that will generate the sequence is roughly (2^64)/(2^100), or about 1 in 100 billion. A theoretically optimal solution to Hutter's challenge would somehow notice whenever this happens to be the case, across all possible seeds and all possible sequence-generating functions, and provide the seed and function as the solution! So, no: it wouldn't be cheating. But, it's statistically likely to be impossible.

mapt 13y ago

No, this would be precisely the sort of optimization that they are seeking. But... It's hard. To do this over large numbers of high-entropy bits with a small seed (varying) and some simple algorithm (varying) rapidly requires a search space of a scale implying more computation than might plausibly be made to exist in our observable universe. There has to be a minimum-message-length compression solution for any arbitrary message and decoder environment (whether their code or the uncompressed text), but good luck provably finding it for messages even as long as this post. "You would have to be a god" is a reasonable response if it's talking about using computation capability outside of our observable universe and the physical rules we understand it by.