patternMinor
Undecidable/Decidable Language
Viewed 0 times
decidableundecidablelanguage
Problem
This question might sound stupid but, can the language of a TM be not recursively enumerable ?
Thank you ~
Thank you ~
Solution
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.
A language can be non-recursively enumerable, but the language of a concrete TM is always recursively enumerable.
Context
StackExchange Computer Science Q#66779, answer score: 7
Revisions (0)
No revisions yet.