2 ms·
> we can just get it complex enough that we can't accurately pre-determine what will happen. Which is observably indistinguishable from indeterminism.
by naasking 8y ago
> we can just get it complex enough that we can't accurately pre-determine what will happen.
Which is observably indistinguishable from indeterminism.
- szemet 8y agoIt is not possible universally. I like the proof of this, it is simple and resembles to many similar no-go theorems (like the halting problem). 1. Imagine a finite formal system which universally can identify if an input is regular (compressible) or random (not compressible) / So we are using the Kolmogorov-complexity definition of randomness here... 2. Assume the above formal system can be described using L bits (e.g. it is an L bit long program) 3. Lets take the first (e.g. smallest in numerical ordering) 2×L (or 10×L, 100×L, ... take it as large you want) long bit string that the program classifies as random bit string 4. "3." is a definition of a 2×L long string in L bits (the formal system itself) + constant 5. The 2×L long string is therefore compressibe so it is not random - but our original algorithm is misclassify it as random (it is in its definition) - so the algorithm is not universal...