0
$\begingroup$

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?

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

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.

$\endgroup$
7
  • $\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
    Feb 13 '19 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$ Feb 13 '19 at 10:48
  • $\begingroup$ Indeed (too late to edit comment). $\endgroup$
    – Aryeh
    Feb 13 '19 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$ Feb 13 '19 at 12:48
  • 1
    $\begingroup$ Eventually minorized? $\endgroup$
    – Aryeh
    Feb 13 '19 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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