3 ms·
While "real" numbers are indeed weird, I don't think that's the real explanation here. There are lots of small programs with complex output that have nothing to
by andrewflnr 10y ago
While "real" numbers are indeed weird, I don't think that's the real explanation here. There are lots of small programs with complex output that have nothing to do with real numbers. If someone gave you one of these programs without telling you what it was for, real numbers would at best be a useful abstraction (bear in mind that there are no actual "real numbers" here, only finite bit-strings). But it might turn out to be the equivalent of a stream cipher, instead. That would, if done correctly, have even more apparent entropy than your typical fractal, which at least has some higher-level structure.
In my view, the real source of complexity is the fact that the algorithm can use arbitrary iterations to magnify small differences. It's the unpredictable nature of computing machines, not real numbers. The nature of real numbers is only a guide to developing and explaining that underlying complexity.
- wyager 10y agoBut computing machines aren't unpredictable. They are very predictable. They appear to pull complex structure out of the aether. Perhaps the interesting thing is that the set of n-bit programs expands to only 2^n possible outputs. Why are some finite number of infinite-length outputs accessible, but not others? Why does nature favor those sequences?
- Grue3 10y ago>But computing machines aren't unpredictable. They are very predictable. Are they though? A 5-state Turing machine might seem trivial, but there exist programs in it, that we don't know if they ever halt or not [1]. Their behavior is totally non-deterministic for our understanding. There are also minimalistic cellular automata that produce completely unpredictable patterns. [2] [1] https://en.wikipedia.org/wiki/Busy_beaver#Known_values_for_.CE.A3_and_S https://en.wikipedia.org/wiki/Busy_beaver#Known_values_for_.... [2] https://en.wikipedia.org/wiki/Rule_110 https://en.wikipedia.org/wiki/Rule_110
- andrewflnr 10y agoSee also the turing machines whose halting behavior is independent of ZFC. http://www.scottaaronson.com/blog/?p=2725 http://www.scottaaronson.com/blog/?p=2725