Difference between Turing-Decidable and Co-Turing-Decidable

Question

I am really struggling with understanding the difference between these two. From my textbook, it essentially describes the difference by saying

a language is co-turing recognizable if it is complement of a turing-recognizable language.

I guess the part of this definition I don't understand is: what does it mean when it is a complement of a turing-recognizable language?

How exactly do you determine if it is a complement of another language?

Answer 1

(A note- the terms "Turing decidable" and "co-Turing decidable" are the same thing. However, "Turing-recognizable" and "co-Turing-recognizable" are not the same, and it's this that I've decided to cover in my answer. The reason for this is that if a language is decidable, then its complement must be decidable as well. The same is not true of recognizable languages.)

Intuitively, a language is Turing-recognizable if there is some computer program that, given a string in the language, can confirm that the string is indeed within the language. This program might loop infinitely if the string isn't in the language, but it's guaranteed to always eventually accept if you give it a string in the language.

While it's true that a language is co-Turing-recognizable if it's the complement of a language that's Turing-recognizable, this definition doesn't shed much light on what's going on. Intuitively, if a language is co-Turing-recognizable, it means that there is a computer program that, given a string not in the language, will eventually confirm that the string is not in the language. It might loop infinitely if the string is indeed within the language, though. The reason for this is simple - if some string w isn't contained within a co-Turing-recognizable language, then that string w must be contained within the complement of that co-Turing-recognizable language, which (by definition) has to be Turing-recognizable. Since w is in the Turing-recognizable complement, there must be some program that can confirm that w is indeed in the complement. This program therefore can confirm that w is not in the original co-Turing-recognizable language.

In short, Turing-recognizability means that there is a program that can confirm that a string w is in a language, and co-Turing-recognizability means that there is a program that can confirm that a string w is not in the language.

Hope this helps!

Answer 2

Let me tell why decidable and co-decidable meant the same with some different usage words. Experienced here, please let me know if I have gone wrong way:

If we have set of strings S which forms L. Then S’ will form L’. Now, L being decidable means we have algorithm / TM which can confirm any string s∈S belongs to L and s'∈S' does not belong to L. Same algorithm will tell us s∈S does not belong to L’ and s'∈S' belongs to L’. So, in other words, we have exact same definition for L’. So, there is no such different meaning to the complement of the concept of decidable language. Hence, both decidable and co-decidable languages are said to be the same.

Answer 3

A language is Recognizable iff there is a Turing Machine which will halt and accept only the strings in that language and for strings not in the language, the TM either rejects, or does not halt at all. Note: there is no requirement that the Turing Machine should halt for strings not in the language.

A language is Decidable iff there is a Turing Machine which will accept strings in the language and reject strings not in the language.