Questions tagged [primitive-recursion]
The primitive-recursion tag has no usage guidance.
63
questions
1
vote
1
answer
49
views
Are there situations where we can decrease the time complexity of a program by increasing its ordinal complexity?
Are there (interesting) situations where we can decrease the time complexity of a program by increasing its ordinal complexity?
For example, is it possible to find a primitive recursive function such ...
- 177
0
votes
1
answer
53
views
How to show that the following function $F$ is primitive recursive?
We want to show that the following function $F$ is primitive recursive (using the primitive recursion scheme) :
For all $x,p,a\in \mathbb N$,
$F(p,a,0)=g(\eta^{p}(a))$
$F(p,a,x+1)=h(\eta^{(p-(x+1))}(...
- 199
0
votes
0
answers
51
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 ...
1
vote
1
answer
60
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 ...
- 113
1
vote
1
answer
74
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+...
- 199
1
vote
0
answers
66
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 ...
- 199
0
votes
1
answer
71
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 :)
- 23
14
votes
0
answers
219
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 ...
- 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 ...
- 13
3
votes
1
answer
92
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 ...
- 416
1
vote
1
answer
43
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
1
answer
92
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 ...
- 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 $...
- 156
3
votes
2
answers
312
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:
...
- 200
1
vote
1
answer
38
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)...
- 11
1
vote
1
answer
793
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 ...
- 13
0
votes
0
answers
69
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
1
answer
214
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
0
answers
140
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 ...
- 181
1
vote
1
answer
55
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, ...
- 29.6k
2
votes
1
answer
122
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) ?
- 51
1
vote
0
answers
66
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 ...
- 11
2
votes
2
answers
343
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
2
answers
231
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 ...
- 180
0
votes
1
answer
1k
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 ...
- 151
1
vote
2
answers
2k
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 ...
- 45
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,...
- 317
4
votes
0
answers
93
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 ...
- 3,453
0
votes
1
answer
109
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}
\...
- 478
1
vote
1
answer
404
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 ...
- 25
3
votes
1
answer
381
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 ...
- 1,062
3
votes
1
answer
110
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 ...
- 475
5
votes
1
answer
625
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 ...
- 1,048
2
votes
1
answer
143
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 ...
- 5,362
1
vote
1
answer
134
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?
- 83
3
votes
1
answer
784
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, ...
- 35
3
votes
0
answers
82
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 ...
- 369
3
votes
1
answer
208
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 (...
- 131
3
votes
1
answer
310
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{...
- 295
3
votes
1
answer
531
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=\{...
- 199
4
votes
1
answer
66
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 ...
- 309
-1
votes
1
answer
132
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+...
- 175
0
votes
0
answers
48
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 ...
- 361
0
votes
1
answer
532
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$?
- 361
7
votes
1
answer
85
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 ...
- 235
5
votes
4
answers
877
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 ...
- 1,188
2
votes
2
answers
2k
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?
- 21
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) =\...
- 141
7
votes
2
answers
513
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 ...
- 459
5
votes
2
answers
626
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:...
- 459