8
$\begingroup$

If you have a language L, without doing any proofs, is there a way to tell if it's recognizable or co-recognizable or decidable?

Basically any hints or tricks that can be used to tell. Or maybe the common patterns to search for to tell which kind it is?

$\endgroup$
  • $\begingroup$ "without doing any proofs", i can kinda prove you anything. (: $\endgroup$ – Ran G. Apr 25 '13 at 2:45
  • 1
    $\begingroup$ In mathematics a "trick" is usually called "theorem", and on some occasions a "lemma". $\endgroup$ – Andrej Bauer Jan 19 '18 at 7:14
  • $\begingroup$ Some common patterns are those addressed by the Rice's theorem (proving a set undecidable) and Rice-Shapiro theorem (proving a set unrecognizable). These are particularly helpful for the pattern "the set of (encoded) TMs $M$ such that, running $M$ we observe this behavior" $\endgroup$ – chi Jan 19 '18 at 12:51
5
+50
$\begingroup$

L is recognizable

A language $L$ is recognizable if and only if there exists a verifier for $L$, where a verifier is a Turing machine that halts on all inputs and for all $w \in \Sigma^*$, $w \in L \leftrightarrow \exists c \in \Sigma^*. V\text{ accepts }\langle w, c\rangle$. Commonly, $c$ is thought of as a "certificate" or "proof" that $w$ is in $L$ and the verifier $V$ checks whether $c$ is a valid proof of $w$ being in $L$. (Note that this definition is equivalent to the recognizer definition because we can construct a recognizer for a language from a verifier for that language). Now to determine whether or not a language is in RE we can ask the following question:

Given a string $w \in L$, could you prove that $w \in L$?

For example, consider $HALT = \{\langle M, w\rangle\ |\ M\text{ is a TM that halts on }w\}$. $HALT$ is recognizable because to prove to you that $M$ halts on $w$, I can just tell you the number of steps you should run $M$ for and if $M$ does halt after that many steps, you would be convinced that $\langle M, w\rangle \in HALT $.

L is co-recognizable

Similarly, a language $L$ is co-recognizable if and only if its complement is recognizable, or in other words if there exists a verifier for $\overline{L}$. Thus to see if a language is in co-RE, we can ask:

Given a string $w \not\in L$, could you prove that $w \not\in L$?

Taking again the example of $HALT$, we can use this intuition to show that $HALT$ is not co-recognizable. This is because if I told you that some machine $M$ does not halt on input $w$, there isn't really anything I can tell you to convince you of that fact. I could run $M$ on $w$ but even if we've been watching $M$ run and haven't seen it halt yet, we don't know that it won't go and halt sometime in the future.

L is decidable

Finally, a language $L$ is decidable if both $L$ and $\overline{L}$ are recognizable. So if the answer to both of the above two questions is yes, then the language is decidable.

As an example, consider $L = \{a^nb^n\ |\ n \in \mathbb{N}\}$. Given a string $w \in L$, could I prove to you that $w \in L$? Sure, I could count up the number of $a$s and the number of $b$s and show that they're equal, so $L$ is recognizable. What about if $w \not\in L$? I could prove that a string is not in $L$ by showing that it's either not of the form $a^nb^m$ or that there's a mismatch in the number of $a$s and $b$s. Thus, $L$ is co-recognizable. Since it's both recognizable and co-recognizable, $L$ is also decidable.

Reference: I'm a TA for an intro computability/complexity theory class at my university and my professor made this really helpful animated guide for reasoning about regular, decidable, and recognizable languages.

$\endgroup$
  • $\begingroup$ Thanks for that link ! and thanks to your prof for making that! it was great $\endgroup$ – void Jan 24 '18 at 12:09
2
$\begingroup$

Main ideas

Being recognizable means you can build an automatic process (we'll get back to that later) that takes a word as a parameter such that

  • If the automatic process ends, it returns either YES or NO.
  • This automatic process doesn't have to terminate on every input, but it has to terminate if the input word is in the language.

Being co-recognizable means the language ${w\in \Sigma^*, w\not\in L}$ (or, in english, the set of all the words that are not in $L$, i.e. its complementary) is recognizable.

Being decidable means you can build an automatic process that takes a word as an input, such that

  • The automatic process always ends
  • It answers YES or NO. If it answers YES, the word is in the language, if it answers NO, the word is not in the language.

One important result is that $L$ is decidable if and only if $L$ is recognizable and co-recognizable.


The idea to prove this result, is that you can build up an automatic process from the processes that recognizability and co-recognizability give you, by alternating steps from both processes, until one of those gives you the answer YES. One of those have to do so, as every word either is or isn't in the language)


Automatic processes

Without being too formal, many types of machines have been designed, and basically all of them have been linked to types of languages (those types depend on the tools needed to define such languages. For more information, Chomsky Hierarchy may help).

The usual meaning of automatic process, regarding to decidability, is a Turing Machine. You can define a Turing Machine such that it can :

  • Receive values from the input
  • Store values
  • Read the values it stored
  • Compute basic mathematical operations on values
  • Test basic mathematical properties on those values, and act accordingly, eventually looping.

Basically, a Turing Machine can do everything you can define in a program, except it is a mathematical object, with infinite memory and time to spend on a computation. It doesn't always terminates.

Another important property of Turing Machines, is that you can describe a Turing machine as a single word (this is encoding), and there exists a Turing machine that, given as inputs the encoding of a machine $M$, and a word $w$, can simulate the computation of $M$ on the input $w$. This will be important in a bit.


Let's just point out that regular languages — which are (almost) the simplest kind of language you can think of from a maths point of view — have the peculiar property that they are closed under complement. This basically means that on those languages, the notions of recognizability and decidability are equivalent. This doesn't hold as you move up in Chomsky Hierarchy.


Example of an undecidable language

We will study the Halting problem. The question is, can we build a Turing Machine that, given the encoding of another Turing Machine $M$ and a word $w$, decides wether $M$ terminates on input $w$ ?

Obviously, this is recognizable, as we just have to simulate $M$ on $w$ until it terminates, and when it does, say YES. However, if $M$ never does terminate, we won't say NO, so we're recognizing this language, but not deciding it. It has been proven that this language cannot be decided by a Turing Machine. This involves a usual mathematical scheme : a diagonal argument, which I wouldn't call intuitive. You can check this sketch of proof to get used to it.

To sum up

You won't be able, given a language, to just state if it's decidable or not. There isn't any algorithm that can do that, and proving a language isn't decidable takes some thinking, and can require some knowledge on Turing Machines, Diagonal arguments, etc...

However, here is my personal way of handling this question. Usually, when studying a language, I assume that it is decidable, unless it shows some form of reference to the way Turing Machine work. In that case, I start warying, and try to define an algorithm deciding the language. If this doesn't look easy, it sometimes help to split up the work in both a recognizing, and a co-recognizing algorithms. If I still can't do it, I'd try to make a connection between this language, and another undecidable one, such as "If I can decide that language, I can decide the halting problem". This is a Turing reduction to an undecidable problem, so the first problem can't be decidable. If all of those fails, I can try to use diagonal arguments, but this can be a bit tricky.

$\endgroup$
1
$\begingroup$

One trick is that if the language is finite, then you know for sure that it is decidable - as you can "hardcode" a machine to accept anything in that language. However I find the easiest way is to simply reduce from another language

$\endgroup$
  • $\begingroup$ Same works for co-finite languages. $\endgroup$ – Raphael Apr 23 '13 at 9:12
  • $\begingroup$ Moreover, a language with a finite solution space given its input will be decidable since you can perform brute force search. $\endgroup$ – jmite Apr 23 '13 at 15:54
1
$\begingroup$

As I mentioned in my comment above, I find it helpful to think about the solution space of the problem.

Think of something like $SAT$. We know that it is decidable, since to test it there is a finite number of solutions we have to try. If there is some finite set of conditions to check, where one of these succeeding guarantees a yes, and none of them succeeding guarantees a no, then the problem is decidable, since we just check the conditions in succession. Note that this set of conditions could be very large (like in the case of NP-complete problems).

Consider now when the solution space is countably infinite, and we can generate each possible solution in sequence, and testing each solution is decidable. In this case we know that the problem is recognizable. For example, a problem asking "is there a natural number such that ..." is recognizable, because we can start at 0, and keep trying every number in sequence. If there is a solution, we are guaranteed to find it, but there is not necessarily a bound on the time it will take to find it. Also, this algorithm would never halt if no such integer existed, so it doesn't prove that a problem is decidable.

You can apply the same technique to the set of all strings, all integers, all graphs, or any finite structure which we can enumerate. This wouldn't work for finding a real number, or a (possibly infinite) set of strings.

Note however, that some problems might have countably infinite solution spaces and still be decidable.

$\endgroup$
  • $\begingroup$ "If the solution space is countably infinite, then we know that the problem is recognizable." -- Not necessarily. First, the solution space may not be effectively enumerable (Example: "Is there a TM that computes a total function and so that [non-trivial predicate]?"). Second, the decision whether the considered object is a solution may be undecidable itself (Example: "Find a TM that does not halt on 77."). $\endgroup$ – Raphael Apr 23 '13 at 17:44
  • $\begingroup$ Ah, that sparks an idea. We know that $NP \subseteq \{L|\ L\ Decidable\}$, so that would imply that if we can show a problem to be in NP (or P for that matter) then it simply follows from that. That could help narrow it down. $\endgroup$ – Steven Apr 23 '13 at 17:45
  • $\begingroup$ Also: "Anything with a finite "set of possibilities" to try will be decidable" -- no. The halting problem has two possible answers but is undecidable. $\endgroup$ – Raphael Apr 23 '13 at 17:45
  • $\begingroup$ @Steven Yes, but that's an even harder proof. (The set you are referring to is typically denoted with R, the set of recursive(ly decidable) languages.) $\endgroup$ – Raphael Apr 23 '13 at 17:46
  • $\begingroup$ I guess I should clarify. The idea is that you can't brute-force the halting problem the way you can, say, 3-SAT. Or how, when you run something on a PDA, you can try all possible paths even though it's non-deterministic. But for a TM, you can't because it could run infinitely long, so the set of "things to try" i.e. the possible paths through the program, is not finite. $\endgroup$ – jmite Apr 23 '13 at 18:01
0
$\begingroup$

The trick to see if a language is undecidable is to ask yourself the question "can I code a computation of Turing machine using this language" ? Or more generally, "does it get as complicated as what happens in a computation ?". Of course sometimes this coding is hard, and it helps to know a list of undecidable problems to reduce to (like Post correspondance problem). If you don't find such a reduction, try thinking of algorithms to decide your language. For instance the language of lists of integers in increasing orders is not finite, but it is easy to design an algorithm testing whether a list is sorted in increasing order, so this language is decidable. And for a lot of languages, we don't know about their decidability, so this is a hard question.

$\endgroup$
  • $\begingroup$ This answer is promoting wrong intuition, see here. $\endgroup$ – Raphael Apr 23 '13 at 17:37
  • $\begingroup$ I don't agree that it's wrong intuition. Of course I didn't mention all the issues, for instance the language can be presented in an excessively complicated way as in your example, and so one has to first simplify it, to get to its "essence". I also didn't mention the fact that there exists undecidable languages "above" halting, and "below" halting, because I don't think it helps the intuition at this level. $\endgroup$ – Denis Apr 24 '13 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.