# 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. – Emil Jeřábek Feb 13 '19 at 7:22
• In the Growth rate tab on the side, it has the same >= as the busy beaver article? – Phylliida Feb 13 '19 at 7:56
• Oh. Well, that’s wrong, then. Read the actual text. – Emil Jeřábek Feb 13 '19 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). – Emil Jeřábek Feb 13 '19 at 8:54
• @EmilJeřábek awesome thanks, good to hear it is wrong and I wasn't missing anything – Phylliida Feb 16 '19 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$. – Emil Jeřábek Feb 13 '19 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). – Emil Jeřábek Feb 13 '19 at 12:48