Questions tagged [primitive-recursion]
The primitive-recursion tag has no usage guidance.
3
questions
0
votes
1
answer
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
7
votes
2
answers
534
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
2
votes
1
answer
833
views
primitive recursion in the lambda calculus
I am having trouble finding out what a primitive subset of the lambda calculus would look like. I reference primitive recursion as shown here: "https://en.wikipedia.org/wiki/...
- 459