Is the set {i | Dom(Φi) = ∅} recursive, recursive enumerable or none of them?
We use Φk to denote the k-th computable function and Dom(Φk) for the set {x | Φk(x) ↓}.
Thank you for your help
Asked
Active
Viewed 64 times
-1
-
This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc. – Carl Mummert Jan 07 '19 at 14:02
-
1This is an exact duplicate of your previous question, unless I'm missing something. Don't do that. – Noah Schweber Jan 07 '19 at 14:35
1 Answers
0
The set is not recursively enumerable.
The theorem of Rice-Shapiro says: Let $A$ be a class of monadic partial recursive functions whose corresponding index set $${\rm prog}(A) = \{x\in{\Bbb N}_0\mid \phi_x\in A\}$$ is recursively enumerable. Then a monadic partial recursive function $f$ lies in $A$ iff there is a finite function $g \in A$ (i.e., $g$ has finite domain) such that $g \subseteq f$ (i.e., $f$ is an extension of $g$).
If the nowhere-defined function $f_\uparrow$ lies in $A$, then all monadic partial recursive functions lie in $A$. Indeed, each monadic computable function extends the nowhere-defined function and so by the theorem of Rice-Shaprio lies in $A$. This is not the case.
Wuestenfux
- 20,964