1
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.