How do I make a primitive recursive function that does division?

Question

I am trying to define a primitive recursive function that does division. I looked at this answer but it seems wrong to me, because according to Wikipedia:

The primitive recursive functions are among the number-theoretic functions, which are functions from the natural numbers (nonnegative integers) {0, 1, 2, ...} to the natural numbers

So the inequality x−t⋅y≥0 will always be true and the function will always keep adding +1. The function given in the answers seems right but only assuming that I have negative numbers. Now how could I build a PRF with just natural numbers?

EDIT: I found a way to either make a division that always rounds up or always rounds down. But I haven't found one yet that always does the correct thing. So far:

Div(x,y,0) = 0
Div(x,y,S(m) = A(Div(x,y,m),V(D(x,M(y,S(m)))))

where S(m) is successor, A is addition, V is 0 if 0 and 1 otherwise, D is subtraction and M is multiplication.

Now the above always rounds down and the next one always rounds up:

Div(x,y,0) = 0
Div(x,y,S(m) = A(Div(x,y,m),V(D(x,M(y,m))))

Answer 1

Definition by cases is a valid, derived principle of definition for primitive recursive functions. So is subtraction, and so is equality. I will therefore use them freely.

Moreover, it is a good idea to define not just integer division $d(m,n)$ but also the remainder function $r(m,n)$. One can then write

\begin{align} r(0,n) & = 0 \\ r(m+1,n) & = \begin{cases} 0 & \text{if}\; n-1 = r(m,n) \\ r(m,n) + 1 &\text{otherwise} \end{cases} \end{align}

and define integer division by

\begin{align*} d(0,n) & = 0 \\ d(m+1,n) & = \begin{cases} d(m,n) + 1 & \text{if}\; r(m,n) = n-1 \\ d(m,n) & \text{otherwise} \end{cases} \end{align*}

Answer 2

I know I'm late to the party, but here goes formulation given by N. Cutland in Computability: An Introduction to Recursive Function Theory (p. 36):

First, let's define

$$ sg(x) = \begin{cases} 0 &\mbox{if } x = 0,\\ 1 &\mbox{if } x \neq 0. \end{cases} $$

By recursion we have $sg(0) = 0$ and $sg(x + 1) = 1$, hence $sg$ is computable. Analogically, we define $\overline{sg}$ which returns $1$ if $x = 0$ and 0 otherwise. Next, let's define reminder when $y$ is divided by $x$ (to obtain a total function we adopt the convention $rm(0, y) = y)$}. We have:

$$ rm(x, y + 1) = \begin{cases} rm(x, y) + 1 &\mbox{if } rm(x, y) + 1 \neq x \\ 0 & \mbox{if } rm(x, y) + 1 = x \end{cases} $$

This gives the following definition by recursion:

$$ rm(x, 0) = 0,\\ rm(x, y + 1) = (rm(x, y) + 1) \times sg(|x - (rm(x, y) + 1)|). $$

The second equation can be written as $rm(x, y + 1) = g(x, rm(x, y))$ where $g(x, z) = (z + 1) \times sg(|x - (z + 1)|)$; and $g$ is computable by several applications of substitution. Hence, $rm(x, y)$ is computable. Then, we can define quotient when $y$ is divided by $x$ (to obtain a total function we define $qt(0, y) = 0$):

$$ qt(x, y + 1) = \begin{cases} qt(x, y) + 1 &\mbox{if } rm(x, y) + 1 = x,\\ qt(x, y) &\mbox{if } rm(x, y) +1 \neq x. \end{cases} $$

By recursion, we have:

$$ qt(x, 0) = 0,\\ qt(x, y + 1) = qt(x, y) + \overline{sg}(|x - (rm(x, y) + 1)|). $$

Hence, $qt$ is computable.

Answer 3

If y has to divide x such that x>y, then, initially assuming i=0;

x/y=f(x,y,0);

f(x,y,i)=f(x-y,y,i+1)

quotient =i and remainder =x-y (finally, such that when y>(x-y)) ,

the recursive step has to be stopped.

Example 1:

25/4=f(25,4,0)

=f(21,4,1)

=f(17,4,2)

=f(13,4,3)

=f(9,4,4)

=f(5,4,5)

=f(1,4,6)

Hence quotient=i=6 and reaminder=x-y=1.

i.e, 25=6*4+1!

Example 2:

30/8=f(30,8,0)

=f(22,8,1)

=f(14,8,2)

=f(6,8,3)

Since 6<8, we stop here.

Therefore 30=3*8+6!!

Answer 4

I found a solution to my problem. The main issue was to figure out if $a - b \geq 0.$ One has to use a little trick to figure this out. Below is the function I used for it and the final primitive recursive function that does division.

$a-b \geq 0$

$BOE(a,0) = 1$

$BOE(a,S(m)) = A(V(D(a,S(m))),E(a,S(m)))$

with $A$ being Addition, $V(0) = 0$ else $1$, $D$ being subtraction, $E$ being equals, $S$ being successor and $M$ being multiplication.

$$ Div(x,y,0) = 0$$

$$Div(x,y,S(m)) = A(A(Div(x,y,m),V(D(x,M(y,S(m))))),E(D(x,M(m,y)),D(M(m,y),x)))$$