2
$\begingroup$

Are division and Hailstone primitive recursion function?

$$\text{Div}(x,y) = \begin{cases} x/y, & \text{if $y$ divides $x$ } \\ 0, & \text{otherwise} \end{cases}$$

$$\text{Hailstone}(n) =\begin{cases} 3n + 1, & \text{if $n$ is odd } \\ n/2, & \text{if $n$ is even} \end{cases}$$

I tried to solve division in this way $$\text{Div}(0,y) = 0 $$ $$\text{Div}(x+y,y) = \text{Div}(x,y) + 1$$

I do not know how to proceed from here. Can anyone help me?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ This is essentially a programming question, if in a slightly atypical programming language. Community votes, please: is this ontopic? $\endgroup$ – Raphael♦ Mar 16 '16 at 10:27
  • $\begingroup$ Hint: you need to express all parts using primitive recursion. I see operations addition, multiplication and (integer) division, and predicates "divides", "is odd" and "is even", as well as (finite) case distinction. Some of these are probably known to be primitive recursive from lecture or prior exercise problems. Which are missing? $\endgroup$ – Raphael♦ Mar 16 '16 at 10:29
  • $\begingroup$ Regarding your attempt: that does not match the pattern for primitive recursion, at all. "$x+y$" is not something you get to do on the left-hand side. $\endgroup$ – Raphael♦ Mar 16 '16 at 10:29
  • $\begingroup$ For Div, it could also help to know that the bounded $\mu$ operator is primitive recursive. $\endgroup$ – Klaus Draeger Mar 16 '16 at 11:36
  • $\begingroup$ @Raphael, I proved isodd,iseven,add,limited subtraction,divides,multiplication,modulo to be primitive recursive function. I know it should be Div(x+1,y) = F(Div(x,y)). I am not able to find that function(s).I thought maybe I could use Div(x+y,y) to get something. $\endgroup$ – Perseus14 Mar 16 '16 at 11:38
-2
$\begingroup$

For your division example, what would the case be if y was equal to zero?

The function is undefined if y = 0. Thus, it is not a total function. Thus, division is not primitively recursive, as all primitively recursive functions are total functions.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ You are confusing Hailstone function and Collatz conjecture. It calculates one step only, no iteration. $\endgroup$ – gnasher729 Mar 3 '17 at 23:53
  • 1
    $\begingroup$ Regarding the first two paragraphs of this answer: The function $\text{Div}(x,y)$ is defined if $y=0$ and $x>0$. We say $y$ divides $x$ iff there exists an integer $z$ such that $yz=x$. Thus, $0$ divides $x$ iff $x=0$. Therefore, when $x>0$, we have $\text{Div}(x,0)=0$. The only ambiguous case is $\text{Div}(0,0)$. I'd guess that the original poster means that $\text{Div}(0,0) = 0$. But if there is some doubt in your mind about that, I think it'd be more useful to post a comment requesting clarification, or suggest an edit to the question that defines $\text{Div}$ more carefully. $\endgroup$ – D.W.♦ Mar 4 '17 at 1:14
  • $\begingroup$ The question was "Are division and Hailstone primitive recursion function(s)?", not "is function X primitively recursive?" The division function is not primitively recursive, period. I don't have to ask him to define for me what division is. A function X I would have to ask - but then that function would not be division. $\endgroup$ – Dennis Sheil Mar 6 '17 at 0:32

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.