Questions tagged [primitive-recursion]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
19 views

Prove a Predicate is Primitive Recursive

Suppose $x$ is Godel's number of some formula. Predicate $\operatorname{P}(\operatorname{f}(x))$ is true only when the number of functions is equal to the number of predicates in that formula. Prove ...
user avatar
1 vote
1 answer
58 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 ...
user avatar
  • 113
1 vote
1 answer
52 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+...
user avatar
  • 197
1 vote
0 answers
59 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 ...
user avatar
  • 197
0 votes
1 answer
53 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 :)
user avatar
  • 23
14 votes
0 answers
160 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 ...
user avatar
  • 241
0 votes
0 answers
36 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 ...
user avatar
3 votes
1 answer
81 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 ...
user avatar
  • 386
1 vote
1 answer
39 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?
user avatar
1 vote
1 answer
55 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 ...
user avatar
  • 113
0 votes
0 answers
25 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 $...
user avatar
2 votes
2 answers
297 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: ...
user avatar
  • 123
1 vote
1 answer
36 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)...
user avatar
1 vote
1 answer
571 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 ...
user avatar
0 votes
0 answers
60 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 ...
user avatar
1 vote
1 answer
172 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 &...
user avatar
2 votes
0 answers
115 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 ...
user avatar
  • 181
1 vote
1 answer
35 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, ...
user avatar
  • 29.1k
2 votes
1 answer
82 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) ?
user avatar
1 vote
0 answers
49 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 ...
user avatar
2 votes
2 answers
248 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 ...
user avatar
3 votes
2 answers
195 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 ...
user avatar
  • 180
0 votes
1 answer
740 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 ...
user avatar
  • 151
1 vote
2 answers
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 ...
user avatar
5 votes
0 answers
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,...
user avatar
4 votes
0 answers
87 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 ...
user avatar
0 votes
1 answer
105 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} \...
user avatar
  • 468
1 vote
1 answer
356 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 ...
user avatar
  • 25
2 votes
1 answer
292 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 ...
user avatar
  • 1,042
3 votes
1 answer
107 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 ...
user avatar
5 votes
1 answer
541 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 ...
user avatar
2 votes
1 answer
136 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 ...
user avatar
1 vote
1 answer
127 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?
user avatar
  • 83
3 votes
1 answer
715 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, ...
user avatar
3 votes
0 answers
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 ...
user avatar
  • 369
3 votes
1 answer
197 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 (...
user avatar
3 votes
1 answer
290 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{...
user avatar
3 votes
1 answer
470 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=\{...
user avatar
  • 197
4 votes
1 answer
65 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 ...
user avatar
  • 309
-1 votes
1 answer
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+...
user avatar
  • 175
0 votes
0 answers
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 ...
user avatar
  • 351
0 votes
1 answer
472 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$?
user avatar
  • 351
6 votes
1 answer
59 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 ...
user avatar
5 votes
4 answers
772 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 ...
user avatar
2 votes
2 answers
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?
user avatar
2 votes
1 answer
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) =\...
user avatar
  • 141
7 votes
2 answers
466 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 ...
user avatar
  • 459
5 votes
2 answers
571 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:...
user avatar
  • 459
1 vote
1 answer
119 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 ...
user avatar
  • 459
2 votes
1 answer
655 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/...
user avatar
  • 459