3 ms·
But computing machines aren't unpredictable. They are very predictable. They appear to pull complex structure out of the aether. Perhaps the interesting thing
by wyager 10y ago
But 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