-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?

$\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 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 at 7:56
  • 1
    $\begingroup$ Oh. Well, that’s wrong, then. Read the actual text. $\endgroup$ – Emil Jeřábek Feb 13 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 at 8:54
  • $\begingroup$ @EmilJeřábek awesome thanks, good to hear it is wrong and I wasn't missing anything $\endgroup$ – Phylliida Feb 16 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$
  • $\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 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 at 10:48
  • $\begingroup$ Indeed (too late to edit comment). $\endgroup$ – Aryeh Feb 13 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 at 12:48
  • 1
    $\begingroup$ Eventually minorized? $\endgroup$ – Aryeh Feb 13 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.