Question

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, we can enumerate $S$ by calculating $\{f(0), f(1) \ldots \}$.

What is known about this class of sets? Where does it stand in terms of computability? I suspect that it contains sets that are not context free, and that it does not contain all recursive sets.

Has this been studied? Does anyone have a reference for this?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top