10

Every computable function can be expressed in continuation-passing-style, in which all calls are tail-calls. The trick is to add a "continuation" parameter to every function. Instead of making a non-tail-call to a function, you make a tail call to that function with a modified continuation, describing what to do with the result. All instances where a value ...


8

Let $f$ be a bijective function, which is not primitive recursive. We know, that such a function exists. Let further be $g=f^{-1}$ the inverse function of $f$. Therefore $f\circ g$ is the identity function, which is clearly primitive recursive.


7

I think you're confused about definitions. What you represented above is bounded minimization where we look for the least number $z$ below a given bound $k$ such that $f(n,z) = 0$. Such bounded minimization can be defined without any extra gadgets, using only primitive recursion. The so-called $\mu$ operation performs unbounded search. It is not something ...


7

You are asking (or at least typing) multiple questions that are unrelated. Time Complexity of the Ackermann function First, understand that this is not a meaningful query. The Ackermann function, let's call it $A$ (assume a one-parameter variant), is a function, not an algorithm. You can certainly talk about $\Theta(A)$. What you likely mean is the time $...


6

The idea is to use some appropriate coding. A primitive recursive encoding of pairs is an encoding $\mathbb{N}^2 \to \mathbb{N}$, denoted by $\langle x,y \rangle$, such that the following functions are recursive: $e(x,y) = \langle x,y \rangle$, $p_1(\langle x,y \rangle) = x$, $p_2(\langle x,y \rangle) = y$. Coming up with a primitive recursive encoding of ...


6

It is well known that equivalence is undecidable even for CFGs resp. PDAs (see even Wikipedia). This provides a proof that the same property is undecidable for every model of any superset of CFL (by a simple special case reduction). Since solving the word problem for any given CFL is clearly primitive recursive (by virtue of your favorite parsing algorithm),...


6

