Questions tagged [primitive-recursion]
The primitive-recursion tag has no summary.
66 questions
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
7
votes
1
answer
133
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
2
answers
760
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:...
- 469
5
votes
1
answer
770
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,058
5
votes
0
answers
74
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
1
answer
102
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
3
votes
2
answers
7k
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 ...
3
votes
1
answer
376
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
2
answers
603
views
Primitive recursive functions and unbounded quantifiers
From what I know If the predicate $P(t,x_1,...,x_n)$ belongs to some PRC class $\zeta$ then so do the predicates
$(\forall t)_{\le y}$ $P(t,x_1,...,x_n)$
$(\exists t)_{\le y}$ $...
- 1,561
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
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
3
votes
2
answers
285
views
Undefined behaviour when composing primitive-recursive with $\mu$-recursive functions?
It is quite easy to show that the following two functions are primitive recursive and thus also $\mu$-recursive:
$$ifthen(n,a,b) = \begin{cases}a & n > 0 \\ b & else\end{cases} $$
$$ eq(x,...
- 151
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
3
votes
0
answers
138
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 ...
- 379
2
votes
2
answers
200
views
can we computably list every primitive recursive function?
i have seen some articles where they use the diagonalization argument to prove the existence of non-primitive recursive functions. But this should only work if we can create an infinite list of every ...
- 141
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
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
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
2
votes
1
answer
193
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
2
votes
0
answers
100
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?...
- 85
1
vote
1
answer
167
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?
- 93
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
1
vote
1
answer
161
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
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
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