Inverse Collatz's Tape

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}<br>n/2 & \text{if} \quad n \equiv 0 \quad (\text{mod}\, 2) \\<br>(3n + 1)/2 & \text{if} \quad n \equiv 1 \quad (\text{mod}\, 2) \\<br>\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$):

Back