I was thinking about what would it mean for a sequence of bits to be "anti-inductive". It probably is a concept that is already known (as a rule of thumb, if I can think about it, someone probably already wrote a paper on it 50 years ago), but I haven't heard about it.

*

Some sequences are predictable and can be compressed. These two concepts are deeply related, because if you can successfully predict the next part of the sequence, you don't need to actually write it down; hence compression. A completely random sequence of bits cannot be compressed or predicted.

There is a simple mathematical proof that some sequences cannot be compressed, although it doesn't say which ones. For any natural number N, there are more sequences of size exactly N, than sequences of size smaller than N. Therefore no program can generate a unique sequence shorter than [...]

---

First published:
August 14th, 2024

Source:
https://www.lesswrong.com/posts/6bnushzT6mtTfwhSF/an-anti-inductive-sequence

---

Narrated by TYPE III AUDIO.

“An anti-inductive sequence” by Viliam

LessWrong (30+ Karma)