# Questions tagged [primitive-recursion]

The tag has no usage guidance.

56 questions
Filter by
Sorted by
Tagged with
20 views

### How to show a function is primitive recursive by induction?

I know, loosely speaking, if we can define a function $f$ in term of \begin{align} &f(0,\vec{x})=g(\vec{x})\\ &f(n+1,\vec{x})=h(f(n),n,\vec{x}) \end{align} where functions $g,h$ are primitive ...
28 views

72 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 ...
34 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 ...
26 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, ...
53 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) ?
36 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 ...
112 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 ...
129 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 ...
387 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 ...
667 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 ...
51 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,...
70 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 ...
86 views

39 views

### Is there a broader class of total functions than $PR$? [duplicate]

In total functional programming programs are restricted to total computable functions. A well-known class of total functions are the primitive recursive functions ($PR$). However the Ackermann ...
259 views

### Are all functions with constant space complexity in $REG$?

The Wikipedia article about regular languages mentions that $DSPACE(O(1))$ is equal to $REG$. Can I conclude from this that every function in $R$ with constant space complexity is in $REG$?
49 views

### Primitive Recursion equipped with an evaluator function

The wikipedia article for primitive recursion mentions a limitation that primitive recursive function can't compute the function $ev(i,j)$ which computes the $i$th primitive recursive function on ...
551 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 ...
997 views

### How do I prove that all primitive recursive functions are computable?

I stumbled across an exam question, and I am not sure how to prove that that all primitive recursive functions are computable. Is there a formal definition of this?
1k 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) =\...
356 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 ...
451 views

### Decidability of dependent typing on primitive recursive languages

With a dependent type system in a normal functional language type checking may never halt. This is partially because dependent typing removes the isolation between types, and code. My question is this:...
106 views

### Recognizing primitive recursion

I am trying to write a program to recognize if a given lambda calculus expression is primitive recursive. I believe that a general algorithm to do this does not exist, but I am interested in the most ...
482 views

### primitive recursion in the lambda calculus

I am having trouble finding out what a primitive subset of the lambda calculus would look like. I reference primitive recursion as shown here: "https://en.wikipedia.org/wiki/...
153 views

### primitive recursion on untyped lambda calculus

Does a definition of primitive recursion exist for the untyped lambda calculus? Does the definition of primitive recursion require typing for natural numbers? The only definitions I can find are for ...
69 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?...
249 views

### How can the class of tail recursive functions be compared to the classes of PR and R?

How can the class of tail recursive functions (TR) be compared to the classes of primitive recursive functions (PR) and recursive functions (R)? The computation of a PR function always halts. This ...