The structures of computation and the mathematical structure of nature (2010)

Post by ukj » Thu, Mar 26, 2020, 2:40 PM UTC

yters wrote: post #11

ukj wrote: post #10

Earlier quoted context omitted.

Not really. You are still in the paradigm of computation. Detecting anything is signal processing. And if I am wrong about this - all the better! It is exactly the right kind of wrongness we need to progress science.

Let's say I have a computer that can only store 10 bits worth of information, but generates 100 bits of information. Then obviously the information cannot entirely originate in the computer.

Post by ukj » Thu, Mar 26, 2020, 4:06 PM UTC

yters wrote: post #13

ukj wrote: post #12

Earlier quoted context omitted.

Sure it can. Compression. Kolmogorov complexity. I don't need to 'store' the infinite set of natural numbers - that would require infinite space (memory). But I can describe the infinite set in a single line of Python. Nat = lambda x=0: Nat(x+1) It's just a space-time tradeoff.

If the sequence isn't compressible, then you can eliminate that possibility.

Post by ukj » Thu, Mar 26, 2020, 5:06 PM UTC

yters wrote: post #15

ukj wrote: post #14

Earlier quoted context omitted.

You can never determine this with 100% certainty - that is what we have falsification for. The non-compressibility of a sequence is a falsifiable claim. All it takes is a single demonstration of successful compression.

for limited runtime you can

Post by ukj » Thu, Mar 26, 2020, 7:03 PM UTC

yters wrote: post #17

ukj wrote: post #16

Earlier quoted context omitted.

So you were unable to compress the stream given the allocated time. Perhaps you could've compressed it had you kept running for just a second longer?

i mean run all the shorter bitstrings until time runs out or they terminate.

Post by ukj » Fri, Mar 27, 2020, 8:09 AM UTC

yters wrote: post #19

ukj wrote: post #18

Earlier quoted context omitted.

How does “time run out” in practice other than you putting an upper bound on your computation? Obviously, the code will not halt until it compresses the stream successfully.

enumerate all bitstrings of length 10. run them for N steps. if none terminate on the target bitstring of length 100, then we've eliminated the computation hypothesis for 10 bits and N runtime if we continue this approach and eliminate all the available storage and time available, then we eliminate the computation hypothesis altogether for our scenario