undefined | Better HN

0 pointsyters6y ago0 comments

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.

0 comments

ukj6y 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.

ytersOP6y ago

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

ukj6y ago

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.

ytersOP6y ago

for limited runtime you can

1 more reply

j / k navigate · click thread line to collapse

0 comments

ukj6y 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.

ytersOP6y ago

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

ukj6y ago

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.

ytersOP6y ago

for limited runtime you can

1 more reply

j / k navigate · click thread line to collapse