The recursive tag has no wiki summary.
1
vote
2answers
186 views
Primitive Recursive Isomorphisms
What is the relationship between invertible primitive recursive functions (that is, a primitive recursive function that is an isomorphism) and all primitive recursive functions? Can every primitive ...
5
votes
1answer
121 views
How to describe the set of “all computable functions” using Coq?
Would the set of all computable functions be just the set of all maps of the form
f : forall n : nat, P n -> nat
where ...
3
votes
0answers
90 views
Computational complexity of some recursive property
I am currently working on a property of graphs defined as follows. A graph $G$ is said to be OL-AP iff one of the following two conditions holds:
$G$ is an isolated vertex.
$G$ is connected and for ...
8
votes
6answers
895 views
Removing recursion - a look into theory behind the scenes
I am new to this site and this question is certainly not research level - but oh well. I have a little background in software engineering and almost none in CSTheory, but I find it attractive. To make ...
8
votes
2answers
575 views
How to analyze a randomized recursive algorithm?
Consider the following algorithm, where $c$ is a fixed constant.
...
