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:
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):
