<p>The function <span class="math-container">$PP(n)$</span> is essentially the Kolmogorov complexity of the number <span class="math-container">$n$</span>, and is non-computable by standard arguments, which I present below.</p>

<p>Suppose to the contrary that <span class="math-container">$PP$</span>
is computable. Then so is the function <span class="math-container">$f:k\mapsto n$</span> that maps a number <span class="math-container">$k\in\mathbb{N}$</span>
to the least integer <span class="math-container">$n$</span> such that <span class="math-container">$PP(n)&gt;k$</span>. (Such an <span class="math-container">$n$</span> always exists by simple counting arguments.)
If <span class="math-container">$PP$</span> is computable then so is <span class="math-container">$f$</span>.</p>

<p>Now define the Turing machine <span class="math-container">$M$</span> as follows:
<span class="math-container">$M$</span> prints <span class="math-container">$f(|M|)$</span> ones, where <span class="math-container">$|M|$</span> is the number of states in <span class="math-container">$M$</span>.
Thus, <span class="math-container">$M$</span> has size <span class="math-container">$\ell=|M|$</span>,
and it prints 
a string of <span class="math-container">$\ell$</span> ones.
By construction, <span class="math-container">$PP(\ell)&gt;\ell$</span>,
and so
<span class="math-container">$\ell$</span> 
ones cannot be printed by any TM with <span class="math-container">$\ell$</span> states or fewer.
Contradiction.</p>

CC BY-SA 4.0
2019-02-13T10:30:40.500Z
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.
Aryeh
CC BY-SA 4.0
2019-02-13T10:48:12.597Z
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
CC BY-SA 4.0
2019-02-13T10:51:29.800Z
Indeed (too late to edit comment).
Aryeh
CC BY-SA 4.0
2019-02-13T12:19:54.740Z
So in fact PP grows *slower* than any computable function! Cool!
Aryeh
CC BY-SA 4.0
2019-02-13T12:48:00.733Z
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
CC BY-SA 4.0
2019-02-13T12:52:21.543Z
Eventually *minorized*?
Aryeh
CC BY-SA 4.0
2019-02-13T12:56:28.973Z
Sorry, minorized, yes.
Emil Jeřábek
CC BY-SA 4.0
2019-02-13T09:14:52.813Z
2019-02-13T09:14:52.813Z
Aryeh
<p>I came across the <a href="http://googology.wikia.com/wiki/Placid_platypus_function" rel="nofollow noreferrer">Placid Platypus</a> function <span class="math-container">$PP(n)$</span> today, defined as the minimal number of states needed for a turing machine that prints a string of <span class="math-container">$n$</span> ones and halts. This function is claimed to (eventually) grow faster than any computable function, similar to the busy beaver function.</p>

<p>However, it is trivial to upper bound this function: consider the turing machine with <span class="math-container">$n+1$</span> states. It's transition function is simply (have it start in state 1):</p>

<ul>
<li>If in state <span class="math-container">$k \leq n$</span>, go to state <span class="math-container">$k+1$</span>, write <span class="math-container">$1$</span> on the tape, then move left</li>
<li>If in state <span class="math-container">$n+1$</span>, halt</li>
</ul>

<p>This will write a string of <span class="math-container">$n$</span> ones, thus, <span class="math-container">$PP(n) \leq n+1$</span>, disproving the claim that the Placid Platypus function grows faster than any computable function.</p>

<p>What am I missing?</p>

CC BY-SA 4.0
2019-02-13T07:22:07.320Z
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
CC BY-SA 4.0
2019-02-13T07:56:57.610Z
In the Growth rate tab on the side, it has the same >= as the busy beaver article?
Phylliida
CC BY-SA 4.0
2019-02-13T08:49:08.857Z
Oh. Well, that’s wrong, then. Read the actual text.
Emil Jeřábek
CC BY-SA 4.0
2019-02-13T08:54:01.480Z
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
CC BY-SA 4.0
2019-02-16T04:57:08.767Z
@EmilJeřábek awesome thanks, good to hear it is wrong and I wasn't missing anything
Phylliida
<computability><turing-machines>
Why does the Placid Platypus function grow faster than any computable function?
Phylliida
# Why does the Placid Platypus function grow faster than any computable function?

(Asked by: username_0 on 2019-02-13)

I came across the [Placid Platypus](http://googology.wikia.com/wiki/Placid_platypus_function) 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?

**Tags:** computability, turing-machines

> **Comments:**
> **username_1**: 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.  
> **username_0**: In the Growth rate tab on the side, it has the same >= as the busy beaver article?  
> **username_1**: Oh. Well, that’s wrong, then. Read the actual text.  
> **username_1**: 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).  
> **username_0**: @EmilJeřábek awesome thanks, good to hear it is wrong and I wasn't missing anything  

---

## 1 answers

### Answer by username_2 on 2019-02-13. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_2**: 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.  
> **username_1**: 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$.  
> **username_2**: Indeed (too late to edit comment).  
> **username_2**: So in fact PP grows *slower* than any computable function! Cool!  
> **username_1**: 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).  
> **username_2**: Eventually *minorized*?  
> **username_1**: Sorry, minorized, yes.  

---

