I'm finding it difficult to find the information online and I can't find the information in my college notes but i'm wondering what complexity-class languages like Atm and Halttm (The TM that always accepts, the TM that always halts respectively) are in. If anyone could explain which class they're in an why that would be great. Also what about languages like NEtm(langague of TM no equal to null). What langague would that fall into and why. Thanks in advance
The correct measure for the complexity of undecidable problems is the arithmetical hierarchy and its extensions. Undecidable problems sit outside all of the complexity classes defined by time or space constraints.