4 ms·
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
by ukj 7y ago
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.
- yters 7y agoIf the sequence isn't compressible, then you can eliminate that possibility.
- ukj 7y agoYou 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.
- yters 7y agofor limited runtime you can
- ukj 7y agoSo 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?
- yters 7y agoi mean run all the shorter bitstrings until time runs out or they terminate.
- ukj 7y agoHow 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.
- yters 7y agoenumerate 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
- ukj 7y agoYou understand that "Number of bitstrings of length 10" is a function of the cardinality of your alphabet, right? A binary alphabet has 2^10 such strings. A decimal alphabet has 10^10 such strings. So before you can make the assertion you've made you first have to answer two question: 1. How many symbols does your alphabet contain? 2. How did you choose that number? Down that path you arrive the Linear speedup theorem. https://en.wikipedia.org/wiki/Linear_speedup_theorem https://en.wikipedia.org/wiki/Linear_speedup_theorem
- yters 7y agobit is base 2 as far as i know yes, there is always a turing machine that can generate the target with any performance characteristics so, the key is to keep the reference turing machine fixed
- ukj 7y agoYou can’t keep the reference Turing machine fixed in light of the linear speed up theorem. Hence the argument for compression. A Turing machine with a better language is faster. It compresses time.
- 7y ago