S.O.S. Mathematics CyberBoard

[Corneo]

I have a quick question about the useage of these terms. As I know if a language is decidable aka rec, then that means there exists a TM that will halt on the input and output either an accept or a reject. Now if a language is recognizable, that means there exists a TM that will halt if it accepts the language, but it may loop forever or enter a reject configuration otherwise. This type of TM is not gurantee to halt.

I wish to know is a decidable language automatically Turing recognizable? I say yes because for a language to be recognizable it has to be in the intersection of rec and co-re. Is this correct?

[Matt]

Hi Corneo,

If a language L is decidable, then there exists a Turing machine for the language which halts on every input. In particular, the Turing machine will halt and accept on every string that is a member of L. That makes L Turing recognizable.

[Corneo]

Thanks Matthew. Are you familiar with the Four Worlds diagram? There are 2 sets in the universe. If one set is the set of re languages. The other set is the set of co-re languages. And the intersection of these sets is the set of decidable languages. I am trying to use this idea to solve another problem I have. I am thinking I might need to use reducibility to show something is not decidable hence it is either in re or co-re. But there is still the possibility is may fall into the neither region. That is everything not i rec, re, and co-re.