19

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?

nbro
  • 15,395
  • 32
  • 113
  • 196
Jason M.
  • 692
  • 2
  • 8
  • 24

3 Answers3

47

(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!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • This does help immensely. I couldn't put into words what I was thinking which makes it difficult to determine the actual definition :) – Jason M. Apr 05 '12 at 16:39
  • Downvoter- Can you please explain what's wrong with this answer? I'd like it to be as useful as possible, and I'm not sure I see what's wrong with it. – templatetypedef Jul 25 '12 at 17:08
  • @templatetypedef I am guessing you just know a lot more about this than the downvoter. – Rob Neuhaus Jul 25 '12 at 18:19
  • You might want to add the significance of a language being both Turing-recognizable and Co-Turing-Recognizable since this implies decidability. – ramblinjan Nov 26 '12 at 17:59
  • if I am not wrong we can say that the language is "recursively enumerable" if it is Turing recognizable. What we can say in terms of recursive enumerability of the language if it is co-Turing recognizable? It is "not recursively enumerable"? – Mahesha999 Dec 22 '16 at 20:28
  • 1
    It's possible that a language is co-Turing recognizable and also recursively enumerable - that means that it's decidable! You sometimes hear the term co-RE tossed around for languages that are co-recursively-enumerable. – templatetypedef Dec 22 '16 at 21:30
0

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.

MsA
  • 2,599
  • 3
  • 22
  • 47
-2

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.

Avinash Singh
  • 5
  • 1
  • This answer completely avoids the question that has been asked, just gave some formal definition. Either he does not understand the question, or avoids it. – Muhammad Razib Apr 02 '15 at 22:28