The Decision Problem for Decision Problems
- Yuri Gurevich
Algebra and Logic | , Vol 8: pp. 362-363
Consider the collection D of first-order formulas α such that the first-order theory with axiom α is decidable. It is proven that D is neither r.e. nor co-r.e. (The second part has been known earlier.)