Inverse Collatz's Tape
Consider an empty tape with all unmarked cells, such that the reading head (standing initially in the middle of the tape) applies the collatz function to a starting $n$:
\[f(n) = \begin{cases} n/2 & \text{if} \quad n \equiv 0 \quad (\text{mod}\, 2) \\ (3n + 1)/2 & \text{if} \quad n \equiv 1 \quad (\text{mod}\, 2) \\ \end{cases}\]flipping the state of the cell it currently stands in, and then moving left if $n$ is odd, and right if $n$ is even. It will do this until $n = 1$ is reached. Consider the example of $n = 27$:
and the corresponding tape development over time (↓):
For the prior example we have a stopping time of $τ = 70$, and a score fuction $Σ$, which returns the amount of 1s (or marked states) left in the tape after $τ$ iterations, of $Σ = 6$.
Now, much in the same way that one can think about the Inverse Busy Beaver in the context of the Busy Beaver problem:
- What’s the minimal number of states $k$ that a Turing Machine with $k$ states and 2 symbols (from a set of size $(4(k + 1))^{2k}$) needs so as to produce a tape with a specific $Σ$?
we can also think about what’s the smallest collatz number $n$ which will produce a tape with a specific $Σ$. The following figure shows precisely that, over a range of $Σ = 0$ to $Σ = 37$ (here $\log$ scale for $n$ is using $\ln$):
