I've searched tons of resources and while conceptually I understand the turing machine itself and what it does- I'm a bit stuck on Turing Recognizable and Turing Decidable languages and I'm not sure if the idea I have about them is right or wrong.
My professor defines four possible actions a Turing machine can do on a given input string:
- Hang: The turing machine goes off the left end of the tape and "hangs"
- Loop: The turing machine goes in a loop- never halts
- Accepts: Turing machine halts in an accepting state
- Rejects: Turing machine halts in a rejecting state
Is a turing recognizable language just one that can either hang or loop? How do I determine if it can hang or loop? Just run it through the machine and if it doesn't halt on the rejecting state (or accepting) and its not part of the language of the TM then I determine its not decidable- so it must be recognizable? And then the decider is if the language is guaranteed to accept or reject? What about languages that aren't recognizable? What would they do? Because it seems that all languages would be recognizable unless it would be possible for the language to not be in the language of the turing machine- but it halts in the accepting state anyways. Which seems like it would be due to bad design of the turing machine rather than the language itself.
Just struggling to understand these two definitions. I've been studying for my exam which is tomorrow for hours and I just can't grasp what should be a simple concept. Please help clear up my confusion?
Best Answer
A language $L$ is said to be recursively enumerable if there exists a Turing Machine $M$ satisfying the following conditions:
-For every $\omega \in L$, simulating $M$ on $\omega$ (which we denote $M(\omega)$) results in $M$ halting and accepting $\omega$. -For every $\omega \in \Sigma^{*} \setminus L$, $M$ does not accept $\omega$.
Note that for a recursively enumerable language, any TM accepting $L$ need not halt on inputs outside of the language.
If $L$ is decidable, there must exist some TM that halts on all inputs in addition to the conditions for $L$ being recursively enumerable.
No such decider or recognizer would exist. Consider the following language: $L_{NOT-HALT} = \{ \langle M_{i} \rangle, \omega_{i} : M_{i}$ is the $i$th TM and $\omega_{i}$ is the $i$th string in $\Sigma^{*}$ and $M_{i}$ does not halt on $\omega_{i} \}$.
The language $L_{NOT-HALT}$ is not recursively enumerable. No TM can accept every string in $M_{i}$. For some TMs in $L_{NOT-HALT}$, it may be possible to recognize an infinite loop by checking the states and transition function. However, there is no general procedure to do this for all TMs in $L_{NOT-HALT}$. A Cantor diagonal argument proves this. See the undecidability of the halting problem.
Does this clear things up?