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..".


$\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)$.)

  • $\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$ – Gerhard Paseman May 6 '13 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$ – Emil Jeřábek May 6 '13 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$ – Emil Jeřábek May 6 '13 at 16:42
  • $\begingroup$ It's likely that you and I are meaning different things by "unbounded search" and "minimization". (It's also possible I left out something.) I will look for some old notes to help me clarify. Two important points: in standard references (e.g. Soare, Hartley), certain classes of total functions which are recursive form clones and are given redundant bases; with closure under (some form of) recursion one can define some of the base functions in terms of others. Rosza among others worked on finding (near-) minimal bases. Gerhard "But Wait, There's Still More!" Paseman, 2013.05.06 $\endgroup$ – Gerhard Paseman May 6 '13 at 17:50
  • 1
    $\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$ – Emil Jeřábek Nov 29 '16 at 13:27

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$).

  • $\begingroup$ What are these two $\Delta_0$ functions that we can go with? $\endgroup$ – user10891 May 6 '13 at 12:38
  • $\begingroup$ Frank, I edited the answer to add those. $\endgroup$ – Asaf Karagila May 6 '13 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$ – Joel David Hamkins May 6 '13 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 '13 at 12:52
  • $\begingroup$ Joel, thank you for your comment. I edited accordingly. $\endgroup$ – Asaf Karagila May 6 '13 at 13:04

Your Answer

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