# Are there complexity classes so that RE ⊂ C ⊂ ALL?

If so what are they? These are Computational Complexity Classes that are not in RE but are in ALL. What would a problem in one of these classes look like? Would any of these problems be decidable?

• For example, see en.wikipedia.org/wiki/Arithmetical_hierarchy . Nov 26, 2021 at 13:21
• Any class that contains RE has undecidable problems. Nov 26, 2021 at 14:50
• @Yuval Filmus. Yes i know that. But what I'm asking is are there any decidable problems that are not in RE? Nov 26, 2021 at 19:57
• RE contains all decidable problems. Nov 26, 2021 at 22:19

As has been commented above, decidability implies recursive enumerability - indeed, one of the standard exercises in any computability theory book is proving that a set is decidable iff it is both r.e. and co-r.e. (note that "decidable," "recursive," and "computable" are all synonyms). So no, a fortiori there are no decidable problems outside of $$\mathsf{RE}$$.
But that doesn't mean that there aren't interesting non-r.e. problems or classes of problems. For example, the set $$\mathsf{Tot}$$ of (indices for) Turing machines which halt on all inputs is strictly more complicated than any r.e. set; in a precise sense it is the halting problem's halting problem.