-1
$\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?

| cite | improve this question | | | | |
$\endgroup$
  • 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$ – Emil Jeřábek 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$ – Emil Jeřábek 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$ – Emil Jeřábek 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.

| cite | improve this answer | | | | |
$\endgroup$
  • $\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$ – Emil Jeřábek 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$ – Emil Jeřábek 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.