Questions tagged [primitive-recursion]
The primitive-recursion tag has no summary.
66 questions
3
votes
1
answer
150
views
Are Primitive recursive functions (with bounded $\mu$ operator) equivalent to other known computational model?
There is a famous equivalence between types of grammars and automatons. However when discussing recursive functions, we only consider equivalence of General Recursive functions with Turing machines. ...
- 394
3
votes
1
answer
189
views
Useful algorithm not primitive recursive
The Ackermann function is the textbook example of a function which is total recursive but not primitive recursive.
If we want to implement it in some programming language we will need to use a priori ...
- 253
0
votes
1
answer
123
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
1
vote
1
answer
101
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
0
answers
91
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
14
votes
0
answers
307
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
3
votes
1
answer
172
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 ...
- 446
1
vote
1
answer
203
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
3
votes
2
answers
376
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
1k
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
1
vote
1
answer
299
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
1
answer
133
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, ...
- 30.4k
1
vote
0
answers
81
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
3
votes
2
answers
316
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
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
4
votes
0
answers
124
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,583
1
vote
1
answer
496
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
169
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 ...
- 485
2
votes
1
answer
187
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,450
3
votes
1
answer
879
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
1
answer
280
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
625
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
-1
votes
1
answer
195
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
1
answer
667
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
5
votes
4
answers
1k
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 Work
...
- 1,208