3
$\begingroup$

This question might sound stupid but, can the language of a TM be not recursively enumerable ?

Thank you ~

$\endgroup$
7
$\begingroup$

No, because A TM has 3 possibilities: run forever, accept, or reject. So the language of a TM is recursively enumerable as the TM M either accepts some input x, which means x is in L(M), or otherwise rejects or runs forever.

A language can be non-recursively enumerable, but the language of a concrete TM is always recursively enumerable.

$\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.