Questions tagged [primitive-recursion]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
52 views

Any PRC class is closed under a construction involving a function f such that f(x+1) < x+1

So I'm trying to solve this problem(problem 8 from section 3.4) of the book Computability, Complexity and languages by Martin Davis: Let k be some fixed number, let ...
1
vote
1answer
44 views

How to prove that the set of recursive primitive functions is closed under

the scheme of iteration ? Here is the scheme of iteration : for $g : \mathbb{N}^p\to \mathbb{N}$ and $h:\mathbb{N}^{p+1}\to \mathbb{N}$ two primitive recursive functions we associate $f: \mathbb{N}^{p+...
1
vote
0answers
53 views

Why is this function primitive recursive?

Let $f:\mathbb{N}^{p+1} \to \mathbb{N}$ a primitive recursive function and $g:\mathbb{N}^{p+1} \to \mathbb{N}$ the bounded sum defined by : $g(\bar{a},x)=\sum\limits_{i=0}^x f(\bar a , i)$. To show ...
0
votes
1answer
45 views

How does primitive recursion handle mutual recursion?

My intuition is that you can't call a function that has not yet been defined, although I have yet to find a source confirming this. Is this true? Thanks, friends :)
14
votes
0answers
146 views

What can be proven regarding the differences in power between unary ECMAScript regex functions and primitive recursive functions?

In 2014, inspired by Regex Golf, I started exploring, along with a mathematician going by the name teukon, what could be done in the unary domain in ECMAScript regex that went significantly beyond ...
0
votes
0answers
33 views

For what reason this function is recursive primitive?

Let $\forall n \in \mathbb{N}\ \ P(n)$ a primitive recursive predicate such that $\neg P(n)$ for a finite number of values of $n$. Why this function: $$ f(x) = \begin{cases} 1 & \text{ if there ...
3
votes
1answer
72 views

Characterization of computationally universal functions

Is it correct to state that $u$ is a universal function if and only if $$ \forall f : \text{RE} \quad \exists g : \text{R} \quad \exists h : \text{R} \quad f = h \circ u \circ g $$ where RE is the set ...
1
vote
1answer
36 views

Relative primality is primitive recursive

How do I prove that the predicate $P(x , y)$ is primitive recursive, where $P(x,y)$ holds if $x,y$ are relatively prime?
1
vote
1answer
41 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
23 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
290 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)...
1
vote
1answer
450 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
59 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
150 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
106 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 ...
1
vote
1answer
30 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
76 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
45 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
222 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
177 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
618 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
1k 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
54 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
86 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
104 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
342 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
281 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
102 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 ...
5
votes
1answer
482 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
123 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
119 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
678 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
77 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
195 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
288 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{...
3
votes
1answer
451 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
64 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
127 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
47 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
450 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
57 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
763 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
1k 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
439 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
543 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
117 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
609 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
184 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 ...