Why does the Placid Platypus function grow faster than any computable function?

Question

I came across the Placid Platypus function $PP(n)$ today, defined as the minimal number of states needed for a turing machine that prints a string of $n$ ones and halts. This function is claimed to (eventually) grow faster than any computable function, similar to the busy beaver function.

However, it is trivial to upper bound this function: consider the turing machine with $n+1$ states. It's transition function is simply (have it start in state 1):

• If in state $k \leq n$, go to state $k+1$, write $1$ on the tape, then move left
• If in state $n+1$, halt

This will write a string of $n$ ones, thus, $PP(n) \leq n+1$, disproving the claim that the Placid Platypus function grows faster than any computable function.

What am I missing?

Answer 1

The function $PP(n)$ is essentially the Kolmogorov complexity of the number $n$, and is non-computable by standard arguments, which I present below.

Suppose to the contrary that $PP$ is computable. Then so is the function $f:k\mapsto n$ that maps a number $k\in\mathbb{N}$ to the least integer $n$ such that $PP(n)>k$. (Such an $n$ always exists by simple counting arguments.) If $PP$ is computable then so is $f$.

Now define the Turing machine $M$ as follows: $M$ prints $f(|M|)$ ones, where $|M|$ is the number of states in $M$. Thus, $M$ has size $\ell=|M|$, and it prints a string of $\ell$ ones. By construction, $PP(\ell)>\ell$, and so $\ell$ ones cannot be printed by any TM with $\ell$ states or fewer. Contradiction.