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?
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 $.
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.
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^n$ 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 introductory computability/complexity theory class at my university and my professor made this really helpful animated guide for reasoning about regular, decidable, and recognizable languages.
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
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
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)
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 :
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.
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.
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.
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
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.
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.
