3
$\begingroup$

I am reading a translation of gödel's original, and i'm a bit confused about the primitive recursive functions.

Everywhere on the internet (or some resources like courses/classes i could put my hands on), the set of basic primitive recursive functions are defined as :

  • zero
  • successor
  • projection
  • composition
  • primitive recursion

every of those functions are talked about in the paper except the "projection" one.

Did I not understand/see it in the paper ? Or how would I construct the basic PR functions "projection" from what has been drawn by Gödel ?

My main question was : how to construct the 'not', 'or', 'equal' using PR. One can find them easily on the internet, but they use this "projection" function.

At the very moment i am editing this question, I am particularily interested in the 'equal' relation.

Thank you

$\endgroup$
3
$\begingroup$

You can define the projections using Gödel's representation of a list of numbers $k_1, \ldots, k_m$ as the single number $p_1^{k_1}\cdots p_m^{k_m}$ (where $p_i$ is the $i$-th prime). I don't think he gives a name to the function, $\lambda_m$ say, that maps the $m$-tuple $(k_1, \ldots, k_m)$ to $p_1^{k_1}\cdots p_k^{k_m}$, but $\lambda_m$ is primitive recursive and you don't need projection to define it. He does give a name to the primitive recursive function that, given $n$ with $1 \le n \le m$, extracts $k_n$ from $\lambda_m(k_1, \ldots, k_m)$ (it's called $\mathit{item}$ in this translation). Composing these things gives you the projection functions. So the projection functions are just a technical convenience.

Mauro Allegranza has shown you how to implement the equality test function: $$ \gamma(x, y) = \left\{ \begin{array}{ll} 0 & \mbox{if $x = y$}\\ 1 & \mbox{if $x \neq y$} \end{array} \right. $$ as a primitive recursive function. As for the negation and disjunction functions: $$ \begin{array}{rcl} \alpha(x) &=& \left\{ \begin{array}{ll} 1 & \mbox{if $x = 0$}\\ 0 & \mbox{if $x \neq 0$} \end{array} \right. \\ \beta(x, y) &=& \left\{ \begin{array}{ll} 0 & \mbox{if one or both of $x, y$ ${} = 0$}\\ 1 & \mbox{if both $x, y$ are ${} \neq 0$} \end{array} \right. \end{array} $$

the following primitive recursive definitions do the job:

$$ \begin{array}{rcl} \alpha(0) &=& 1 \\ \alpha(k + 1) &=& 0 \\ \beta(0, y) &=& 0 \\ \beta(k+1, y) &=& \alpha(\alpha(y)) \end{array} $$

$\endgroup$
  • $\begingroup$ thank you for your answer about the projection operator. I should have thought about it myself :) $\endgroup$ – joseph M'Bimbi-Bene Oct 22 '15 at 16:44
2
$\begingroup$

The theory of (primitive) recursive functions has been sketched by Gödel in his paper and subsequently "streamlined" by other authors.

For a detailed treatment, see :

For a "older" but complete treatment, see :

In brief :

$a=b$ iff $sg(|a — b|) = 0$;

$|a — b|$ is p.r. becuase $|a — b| = (a \div b)+(b \div a)$;

$(a \div b)$ is defined as : $(a \div 0)=a$ and $(a \div (b+1))=pd (a \div b)$, where : $pd(0)=0$ and $pd(y+1)=y$.

Finally : $sg(x)=0$ if $x=0$ and $sg(x)=1$ if $x \ne 0$ is p.r. because it is defined by :

$sg(0)=0$ and $sg(x+1)=1$.


In Gödel's original paper :

A number-theoretic function $\varphi$ is said to be recursive if there is a finite sequence of number-theoretic functions [...] that ends with $\varphi$ and has the property that every function of the sequence is recursively defined in terms of two of the preceding functions, or results from any of the preceding functions by substitution, or, finally, is a constant or the successor function $x + 1$.

In turn, we can define the constant functions inductively from the constant zero function : $Z(x)=0$ and the successor :

$C_0(x)=Z(x)$ and $C_{n+1}(x)=C_n(x)+1$.


Gödel refined his exposition in his 1934 Priceton lectures (see : Martin Davis (editor), The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions (1965 - Dover reprint), page 43) (the notes were taken by S.C.Kleene and J.B.Rosser); here the complete definition is stated :

We define the class of recursive functions to be the totality of functions which can be generated by substitution, according to the scheme (1), and recursion, according to the scheme (2), from the successor function $x+1$, constant functions $f(x_1, \ldots, x_n) = c$, and identity functions $U_j^n(x_1, \ldots, x_n) = x_j, (1 \le j \le n)$.


The usual recursive definition of sum is based on the equations :

$x+0=x$, i.e. $f(x,0)=U_1^1(x)$

$x+(y+1)=S(x+y)$, i.e. $f(x,y+1)=f(x,y)+1$.

$\endgroup$
  • 1
    $\begingroup$ I don't have the paper to hand just now, but surely your $C_x(x)$ can't be right (the subscript is supposed to be a constant, not a variable). However, the identity function is easily defined by recursion using the constant $0$ function in the base case and using $\mathbf{succ}$ in the recursive step. $\endgroup$ – Rob Arthan Oct 18 '15 at 15:41
  • $\begingroup$ thank you for your answer and you useful links. $\endgroup$ – joseph M'Bimbi-Bene Oct 22 '15 at 16:45

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.