# Questions tagged [primitive-recursion]

The tag has no usage guidance.

47 questions
Filter by
Sorted by
Tagged with
506 views

### Showing that the number of primitive-recursion programs for each function is countably-infinite

Problem Statement Prove that if a function $f$ is primitive recursive, then there are countably infinite number of primitive recursive definitions of $f$ Yes, this is a homework question. My ...
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 ...
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 ...
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 ...
21 views

### What is known about the sets enumerated by primitive recursive functions?

Let's say that a set of natural numbers $S \subseteq \mathbb{N}$ is primitive recursively enumerable if there exists some primitive recursive function $f$ such that $S$ is the range of $f$. That is, ...
42 views

### Computability: Proving a predicate is not recursively enumerable

Let P(p) <=> for each x, comp(p,x) is defined. Can anyone explain to me how to prove that P is not RE (recursively enumerable) ?
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 ...
77 views

### Quotient in LOOP program [closed]

I want to construct a LOOP-computable program for the integer division (quotient): x = a DIV b The LOOP specification can be seen here: https://en.wikipedia.org/wiki/LOOP_(programming_language) I ...
85 views

### Primitive recursive plus Ackermann

Let us consider the class $\cal F$ of functions that contains all constant functions all projections the successor function the Ackermann function as basic functions, and that is closed under ...
244 views

### What is the definition of computable partial function?

Let $f:\mathbb{N} \to \mathbb{N}$ be a computable partial functions and $T$ a Turing Machine which computes it. By this I understand that $T$ writes $f(n)$ on its tape and halts when $n$ is an input ...
516 views

### How to prove that if the set and its complement are recursively enumerable, then both are recursive?

How to prove that if the set and its complement are recursively enumerable, then this set and its complement are recursive? My idea is that we can make the characteristic function of recursively ...
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,...
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 ...
3k views

### Time complexity of Ackermann's Function

How would one go about classifying the time complexity of Ackermann's function, and can we say that all primitive-recursive functions are asymptotically bounded by the complexity of the Ackermann ...
138 views

231 views

### Showing the predicate $n \leq \sqrt2 < n+1$ is primitive recursive

Let h(x) be the integer n such that $n \leq \sqrt2 < n+1$ Show that h(x) is primitive recursive. I know how primitive recursive functions are defined, but showing an integer is primitive recursive ...
185 views

### what are Structural recursion, primitive recursion, recursion combinator and recursion principles?

Recently, I encountered terminologies such as primitive recursion and recursion combinator. One of the sources is here link I googled and read some, but missing the points of them. I know that ...
263 views

### How can primitive recursion in two variables be made to be of only one variable?

Problem 7.16 in The Nature of Computation reads as follows: [...] show that when defining primitive recursive functions, we really only need to think about functions of a single variable. In ...
88 views

### Total functional computable real numbers

Is there any computable real number which can not be computed by a higher order primitive recursive algorithm? For computable real number I mean those that can be computed by a Turing machine to any ...
304 views

### primitive recursive functional equivalence

Given two primitive recursive functions is it decidable whether or not they are the same function? For example lets take sorting algorithms A, and B which are primitive recursive. While there are many ...
960 views

### If $g ∘ f$ is primitive recursive, are $f$ and $g$, too?
Assuming I have functions $f, g : \mathbb{N} \to \mathbb{N}$ and I know that $g \circ f$ is a primitive recursive function. What can I tell about $f$ and $g$? Are they primitive recursive as well? Or ...