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?

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

1 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.

  • $\begingroup$ Update: In particular, having a computable upper bound on PP allows one to effectively compute this function (by the same argument as for BB), which answers the OP's question. $\endgroup$
    – Aryeh
    Commented Feb 13, 2019 at 10:30
  • 1
    $\begingroup$ 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$. $\endgroup$ Commented Feb 13, 2019 at 10:48
  • $\begingroup$ Indeed (too late to edit comment). $\endgroup$
    – Aryeh
    Commented Feb 13, 2019 at 10:51
  • 1
    $\begingroup$ 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). $\endgroup$ Commented Feb 13, 2019 at 12:48
  • 2
    $\begingroup$ Eventually minorized? $\endgroup$
    – Aryeh
    Commented Feb 13, 2019 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.