# Questions tagged [primitive-recursion]

The tag has no usage guidance.

61 questions
Filter by
Sorted by
Tagged with
19 views

### Prove a Predicate is Primitive Recursive

Suppose $x$ is Godel's number of some formula. Predicate $\operatorname{P}(\operatorname{f}(x))$ is true only when the number of functions is equal to the number of predicates in that formula. Prove ...
1 vote
58 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
52 views

• 141
466 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
571 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:...
• 459
1 vote
119 views

### Recognizing primitive recursion

I am trying to write a program to recognize if a given lambda calculus expression is primitive recursive. I believe that a general algorithm to do this does not exist, but I am interested in the most ...
• 459