0

Let $f$ be a function that is recursive but not primitive recursive, and let $\mathcal M$ be a Turing machine which computes $f$. I am trying to prove that the function

$$ g(x) = \sup\{\mathcal M(y)|y\le x\} $$

is not primitive recursive. I know that a function is primitive recursive if and only if its graph is PR and is bounded by a PR function. Also I know that if a function is increasing then it is PR if and only if its image is PR.

I've mostly tried proof by contradiction: Assume $g$ is PR and show that $f$ is PR. It seems like $im(f)=im(g)$, and clearly $g$ is increasing. So therefore $im(f)=im(g)$ is PR. But we cannot yet conclude that $f$ is PR. Certainly also $f\le g$ and we are assuming that $g$ is PR, so we only need to show that the graph of $f$ is PR. But I don't see a way to prove that.

Addem
  • 5,656

1 Answers1

1

This isn't true in general. What if $ran(f)$ is bounded? In this case $g$ is eventually constant, and every eventually constant function is PR.

(To see that there are recursive non-PR functions with bounded range, let $\mathscr{H}=(h_i)_{i\in\mathbb{N}}$ be the standard enumeration of PR functions and consider the function $$f(x)=\begin{cases} 1 & \mbox{ if }h_x(x)=0\\ 0 & \mbox{ otherwise}. \end{cases}$$ This $f$ is clearly not PR and has bounded range, and $f$ is recursive since the PR functions are total and our enumeration of PR functions $\mathscr{H}$ was "reasonable." More generally, for any reasonably-indexable class of total recursive functions there will be total recursive bounded functions not in that class by the same argument.)

Noah Schweber
  • 245,398
  • Ah, I realized I neglected a part of what the problem should be -- rather than $\sup{\mathcal M(y)| y\le x}$ it should instead be the sup over the running time of the machine $\sup{T_{\mathcal M}|y\le x}$. – Addem Apr 28 '23 at 22:56