Questions tagged [primitive-recursion]

The tag has no usage guidance.

10 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
50 views

The evolution of the term “recursive” from Goedel to Church to present day

I'm currently studying some of the history of computation / computability, in the early days known as recursion theory. I see Goedel's definition of recursive functions seems significant in his paper,...
4
votes
0answers
62 views

Is there a name for the class of functions whose totality can be proved using “Ackermann-like” reasoning?

Primitive recursion is recursion where totality can be proved because there is a single natural number parameter that strictly decreases in every recursive call. Put another way, the recursion ...
3
votes
0answers
68 views

Prove that variable projection is recursive

Let $\varphi:\mathbb{N}\to\mathbb{N}^*$ be an arbitrary recursive enumeration of finite strings and $\mathcal{I}^n_i(x_1,...,x_n) = x_i $ be the $i$-th projection over $n$ variables. I would like to ...
2
votes
0answers
26 views

Showing that the quotient function is primitive recursive

I'm asked to show that the quotient function is primitive recursive. I know that the operation of integer division $div$ is not total, as it is not defined when the denominator is zero, and a ...
2
votes
0answers
68 views

What is the precise mathematical definition of n-iterated recusion?

Primitive recursion can be extended to double-recursion as in the following link: http://www.andrew.cmu.edu/user/kk3n/recursionclass/1primrec.html How can this be generalized to n-iterated recursion?...
2
votes
1answer
960 views

Primitive Recursive Function for Division and Hailstone function

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) =\...
1
vote
0answers
34 views

Determining whether Turing machine halts on input: primitive recursive?

In Elements of the Theory of Computation by Lewis and Papadimitriou, the authors use a specific function for proving that application of unbounded minimization on a primitive recursive function need ...
0
votes
0answers
24 views

Why is zero basic primitive recursive function?

Given operation Primitive recursion, we can do pred(x)=x-1 as f(0,x) = x f(i+1,x) = i pred(x) = f(x,x) and zero as ...
0
votes
0answers
24 views

If a unary relation is partially recursive, then so is its running total

I am studying Recursive Functions and I found online course notes of Stephen Cook. In the notes, I found this very interesting exercise: Exercise 8   For each unary relation $R(x)$ define the ...
-1
votes
1answer
120 views

How to show that certain summations are primitive recursive?

If we have a function $g\colon \mathbb{N}^{k+1} \to \mathbb{N}$ which is primitive-recursive. How to show that the function $f\colon \mathbb{N}^{k+1} \to \mathbb{N}$ with $$f(x_1, \dots, x_k , x_{k+...