4
$\begingroup$

It is customary to define the class of partial recursive functions by taking the set of primitive recursive functions $PR$ and taking closure over unbound search operation.

Do we need the "whole" set of primitive recursive functions as a base to reach the class of partial recursive functions with the closure? It seems reasonable to assume that unbound search could be used in the place of primitive recursion to reach the class $PR$ from a smaller base class.

For example Grzegorczyk proves that

Every computable function can be presented in the form $f(u)=A(ix[B(u,x)=0])$, where $A$ and $B$ are functions of the class $\mathcal{E}_0$.

Here $ix[B(u,x)=0]$ is the unique $x$ such that $B(u,x)=0$ and $\mathcal{E}_0$ is the lowest set in Grzegorczyk-hierarchy. I don't, however, see how to change the "unique $x$ such.." to "smallest $x$ such..".

$\endgroup$

2 Answers 2

7
$\begingroup$

$\def\dotm{\mathbin{\dot-}}$It follows from the MRDP theorem that every partial recursive function $f(\vec x)$ can be written as $$f(\vec x)\simeq l(\mu z\,[p(\vec x,l(z),l(r(z)),\dots,l(r^{k-1}(z)),r^k(z))=0]),$$ where $p(\vec x,y_0,\dots,y_k)$ is a polynomial with integer coefficients, and $l(z)$ and $r(z)$ are the left and right inverse of a pairing function. If we take the Cantor pairing function $$[x,y]=\frac{(x+y)(x+y+1)}2+x,$$ we can express $l(z)=z-[0,g(z)]$, $r(z)=g(z)-l(z)$, where $g(z)=\mu u\,[2z\dotm(u+1)(u+2)=0]$. Thus, partial recursive functions are the closure of projections, successor, multiplication, and limited subtraction under minimization and composition. (Note that $x+y=S(x)S(y)\dotm ((S(x)S(y)\dotm x)\dotm y)$.)

$\endgroup$
11
  • $\begingroup$ Because of being closed under (having all) projections and composition, many of the subclasses of partial recursive functions are clones on the natural numbers. With unbounded search, successor, and the constant function 0, one can then generate the partial recursive functions, which itself is a form of clone of partial functions. I don't think more is needed. Gerhard "Will That Be Small Enough?" Paseman, 2013.05.06 $\endgroup$ May 6, 2013 at 15:26
  • $\begingroup$ @Gerhard: I don’t follow your reasoning. As far as I can see, the set of all functions $f(x_i)$ of the form $x_i+c$, $c$, the always undefined function, and the function mapping $0$ to $c$ and undefined otherwise, where $c$ is a constant, is closed under composition and minimization. Thus zero and successor are not enough to generate all partial recursive functions. Even more generally, the set of all partial functions depending on at most one argument is also closed under minimization and composition, so you need some function essentially depending on at least two arguments. $\endgroup$ May 6, 2013 at 16:21
  • $\begingroup$ For more fun, the set of functions definable in Presburger arithmetic is also closed under composition and minimization, so it is essential to have something more complicated (such as multiplication) in the list of basic functions. $\endgroup$ May 6, 2013 at 16:42
  • 2
    $\begingroup$ @FFF Even more strongly, it can be made coNLOGTIME: let $B(u,x)$ be the predicate “$x$ is a transcript of an accepting run of $M$ on input $u$”, where $M$ is a fixed Turing machine. (To make life easy, ensure that each configuration in the transcript is written using the same number of bits, which is a power of $2$.) This can be checked in coNLOGTIME as the validity of a Turing machine computation amounts to local conditions. $\endgroup$ Nov 29, 2016 at 13:27
  • 1
    $\begingroup$ On second thoughts, it can even be made DLOGTIME by padding $x$ to exponential length. While it might be tempting to use more padding to make it faster yet, the Turing machine model (even with oracle-like random-access input as employed here) cannot compute anything nontrivial in sublogarithmic time, as this would not be enough to even produce an upper bound on the length of the input. $\endgroup$ Dec 2, 2016 at 15:17
5
$\begingroup$

No. We don't need every primitive recursive function.

In fact every recursive function is the composition of two primitive recursive functions definable by $\Delta_0$ formulas, and using the minimization operator. Since not every primitive recursive function is $\Delta_0$ this shows that you don't really need all the primitive recursive functions after all.

This is because we can write the graph of every recursive function as a $\Sigma_1$ set, i.e. $f(\vec x)=y\iff\exists z\varphi(\vec x,y,z)$, where $\varphi$ is a $\Delta_0$ formula. We can define from $\varphi$ two functions $G$ and $H$ as follows:

  • $G(\vec x,w)=\min_{y < w}\exists z < w\varphi(\vec x,y,z)$ - this function returns the least $y$ such that $\varphi(\vec x,y,z)$ holds, if such $z$ exists.
  • $H(\vec x,w)=\exists y < w\exists z < w\varphi(\vec x,y,z)$ - this function returns $0$ if there is such $y$ and $z$ below $w$, and $1$ otherwise.

It is not difficult to see that indeed both $G$ and $H$ are primitive recursive, and defined by $\Delta_0$ formulas.

Now $f(\vec x)=G(\vec x,\mu w H(\vec x,w))$, and one can verify that even if $f$ is a partial function the result is the same (i.e. it does not extend $f$).

$\endgroup$
5
  • $\begingroup$ What are these two $\Delta_0$ functions that we can go with? $\endgroup$
    – user10891
    May 6, 2013 at 12:38
  • $\begingroup$ Frank, I edited the answer to add those. $\endgroup$
    – Asaf Karagila
    May 6, 2013 at 12:41
  • 2
    $\begingroup$ It is not correct to say that "every $\Delta_0$ function is primitive recursive", since there are functions whose graphs are $\Delta_0$, but which are not primitive recursive. These include some very fast-growing functions and there have been a few MO questions about this. Meanwhile, it is true to say that every $\Delta_0$ relation is primitive recursive. $\endgroup$ May 6, 2013 at 12:47
  • $\begingroup$ Thank you. I was not expecting an answer from this perspective so I need to think both the question and the answer a bit further. $\endgroup$
    – user10891
    May 6, 2013 at 12:52
  • $\begingroup$ Joel, thank you for your comment. I edited accordingly. $\endgroup$
    – Asaf Karagila
    May 6, 2013 at 13:04

Your Answer

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