Background
David Deutsch's paper The Structure of the Multiverse is concerned with the theory of quantum information and quantum computation, but the first few pages contain a purely mathematical prelude. While reading this prelude, I failed to understand one equation in particular.
He begins by considering a classical reversible computational network N with bits $B_1$,...,$B_N$. The functions $b_1(t)$,...,$b_N(t)$ represent the boolean value of the bits just after the $t$'th computational step. We can refer to this sequence of bits as the number $b(t)=2^{N-1}b_N(t) + ... + 2b_2(t) + b_1(t)$.
During each computational step, the values of the bits in the network change according to this equation:
$$ b(t+1)=f_t(b(t)) \tag{1}\label{eq1} $$
Where each $f_t$ is some invertible function from $Z_{2^N}$ to itself, which characterizes the action of all the gates through which the bits pass during the $(t+1)$'th computational step.
All good so far.
On page 5, he introduces the notion of a multiset, which he describes as an NM-bit network that is a multiset of M networks, each with N bits. He further introduces the notion of multiplicity, which is denoted as $\mu_b(t)$ and defined as the number of sub-networks that are in the state $b \in Z_{2^N}$ at time $t$.
Again, all good so far. But he loses me here, when he introduces the equation of motion for how the $\mu$ multiplicities evolve over time:
$$ \mu_b(t+1) = \mu_{f^{-1}_t(b)}(t) \tag{2}\label{eq2} $$
I don't understand how he can use the inverse function $f^{-1}_t$ generically for any $b$ when each function $f_t$ is defined for one and only one $b$. Let me take a concrete example so you see what I mean.
Example
Time t=0
Say that M=2 and N=2, and that the initial state of the network is this:
- N1: (0,1)
- N2: (1,1)
The multiset of multiplicities ${\mu_0(0),\mu1(0),\mu_2(0),\mu_3(0)}$ is this:
- {0,1,0,1}
Computation
Let's define $f_0$ as a function that takes (1,0) and outputs (0,0):
$$ f_0((0,1))=(0,0) $$
It follows that its inverse is:
$$ f^{-1}_0((0,0))=(0,1) $$
Equivalently, we can define these using the succinct form $b(t)$:
$$ f_0(1)=0\\ f^{-1}_0(0)=1 $$
Time t=1
By applying the computation $f_0$ onto the NM-bit network, we get this new network at time t=1:
- N1: (0,0)
- N2: (1,1)
And the multiset of multiplicities ${\mu_0(1),\mu1(1),\mu_2(1),\mu_3(1)}$ is this:
- {1,0,0,1}
In English:
- $\mu_0$ went from 0 to 1 (because now there's one sub-network in the state (0,0))
- $\mu_1$ went from 1 to 0 (because there's no sub-network in the state (1,0) anymore)
- $\mu_2$ and $\mu_3$ remained the same
Question
I can see why equation $\eqref{eq2}$ holds for $\mu_0$:
$$ \mu_0(1)=\mu_{f^{-1}_0(0)}(0) $$
We know what's the output of $f^{-1}_0(0)$, so let's substitute it:
$$ \mu_0(1)=\mu_1(0) $$
Checks out, since we know that the multiplicity of the 0 state is time t=1 is 1 and that the multiplicity of state 1 at time t=0 is also 1.
But I cannot for the life of me understand how equation $\eqref{eq2}$ holds for $\mu_1$, $\mu_2$ and $\mu_3$, or to put it otherwise, I don't understand how it can be an equation of motion for the entire network. The inverse of the function $f_0$ is simply not defined when the input $b$ is 1, 2 or 3 - it's only defined when the input $b$ is 0. So I can't understand how $\eqref{eq2}$ can be considered an equation of motion for all multiplicities.
If we were to define $f_0$ for when $b$ is 0:
$$ f_0(0)=0 $$
We could no longer use its inverse, since $f_0$ would not be bijective anymore (inputs 0 and 1 would both lead to the same output 0).
I expected the equation of motion for the multiplicities to be some sort of piecewise function, such that each multiplicity of a given state that is left untouched by the computation is simply equal to the multiplicity of the state thereof at the previous time.
What am I missing?