A computable function is primitive recursive if and only if it can be computed by a program whose running time is upper-bounded by some primitive recursive function. Your function (usually known as Euler's totient function $\varphi$) can be computed in exponential time, and so is primitive recursive.


5

There are two standard approaches: diagonalization and rate of growth. The definition of primitive recursive functions (whichever one you use) allows enumerating them $f_1,f_2,\ldots$. Since each primitive recursive function is total, the function $f(n) = f_n(n)+1$ is recursive. It is clearly not primitive recursive. The other approach is exemplified by ...


5

A regular automaton can do anything a Turing machine can do, as long as the TM uses only O(1) memory. This is because with finite memory, the number of possible states the TM can be in is also finite (It's the number of possible tape contents * the number of possible head positions * the number of states of your TM). You can encode the whole computation ...


5

You can prove by induction that the number of instructions executed by any given program is bounded (essentially since no command can create instructions). In particular, the number of arithmetic instructions executed by a program is bounded. This means that the output of a univariate function is polynomially bounded. Since the factorial function is not ...


5

You read the theorem wrong; the right-hand side contains this $L(\min \dots)$ -- this is not primitive recursive! Note that, in particular, such $z$ does not necessarily exist (the "algorithm" will loop.) $L(\min \_)$ in that theorem is also called the $\mu$-operator. It can not be expressed with primitive recursion. This theorem states that one ...


5

No it not true. Primitive recursive functions are a subset of computable functions. The minimization operator from $\mu$-calculus is not primitive recursive and not guaranteed to terminate. The constantly false function for instance would cause minimization to loop infinitely. As you likely know primitive recursion is guaranteed to terminate. What does seem ...


5

A very nice question! You just ventured into a large body of knowledge and research in computational theory around the concept of relative primitive recursiveness and hierarchy of total recursive functions such as fast growing hierarchy, which are full of interesting and mind-boggling facts. What function class $\cal F$ do we get by adding the Ackermann ...


5

The Wikipedia statement is informal and quite ambiguous. For example, let $A(n,n)$ be the Ackermann function, and consider the following program, where $n$ is the input: x ← 0 for i from 1 to A(n,n): x ← x + 1 return x This function is not primitive recursive, although there is a bound on the number of iterations which is known ahead of time. A better ...


4

If $P(t,x_1,\dots,x_n) \in \zeta$, then clearly $(\forall t)_{\le 0}P(t,x_1,\dots,x_n) = P(0,x_1,\dots,x_n) \in \zeta$. Moreover, if for some $y$, we have $(\forall t)_{\le y}P(t,x_1,\dots,x_n) \in \zeta$, then it can easily be shown that $(\forall t)_{\le y+1}P(t,x_1,\dots,x_n) = P(y+1,x_1,\dots,x_n) \land (\forall t)_{\le y}P(t,x_1,\dots,x_n) \in \zeta$, ...


4

It is not decidable, by the relatively straightforward informal proof: Given an arbitrary Turing machine $M$, you can define the following function $f_M$: $$ f_M(n) = \cases{0 \mbox{ if $M$ does not halt in $\leq n$ steps on empty input}\\ 1\mbox{ otherwise}}$$ It's a fundamental fact of primitive recursion that $f_M$ is, in fact, primitive recursive (it "...


4

Primitive recursive isn't actually an interesting threshold here. As long as the language only allows terminating programs, and type equality is defined by normal form equality, dependent typing can be checked statically. The gist of the proof is obvious: if the language only allows terminating programs, then all computations on types terminate, because ...


4

Not only is the answer to this question yes, but this is exactly the strategy that modern implementations like Coq and Agda take! To be precise, the type checker has to preform evaluation when deciding definitional equality so it would, if given the right language, be possible to write an infinite loop and ask whether a term was definitionally equal to ...


4

Famously, the fixed-point operator $Y$ of the untyped $\lambda$-calculus, which has the property that $$ Y\ F=_{\beta}F\ (Y\ F)$$ for every term $F$, is enough to implement primitive (and indeed, non-primitive!) recursion. Given any encoding of the natural numbers which allows decrementing, if you have an expression $$ e(n)=C[e(n-1)]$$ where $C$ is some ...


4

The set of higher-order primitive recursive reals is essentially the class of functions $\mathbb{N}\rightarrow\mathbb{N}$ which can be represented by a term $\mathrm{Nat}\rightarrow\mathrm{Nat}$ in Gödel's system T. Since every such function is total, and every well-typed term in the system can be enumerated effectively, there is a relatively easy proof by ...


4

Once you have proved that $|x-2^y|=0$ is a decidable predicate, the function $$\log_2(x) \equiv \mu y(|x-2^y| = 0)$$ should match the description of the function given and proves that it is recursive. Edit: To show that $|x-2^y|=0$ is decidable, show that $\overline{\text{sg}}(|x-2^y|)$ is recursive, which requires you to show that $|x-z|$, $2^y$, and $1 - \...


3

You prove it by structural induction over the definition of primitive recursive functions. The definition of computable is: a function is computable if it is computable by a Turing machine. There are many other equivalent definitions.


3

Agree with David that 3 is primitive recursive, but depending on what is meant exactly, the predicate in 4 is also primitive recursive - as a predicate, $\exists x(P(x) \wedge Q(x))$ has zero arguments and therefore is simply a truth value - and thus trivially primitive-recursive. On the other hand, if you took primitive-recursive predicates $P(x,y), Q(x,y)$ ...


3

The recursion combinator you mention seems to be the recursor associated to an inductive (or recursive) data type. In the paper this seems to be the type describing the syntax of lambda terms. Here, I'll take lists as a simpler recursive type. Note that the "lists of naturals type" can be intuitively described as the "least" type admitting these ...


3

This relation can be written as $$n \leq \sqrt{2} \text{ and } n+1 > \sqrt{2}$$ or equivalently $$ ((n^2 < 2) \text{ or } (n^2 = 2)) \text{ and } ((n+1)^2 > 2)$$ In terms of functions $$h(n) = and[or[ls(sqr(n),2), eq(sqr(n),2)], gr(sqr(n+1),2)]$$ So, we have exponentiation (squaring), increment by $1$ (i.e. $n+1$), less than, equal to, greater ...


3

A Turing machine $\Phi$ computes a partial function $f:$ $\subseteq\mathbb{N}\rightarrow\mathbb{N}$ iff: For each $n\in dom(f)$, $\Phi(n)$ halts and equals $f(n)$. For each $n\not\in dom(f)$, $\Phi(n)$ diverges (that is, never halts). What about when we feed $\Phi$ a "nonsense" input - that is, some string not corresponding to a natural number? Well, we ...


3

In "Extensions of some theorems of Gödel and Church" it's shown by Barkley Rosser that these sets are exactly the recursive sets: Corollary I. If a class can be enumerated (allowing repetitions) by a general recursive function, it can be enumerated (allowing repetitions) by a primitive recursive function. Note that the crux here is repetitions. Since you ...


2

The classical example of a computable function which is not primitive recursive is the Ackermann function. You can also construct such a function using diagonalization: given some effective enumeration $f_n$ of the primitive recursive functions, the function $n \mapsto f_n(n) + 1$ is computable but not primitive recursive.


2

There's a couple of questions here, so a couple of answers. Changing when function parameters evaluated fundamentally changes your extensions of the function. There seems to be a misunderstanding: As primitive recursive functions, both implementation are equivalent and really compute $ifthen$... This depends on exactly what type of $ifthen$ function we'...


2

As you mention, $1$ is primitive recursive according to the following proof: $0$ is primitive recursive (axiom) $\operatorname{suc}$ is primitive recursive (axiom) $1=\operatorname{suc}(0)$ is primitive recursive (composition) Using this you can show that $1$ is admissible, that is if you add $1$ as an axiom, the resulting set of functions is still the ...


Only top voted, non community-wiki answers of a minimum length are eligible