Checking whether signum and the remainder function is primitive recursive

computabilityintuition

I am reading Computability theory from S. Barry Cooper's book. The author asks to check if signum is a primitive recursive function. Here's my response:

Define $f(m,0)=0$ and $f(m,n+1)=U_1 ^3 (m,n, f(m,n))=m$ for each $m, n\in \mathbb N$. By primitive recursion, $f$ is primitive recursive. Then define $\text {sg} (n) = f(1,n)$. Bu substitution, $\text {sg}$ is primitive recursive. Is this correct?

Next Cooper shows as an example that the remainder function defined by
$$rm(m,n) = \begin{cases} \text{the remainder upon division of } n \text{ by } m, & m\ne 0 \\
n & \text{otherwise}\
\end{cases}$$
is primitive recursive by writing the following scheme
$$\begin{align*}
rm(m,0) &= 0 , \\
rm(m, n+1) &=(rm(m,n)+1)\times \text{sg} (|n-rm(m,n)-1|)
\end{align*}$$

It seems wrong to me however. I tried writing a computer program and it did not return to me the correct values:

int rm(int m, int n) {
        if(n==0) return 0;
        else {
            int k=rm(m,n-1);
            return (k+1)*(int)(Math.signum(Math.abs((n-1)-(k+1))));
        }
    }

It just returns me $n-1$. Have I did something wrong or is Cooper's scheme incorrect? If it is okay, what is the intuition behind this scheme?

Best Answer

There must be a typo in the source you're copying the definition from -- you can see something must be fishy because it never uses the $m$ argument for anything (other than passing to the recursive call where, recursively, nothing keeps happening to it). It should really be: $$\begin{align*} \mathrm{rm}(m,0) &= 0 , \\ \mathrm{rm}(m, n+1) &=(\mathrm{rm}(m,n)+1)\times \mathrm{sg} (|m-\mathrm{rm}(m,n)-1|) \end{align*}$$

The underlying trick here is that $$ \mathrm{sg}(|a-b|) = \begin{cases} 0 & \text{if }a=b \\ 1 & \text{otherwise} \end{cases} $$ and you want the right factor of the multiplication to become $0$ and so reset the remainder to $0$ when the output from the recursive call equals $m-1$. In all other cases the factor is $1$ and lets the $\mathrm{rm}(m,n)+1$ result survive.

Related Question