3 ms·

That is not non-determinism; it's just difficult to predict determinism. I postulate that we cannot build non-determinism out of deterministic pieces - we can

• naasking 7y 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 7y ago
    It 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...