What Comes After 8?

How much information does the present contain about the rule that produced it?

Because I'm taking up AI search methods and DL this term, I figured it was probably time to jog a part of my brain that has been sitting around collecting dust for the last 2 years. I haven't done a proper mathematical or algorithmic problem in what feels like forever.

So to remove the rust, I wanted to do something simpler. I thought of a sequence:

$$1,\quad 4,\quad 8,\quad \ldots$$

Now try to complete this sequence. Most people immediately start looking for a pattern, so let's try to find one. Maybe it's the differences:

$$3,\quad 4,\quad ?$$

Maybe the ratios:

$$4,\quad 2,\quad ?$$

Maybe there is some hidden rule involving primes, powers, positions, or maybe something else entirely.

There Is No Unique Answer

But what seems interesting to me is that there cannot be a single unique answer for this pattern. Because given only:

$$1,\quad 4,\quad 8$$

we cannot actually know what comes next with the fundamentals of our brain. We can invent infinitely many rules that produce those three numbers and then diverge at the fourth. For example, perhaps the next number is 16 or 13 or 1000. All of these can be made consistent with the information we were given.

So what I meant to say is that the question I wanted to ask wasn't "what comes next?" but rather: how much information does the present contain about the rule that produced it?

Now back to the exercise, let's try to formulate it technically, like a machine or an agent with a memory. Starting simply, you put a number into the machine as input, and it transforms the number according to some rule. Call the rule $F$. If the machine starts with a state $S_t$, then after one step:

$$S_{t+1} = F(S_t)$$

This notation is very simple and all too familiar. It simply describes that the current state is produced by applying a transformation to the previous state.

A Machine With Memory

For example:

$$F(x) = 2x$$

gives us:

$$3 \rightarrow 6 \rightarrow 12 \rightarrow 24 \rightarrow 48$$

If I show you $24$, you can work backwards:

$$24 \rightarrow 12 \rightarrow 6 \rightarrow 3$$

because the transformation has a valid inverse function:

$$F^{-1}(x) = \frac{x}{2}$$

A Machine That Forgets

But now let's build a different machine. This time, it will be a machine that forgets. Suppose we have a function:

$$F(x) = x \bmod 2$$

This function doesn't depend on the scale of the input number here, it just checks only whether the number is even or odd. So:

$$2 \rightarrow 0,\quad 4 \rightarrow 0,\quad 6 \rightarrow 0,\quad 8 \rightarrow 0$$

And:

$$1 \rightarrow 1,\quad 3 \rightarrow 1,\quad 5 \rightarrow 1$$

Now, again, imagine that you encounter the output:

$$0$$

and ask: what was the input? You don't know. It could have been $2$, $4$, $6$, $8$, or any even number, actually. So there are infinitely many possibilities. This function, or machine, has ignored the distinction between them. So:

$$F(2) = F(4) = F(6) = F(8) = 0$$

Here, different inputs have become indistinguishable. (This is me just trying to think out loud, so please bear with me.) And so, once that distinction of the input pattern is gone, no amount of cleverness can recover it from the output alone.

This leads to another fundamental result from physics and thermodynamics: information can disappear without anything disappearing physically.

Removing Distinctions

Now, another example from statistics that pops into my mind: suppose I tell you that a coin was flipped. Before looking at it, there are two possibilities:

$$H,\quad T$$

Now imagine there is some machine that turns both heads and tails into a blank symbol like this:

$$H \rightarrow X$$

$$T \rightarrow X$$

So here, the physical process happened and something came out, but the output again does not tell us which input had occurred. The information about the original distinction has disappeared.

This gives us a useful way of thinking about transformations. A transformation doesn't just move one state of something into another, it can also "remove distinctions" between states. Take our previous example: $a \neq b$, but $F(a) = F(b)$. Two different inputs have produced the same output. So if I only have the output, I cannot tell which of the two inputs I started with.

This is what we rule out when we talk about a 1:1 function, or an injective function. For a function to be 1:1, different inputs must always produce different outputs:

$$a \neq b \implies F(a) \neq F(b)$$

And this gives us a very simple test for whether we can run our machine backwards. If the function is injective, each output corresponds to at most one input. If it isn't, different possible pasts and inputs can lead to the same present and output. So given $S_{t+1} = F(S_t)$, we ask: can I recover $S_t$ if I only know $S_{t+1}$? The information needed to distinguish those possibilities is not in the output.

Erasing a Bit

Now consider a single bit:

$$0, 1 \rightarrow 0$$

Two possible states have been forced into one. Nothing necessarily disappeared physically and the original system is still there. But our ability to distinguish which of the two states it originally was has vanished.

This is what is meant by logical information erasure, commonly discussed in physics and thermodynamics. Also explained by Landauer's principle which tells us that, under idealized conditions, erasing one bit of information has a minimum thermodynamic cost:

$$E_{\min} = k_B T \ln 2$$

I find this connection more interesting as initially I thought of functions and distinguishable states and eventually it turns into a statement about physical energy.

And that brings me back to the random tiny sequence I started with:

$$1,\quad 4,\quad 8,\quad ?$$

"How much information does the present actually contain about what produced it?" So I started from a question with a sequence puzzle, and then connected it with functions, computation, information, and physics.

This was the end of my little exercise. To the seniors and folks with deeper experience, I welcome similar cross-domain analogies or connections that have helped these concepts click for you. I'd love to hear them so we can all learn from it.