Difference between Turing-Decidable and Co-Turing-Decidable

Go To StackoverFlow.com

16

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?

2012-04-05 16:15
by Jason M.


41

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

2012-04-05 16:31
by templatetypedef
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. 2012-04-05 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 2012-07-25 17:08
@templatetypedef I am guessing you just know a lot more about this than the downvoter - Rob Neuhaus 2012-07-25 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 2012-11-26 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 2016-12-22 20:28
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 2016-12-22 21:30


-1

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.

2014-12-11 04:38
by Avinash Singh
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 2015-04-02 22:28
Ads