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

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?

• Where did you see the claim? The article you link to, as well as the paper linked there, both claim the opposite. The Harland paper even explicitly includes your bound. Feb 13, 2019 at 7:22
• In the Growth rate tab on the side, it has the same >= as the busy beaver article? Feb 13, 2019 at 7:56
• Oh. Well, that’s wrong, then. Read the actual text. Feb 13, 2019 at 8:49
• Wikia is extremely unreliable. The claim that the function is not known to be uncomputable is also likely bogus (and is contradicted on the talk page). Feb 13, 2019 at 8:54
• @EmilJeřábek awesome thanks, good to hear it is wrong and I wasn't missing anything Feb 16, 2019 at 4:57

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.
• You mean a computable lower bound (which, furthermore, goes to infinity). There are computable upper bounds, such as the one given in the question, or even $PP(n)\le c\log n$ for a suitable constant $c$. Feb 13, 2019 at 10:48
• Well, it is not eventually majorized by any computable function, i.e., it is slower than any given computable function on infinitely many inputs. However, a simple counting argument also shows that it is $\Omega(\log n)$ infinitely often (in fact, on a set of inputs with asymptotic probability 1). Feb 13, 2019 at 12:48