Questions tagged [primitive-recursion]

The tag has no usage guidance.

66 questions
Filter by
Sorted by
Tagged with
44 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. ...
• 357
93 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 ...
82 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 ...
• 231
1 vote
59 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
70 views

• 199
1 vote
68 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
79 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
236 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
36 views

159 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
61 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.8k
131 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) ?
1 vote
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 ...
401 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 ...
242 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
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
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 ...
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
94 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,523
122 views

• 175
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
573 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
86 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 ...
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 ...