Questions tagged [primitive-recursion]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
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 ...
0
votes
0answers
28 views

Primitive Recursion

I have been given the following task: Which functions result from primitive recursion: $$ \text{1. } \mathit{h=zero}_2, \quad \mathit{g=succ}_0\mathit{zero}_0 \\ \text{2.}\quad \mathit{g=zero}_0, \...
0
votes
0answers
22 views

Which function results from primitive recursion of the functions g and h?

Which function results from primitive recursion of the functions $g$ and $h$? $f_1=PR(g,h)$ with $g=succ\circ zero_0, h=zero_2$ $f_2=PR(g,h)$ with $g=zero_0, h=f_1\circ P_1^{(2)}$ $f_3=PR(g,h)$ with $...
2
votes
2answers
283 views

What does the phrase “Simple For Loops” mean in computability theory?

I was reading a Wikipedia page on Primitive Recursive Functions but there is a phrase for describing the simple for loops which I really don't understand. Can anyone explain this to me? The Phrase: ...
1
vote
1answer
32 views

Proving a certain primitive recursive function exists

Assume $f\colon ω × ω → ω$ is a computable function. How can we prove that there is a primitive recursive function $g\colon ω × ω → ω$ where the following holds: $∀n [∃s(f(n, s) = 1) ↔ ∃k(g(n, k) = 1)...
0
votes
0answers
45 views

Primitive Recursion of two functions $g,h$

Which function is created when applying Primitive Recursion $PR(g,h)$ to $\begin{align}g:\mathbb{N}\to \mathbb{N}, \quad g(n)&=\mathrm{zero}_1(n)\\ h:\mathbb{N}^3\to\mathbb{N}, \quad h(n,m,l)&...
1
vote
1answer
153 views

Mod 2 is primitive recursive

Given a function E(x) which outputs 0 is x is even and 1 is x is odd, prove that this function is primitive recursive. My attempt is as follows $$ E(x) = x \mod 2$$ To show that any function is ...
0
votes
0answers
55 views

How to show that a partial function is recursive?

I try to prove that this function is recursive: $$f(x_1,x_2)= \begin{cases} 2x_1-x_2 & \text{if $x_1 \geqslant \sqrt{x_2}$} \newline \bot & \text{otherwise} \end{cases}$$ I think that I need ...
1
vote
1answer
90 views

How to show that a $\log_2(x)$ is a recursive function?

I have a problem for the comprehension of how to prove that a function $ \log_2 : \mathbb{N} \rightarrow \mathbb{N}$ defined as: $$\log_2 (x)= \begin{cases} y & \text{if $x=2^y$} \newline \bot &...
2
votes
0answers
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 ...
0
votes
0answers
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 ...
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
vote
1answer
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, ...
2
votes
1answer
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) ?
1
vote
0answers
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 ...
2
votes
2answers
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 ...
3
votes
2answers
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 ...
0
votes
1answer
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 ...
1
vote
2answers
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 ...
5
votes
0answers
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,...
4
votes
0answers
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 ...
0
votes
1answer
86 views

prove that $h(x)$ is partial recursive

If $f:A^*\rightarrow A*$ and $g:A^* \rightarrow A^*$ are partial recursive we want to prove $h:A^* \rightarrow A^*$ with the following definition is partial recursive $$ h(x) = \begin{cases} \...
1
vote
1answer
264 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 ...
2
votes
1answer
211 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 ...
3
votes
1answer
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 ...
4
votes
1answer
306 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 ...
2
votes
1answer
79 views

How to extent primitive recursion from natural numbers to finite strings?

Primitive recursion seems to be related to bounded quantification. It is easier to make sense of bounded quantification with respect to natural numbers than to make sense of bounded quantification ...
1
vote
1answer
113 views

Complete $\mu$-recursive function that is not primitive recursive

Could you find an example of a complete $\mu$-recursive function that is not a primitive function?
3
votes
1answer
564 views

Show a predicate is primitive recursive

Let $S(i,x_1,\ldots, x_n)$ be a primitive recursive predicate. \begin{equation} f(i_1,i_2,x_1,\ldots, x_n) = \begin{cases} 1 &\text{ when for all i, }\; i_1 \le i \le i_2,\; S(i,x_1, \ldots, ...
3
votes
0answers
69 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 ...
3
votes
1answer
185 views

Non-primitive recursiveness in real world nonmathematical software?

Is there a real world nonmathematical example of computer software that isn't primitive recursive? I'm not interested in examples that are somehow closely related to theory of computation or logic (...
3
votes
1answer
273 views

What does the exact $\mu$-recursive program for minimization look like?

The minimization of a given primitive recursive function $f$ is computed by the following expression: $ \newcommand{\pr}[2]{\text{pr}^{#1}_{#2}} \newcommand{\gpr}{\text{Pr}} \newcommand{\sig}{\text{...
2
votes
1answer
337 views

Is Euler's totient function a primitive recursive function?

We consider the function $g$ which associates the number of prime integers with $n$ in the set $\{0,...,n\}$. I have to prove that $g$ is a primitive recursive function. First I defined the set $A=\{...
4
votes
1answer
58 views

How to handle an undefined case with µ-recursive functions?

How to construct my proof and generally what should I aim to get when showing a function is $\mu$-recursive? Should I transform it in some of the basic functions using the given operators? For ...
-1
votes
1answer
123 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+...
0
votes
0answers
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 ...
0
votes
1answer
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$?
6
votes
1answer
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 ...
5
votes
4answers
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 ...
2
votes
2answers
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?
2
votes
1answer
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) =\...
7
votes
2answers
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 ...
5
votes
2answers
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:...
1
vote
1answer
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 ...
2
votes
1answer
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/...
2
votes
1answer
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 ...
2
votes
0answers
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?...
6
votes
1answer
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 ...
5
votes
1answer
351 views

Implementing primitive recursive functions in a programming language

I started studying Design Concepts in Programming Languages by Turbak, Gifford and Sheldon. In the first chapter, they define a language called POSTFIX, similar to a postfix calculator's input ...
3
votes
2answers
4k 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 ...