Given this question:$L$ is an infinite language of encoded Turing machines who always halt.$L$ might be decidable $L$ might be in RE but not in Rboth 1. and 2. are correctI know the solution to this question is 3., but I seem to lack the understanding on how am I suppose to get to that solution. Could you explain how should I approach this kind of questions? Am I supposed to start drawing TMs?Why is the answer is C? What's the indication of that?It would help me a lot if you could explain to me your thought process when facing this kind of problem.
Classifying infinite languages of encodings of halting Turing machines
computability;turing machines
There are certainly examples for all levels:It is easy to give an infinite set of encodings that is decidable. Consider all programs of the form f(x) = x + i -- definitely an infinite and decidable set.Classic examples (think Halting problem) are semi-decidable but not decidable. $L = \{ \langle M \rangle \mid f_M(\langle M \rangle) = 1\}$Other classic examples (think complement of Halting problem) are not semi-decidable.  $L = \{ \langle M \rangle \mid f_M(\langle M \rangle)\uparrow \}$