An anti-inductive sequence

11Oscar_Cunningham

6Dagon

3Viliam

7cousin_it

2Jalex Stark

6khafra

6tailcalled

5Viliam

4NunoSempere

New Comment

A simple version of this is the sequence 1,2,4,8,16,.... Each term is 1 greater than what you would predict by fitting a polynomial to the preceding terms.

The polynomial restriction is an interesting twist, are you asserting that the space of considered algorithms is *ALWAYS* smaller than the space of actual generative algorithms one might encounter? I think that's a restatement of the uncomputability of the "standard solution", but I have to think more.

The non-restricted proposed method (take all algorithms, inverse weighted by program length, and remove ones that get disproven by observed sequence) likely gets 32 for the next prediction (2^n), but considers 31 as only slightly less likely (regions of a circle created by the chords of n points on the circumference), and others as less likely still.

Yes, it seems that the generated sequence will always be outside the space of considered predictors. When the predictors are polynomial, the sequence can be exponential. When the predictors are algorithms in general, the sequence is uncomputable.

Would it be possible to make a space of all possible predictors? No, because the way the sequence is generated is... kinda like a probabilistic version of Cantor's diagonal argument -- only instead of contradicting the *n*-th prediction in *n*-th step, it tries to contradict the greatest mass of remaining predictions at each step. But that still means that each individual prediction will be contradicted at some moment, because if its prior probability is *p*, then at each step either this specific prediction is contradicted, or some other set of predictions with total probability at least *p* is contradicted, so we arrive at this specific prediction after at most *1/p* steps.

Also, if we want to assign a nonzero prior probability to each prediction, we can only have a countable number of predictions. But there is an uncountable number of possible sequences. Therefore some of them (actually most of them) are outside the set of considered predictions.

possibly an easier entry point to the topic is here

https://en.wikipedia.org/wiki/Chaitin%27s_constant

which is a specific construction that has some relation to the ideas OP has for a construction

You'll be happy to know that standards bodies have noticed the "entropy reduction from excessive rules" problem. The latest version of NIST Special Publication 800-63B says to disallow four password categories like "already in a breach database" and "aaaaa," but goes on to direct verifiers to *not* impose any other rules on password composition.

As for me, I just choose the first four digits of the busy beaver numbers--1621--as my PIN. As a noncomputable number, it's guaranteed to be the most random choice possible.

If you have some limited computational model (e.g. n-th order Markov Chains), you can diagonalize over it in an expanded computational model (e.g. general computation) to get a sequence that is unpredictable in the narrower model.

Found an article by Scott Aaronson on a similar topic (except for the last part)

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

predictableand can becompressed. 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

whichones. 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 auniquesequence shorter than N for any input sequence of size N.*

Things get more complicated if we consider the caveat that although random sequences

in generalcannot be compressed, true randomness means thatsometimeswe accidentally get a sequence thatcanbe compressed -- for example, with probability 1/2ᴺ we get a sequence of N zeroes, and it would sound silly to argue that we can't compress that!The solution to this paradox is that if we decide to compress only

someselected sequences, then we need toadd an extra bitof information specifying whether this sequence was compressed or not. Otherwise, if we see a sequence of bits saying (in binary) "a sequence of thousand zeroes", we wouldn't know whether the intended value is this very sequence of bits taken literally, or the sequence of thousand zeroes. One bit doesn't seem like much, but actuallymostsequences cannot be compressed, so the cost of adding one extra bit toeachof them outweighs the occasional space we would save by compressing the ones we can.But still, if I needed a random sequence of bits to use e.g. as a password for something important... and by a miracle I generated a sequence of N zeroes... I would probably feel quite uncomfortable to use it, and would simply generate a new one. Is this a good security practice, or not? Because from certain perspective, by removing the "insufficiently random" sequences from the pool of possible choices, I am

reducingthe size of the pool, which... kinda makes iteasierto guess the password?Something similar actually happened to me once. I used a mobile application that asked me to create a 4-digit PIN. So I typed 4 random digits, and the application said: "nope, you cannot use the same digit multiple times in the PIN, that is not secure". So I typed 4 random digits again, and the application said: "nope, you cannot use an ascending sequence of digits, that is not secure". So I typed 4 random digits yet again, and this time the application was finally satisfied. But it felt funny that the more "security checks" the application uses, the more limited is the choice of possible PINs. There are only 10000 possible combinations of 4 digits to start with; I wonder how far an overzealous security department could reduce that number. In a hypothetical extreme case, we would be left with only

onepossible choice of PIN -- certainly the most secure one that no one could possibly guess! The holy grail of information security.*

Okay, back to the sequences of bits. Imagine that we are trying to create not just any random sequence, but the single most random, most unpredictable sequence ever! Suppose the length of the sequence is not specified in advance, so we just keep generating bits one by one, for as long as necessary.

What we could do is create a

predictor-- an algorithm that looks at the previously generated bits, tries to find all possible patterns in them and predict the most likely following bit -- and then actually output theopposite. Keep doing this for every bit.(To make the output fully deterministic, we add an extra rule that if the predictor assigns

exactly50% probabilities of the next bit being 0 or 1, we output 0.)What would the generated sequence look like?

We need to make a more formal description of the algorithm, because the reasoning is going to get more complicated at each step, since we are trying to defy expectations.

The standard solution for the predictor would be to use the Solomonoff prior (take

allpossible algorithms that generate sequences of bits, and assign to each of them an initial probability 1/2^ the length of the algorithm), after each observed bitremovethe algorithms that were falsified by the observed data, and then calculate the total probability of the remaining algorithms that predict that 0 would be next, versus the total probability of the remaining algorithms that predict that 1 would be next.This solution is (1) uncomputable, and (2) depends on the exact details of the language used to write the algorithms. But, from the mathematical perspective (once we specify the language for writing the algorithms) it is a formal definition of the most unpredictable sequence.

Yes, it sounds ironic that we have a formal definition of something "unpredictable", but the definition is uncomputable, which means that no

algorithmcan actually predict the sequence, we just have its mathematicaldefinition.So I guess we won't find the following bits of the sequence. At least, not arbitrarily many. Perhaps we could still find two or three more, but each of them would require more complicated reasoning.