Chapter 30 of 34

Decidability: Recursive & Recursively Enumerable Languages

So far we have asked "which machine accepts this language?". From now on we ask a sharper question: can this problem be solved by an algorithm at all? For example: given a DFA, is its language empty? Given two DFAs, do they accept the same language? Given a program and an input, does the program ever stop?

To answer such questions precisely we need to say exactly what "solved by an algorithm" means. The Church–Turing thesis (see Variants of Turing Machines) tells us that algorithm = Turing machine. But there is a subtlety: a TM might answer "yes" reliably but, on "no" instances, run forever without ever answering. That gives two levels of solvability, and two classes of languages.

A language L is recursive (decidable) if some Turing machine accepts L and halts on every input. L is recursively enumerable, RE (semi-decidable, Turing-recognizable), if some Turing machine accepts L, where on inputs not in L it may either reject or run forever.

In this chapter we define these classes carefully, show that many natural problems about automata and grammars are decidable (with algorithms you could code today), prove the closure properties of both classes, prove the key theorem that L is recursive if and only if both L and its complement are RE, and see by a counting argument that some languages are not even RE. The DFA-equivalence decider in this chapter was run in Python on the examples shown.


Problems as Languages

A decision problem is a question with a yes/no answer for each instance. We turn it into a language by encoding each instance as a string and collecting the "yes" instances. For any object O (a DFA, a grammar, a TM, a number), ⟨O⟩ denotes its encoding as a string, and ⟨O1, O2⟩ encodes a pair. For TMs, one such encoding was given in Variants of Turing Machines.

Problem

Language

Does DFA D accept w?

ADFA = { ⟨D, w⟩ : D accepts w }

Is L(D) empty?

EDFA = { ⟨D⟩ : L(D) = ∅ }

Do D1 and D2 accept the same language?

EQDFA = { ⟨D1, D2⟩ : L(D1) = L(D2) }

Does CFG G generate w?

ACFG = { ⟨G, w⟩ : w ∈ L(G) }

Does TM M accept w?

ATM = { ⟨M, w⟩ : M accepts w }

"The problem is decidable" means exactly "its language is recursive". A decider is expected to reject strings that are not valid encodings at all; checking the format is always easy, so we ignore it from here on.


Deciders and Recognizers

Recall from Turing Machines that on an input w a TM M either accepts, rejects (halts without accepting), or loops forever.

Input

Decider (for a recursive L)

Recognizer (for an RE L)

w ∈ L

halts and accepts

halts and accepts

w ∉ L

halts and rejects

rejects or loops forever

A decider always gives an answer; a recognizer only guarantees an answer for "yes". Watching a recognizer that has run for a long time tells you nothing: it may accept in the next step, or never.

Every recursive language is RE (a decider is a special recognizer). The converse is false; in Halting Problem & Undecidability we will see ATM is RE but not recursive.

Name used here

Other names you will meet

Recursive language

decidable, Turing-decidable, total TM language, solvable problem

Recursively enumerable (RE) language

semi-decidable, Turing-recognizable, partially decidable, Type 0 language

Non-recursive language

undecidable, unsolvable problem

Careful: "undecidable" means "not recursive"; an undecidable language may still be RE.


Decidable Problems About Automata and Grammars

Here is the good news: almost every natural question about finite automata, and several about CFGs, is decidable. Each algorithm below always halts.

ADFA: does DFA D accept w?

Simulate D on w for |w| steps and look at the final state. A DFA cannot loop: it reads one symbol per step and stops at the end of the input. Decidable.

ANFA and AREX

Convert the NFA to a DFA by subset construction (or the regular expression to an ε-NFA and then to a DFA) and use the decider for ADFA. Both conversions always finish. Decidable. This is a typical pattern: a decider may call other deciders as subroutines.

EDFA: is L(D) = ∅?

L(D) is non-empty exactly when some final state is reachable from the start state. Mark the start state, repeatedly mark every state with an arrow from a marked state, and stop when nothing new is marked (at most |Q| rounds). Accept (L is empty) if no final state is marked. Decidable.

EQDFA: is L(D1) = L(D2)?

The languages differ exactly when the symmetric difference (L1 ∩ L̄2) ∪ (L̄1 ∩ L2) is non-empty. Regular languages are closed under all these operations, so build a DFA for it (the product construction) and test emptiness. In code, we explore reachable pairs (p, q) of states and look for a pair where exactly one is final:

from collections import deque

def equivalent(D1, D2, alphabet):
    """Decide L(D1) == L(D2). Each DFA = (start, finals, delta) with delta[(q, a)] = p.
    Returns (True, None) or (False, shortest string accepted by exactly one DFA)."""
    s1, F1, d1 = D1
    s2, F2, d2 = D2
    start = (s1, s2)
    parent = {start: None}
    queue = deque([start])
    while queue:                                   # BFS over reachable state pairs
        p, q = queue.popleft()
        if (p in F1) != (q in F2):                 # one accepts, the other rejects
            w, node = [], (p, q)
            while parent[node] is not None:
                node, a = parent[node]
                w.append(a)
            return False, ''.join(reversed(w))
        for a in alphabet:
            nxt = (d1[(p, a)], d2[(q, a)])
            if nxt not in parent:
                parent[nxt] = ((p, q), a)
                queue.append(nxt)
    return True, None                              # finitely many pairs: always halts

# D1: even number of a's (2 states)
D1 = ('E', {'E'}, {('E','a'):'O', ('O','a'):'E', ('E','b'):'E', ('O','b'):'O'})
# D2: counts a's mod 4, accepts counts 0 and 2 (a bigger DFA, same language)
D2 = (0, {0, 2}, {(0,'a'):1, (1,'a'):2, (2,'a'):3, (3,'a'):0,
                  (0,'b'):0, (1,'b'):1, (2,'b'):2, (3,'b'):3})
# D3: meant to be 'even number of a's', but has a bug in the move (2, b)
D3 = (0, {0, 2}, {(0,'a'):1, (1,'a'):2, (2,'a'):1, (0,'b'):0, (1,'b'):1, (2,'b'):1})
print(equivalent(D1, D2, 'ab'))
print(equivalent(D1, D3, 'ab'))

Output:

(True, None)
(False, 'aab')

D3 wrongly goes from state 2 (even) to state 1 (odd) on b, so it rejects aab, which has two a's; aab is the shortest string on which the two machines disagree. The loop always terminates because there are at most |Q1| × |Q2| pairs. Decidable. (Another method: minimise both DFAs and compare, using the uniqueness of the minimal DFA from DFA Minimization.)

ACFG: does CFG G generate w?

Convert G to Chomsky normal form and run the CYK Algorithm. Decidable. A naive alternative: in CNF a derivation of a non-empty w has exactly 2|w| − 1 steps, so try all derivations of that length.

Trying derivations without CNF would be a mistake: a general grammar can have arbitrarily long derivations (unit cycles, ε-rules) and the search might never end.

ECFG: is L(G) = ∅?

Mark generating variables bottom-up (see Closure & Decision Properties of CFLs) and check whether S gets marked. Decidable.

Consequence: every CFL is recursive

For a fixed CFL L with grammar G, the TM "on input w, run CYK for G on w" halts on every input and accepts exactly L. So

Regular  ⊂  CFL  ⊂  CSL  ⊂  Recursive  ⊆  RE

(CSL ⊂ Recursive was shown in Chomsky Hierarchy & Linear Bounded Automata. Whether the last ⊆ is proper is settled in the next chapter.)

Not everything about CFGs is decidable, though: EQCFG (are two CFGs equivalent?) and "does G generate all of Σ*?" are undecidable. Why does the EQDFA trick fail for CFGs? Because it needs complement and intersection, under which CFLs are not closed.


Closure Properties of Recursive Languages

Let M1 and M2 be deciders for L1 and L2. Because they always halt, we can run them one after the other.

Operation

Decider for the result, on input w

Complement L̄1

Run M1; accept if it rejects, reject if it accepts. (Swap the answers.)

Union L1 ∪ L2

Run M1, then M2; accept if either accepted.

Intersection L1 ∩ L2

Run M1, then M2; accept if both accepted.

Difference L1 − L2

= L1 ∩ L̄2

Concatenation L1L2

For each of the |w| + 1 ways to split w = xy, run M1 on x and M2 on y; accept if some split works.

Kleene star L1*

Accept if w = ε; otherwise try each of the 2|w|−1 ways to cut w into non-empty pieces and check every piece with M1. Finitely many cuts, so it halts.

Reversal L1R

Reverse w, run M1.

Inverse homomorphism h−1(L1)

Compute h(w), run M1.

Not closed under (arbitrary) homomorphism. To decide whether w ∈ h(L) we would have to search for some x ∈ L with h(x) = w. If h erases symbols, there are infinitely many candidates x, and the search may never end. In fact every RE language is an erasing homomorphic image of some recursive language. (For ε-free homomorphisms, |x| ≤ |w|, so the search is finite and recursive languages are closed.)


Closure Properties of RE Languages

Now M1 and M2 are only recognizers: they may run forever on strings not in their languages. This changes the constructions.

Union needs parallel simulation

The naive approach "run M1 on w; if it rejects, run M2" fails. Suppose w ∉ L1 but w ∈ L2, and M1 loops on w. Then we never get to start M2, and we wrongly fail to accept w.

Instead, run them in parallel, one step at a time (for example, on a 2-tape TM, or alternating steps on one tape):

On input w:
  for k = 1, 2, 3, ...:
      run step k of M1 on w        if M1 has accepted, ACCEPT
      run step k of M2 on w        if M2 has accepted, ACCEPT
      (if both have halted and rejected, REJECT)

If w ∈ L1 ∪ L2, one of them accepts after some finite number of steps, and the parallel run reaches that step. So RE is closed under union.

The other operations

  • Intersection: run M1 on w; if it accepts, run M2 on w; accept if both accept. Sequential is fine here: if w is in both, both runs finish. If either loops, w is not in the intersection anyway.

  • Concatenation: there are |w| + 1 splits; for each split we need M1(x) and M2(y) to accept. Run all splits in parallel (or use a nondeterministic TM that guesses the split). Closed.

  • Kleene star: guess the cutting of w nondeterministically, check each piece. Closed.

  • Homomorphism: guess x with h(x) = w and check x ∈ L1; a nondeterministic TM (or dovetailing over all x and all step counts) does it. Closed, even for erasing h.

  • Reversal, inverse homomorphism, intersection with regular: closed, as for recursive languages.

  • Complement: NOT closed. Swapping answers fails because a recognizer may never give a "reject" answer to swap. The next chapter shows a concrete RE language whose complement is not RE.

Side by side

Operation

Recursive

RE

Union

Yes

Yes (parallel simulation)

Intersection

Yes

Yes

Complement

Yes

No

Difference

Yes

No (but RE − recursive is RE)

Concatenation, Kleene star

Yes

Yes

Reversal, inverse homomorphism

Yes

Yes

Homomorphism (arbitrary)

No

Yes


The Complement Theorem

Theorem: L is recursive if and only if both L and its complement L̄ are recursively enumerable.

(⇒) If L is recursive, so is L̄ (swap answers). Every recursive language is RE. So both are RE.

(⇐) Let M1 recognise L and M2 recognise L̄. Build M:

M on input w:
  run M1 and M2 on w in parallel, one step each at a time
  if M1 accepts:  ACCEPT
  if M2 accepts:  REJECT

Every w is in exactly one of L and L̄, so exactly one of M1, M2 eventually accepts. Hence M always halts, and it accepts exactly L. So L is recursive.

Intuitively: a recognizer for L gives certified "yes" answers, a recognizer for L̄ gives certified "no" answers, and together they give a decider.

The four boxes

For any language L, exactly one of these cases holds:

L

L̄

Possible?

Example

Recursive

Recursive

Yes

ADFA, any CFL, any CSL

RE, not recursive

not RE

Yes

L = ATM (next chapter)

not RE

RE, not recursive

Yes

L = complement of ATM

not RE

not RE

Yes

{ ⟨M⟩ : L(M) = Σ* } (see Reductions & Rice's Theorem)

Recursive

not recursive

Impossible

recursive languages are closed under complement

RE, not recursive

RE

Impossible

by the complement theorem L would be recursive

A very common exam shortcut: if L is RE but not recursive, then L̄ is not RE.


Why "Recursively Enumerable"? Enumerators Again

In Variants of Turing Machines we saw that L is RE exactly when some enumerator (a TM with a printer) prints all strings of L, in some order, possibly with repeats. Recursive languages have a nice enumerator characterisation too. Use shortlex (canonical) order: shorter strings first, strings of the same length in dictionary order: ε, 0, 1, 00, 01, 10, 11, 000, ....

An infinite language L is recursive if and only if some enumerator prints exactly the strings of L in increasing shortlex order. (Finite languages are regular, hence recursive.)

  • (⇒) With a decider M: for each string s in shortlex order, run M on s (it halts) and print s if accepted. The output is in order.

  • (⇐) To decide w: run the enumerator until it prints w (accept) or prints some string that comes after w in shortlex order (reject; since output is increasing, w will never appear). Because L is infinite, one of these happens after finitely many steps.

So the difference between RE and recursive is the difference between "listable in some order" and "listable in order", which is exactly what lets you stop searching.


Not Every Language Is RE: A Counting Argument

Before seeing a specific non-RE language, here is a short argument that most languages are not RE.

  1. There are countably many TMs. Every TM has an encoding as a finite binary string, and the finite binary strings can be listed: ε, 0, 1, 00, 01, .... So TMs can be listed M1, M2, M3, ..., and so can the RE languages L(M1), L(M2), ....

  2. There are uncountably many languages over {0, 1}. List all strings w1 = ε, w2 = 0, w3 = 1, w4 = 00, .... A language is the same as an infinite 0/1 sequence (1 at position i if wi is in it). Given any list of languages, build a new one by flipping the diagonal:

             w1=ε   w2=0   w3=1   w4=00  ...
  L1           1      0      0      1
  L2           0      0      1      1
  L3           1      1      1      0
  L4           0      1      0      0
  ...
  diagonal:    1      0      1      0     ...
  flipped D:   0      1      0      1     ...   D differs from every Li at wi

D differs from Li on string wi, so D is not in the list. No list can contain all languages (Cantor's diagonal argument).

Countably many recognizers but uncountably many languages: some languages (in fact, almost all) are not RE. This proof does not name one. A concrete non-RE language, the diagonal language Ld = { ⟨M⟩ : M does not accept ⟨M⟩ }, is obtained by applying the same diagonal trick to the list of TMs; that is done in Halting Problem & Undecidability.


The Big Picture

┌──────────────────────────────────────────────────────────────┐
│ All languages (uncountably many)              e.g. L_d        │
│  ┌────────────────────────────────────────────────────────┐  │
│  │ RE (semi-decidable): a TM says "yes" when the answer   │  │
│  │ is yes                                     e.g. A_TM    │  │
│  │  ┌──────────────────────────────────────────────────┐  │  │
│  │  │ Recursive (decidable): a TM always halts         │  │  │
│  │  │   A_DFA, E_DFA, EQ_DFA, A_CFG, E_CFG,            │  │  │
│  │  │   every CSL, every CFL, every regular language   │  │  │
│  │  └──────────────────────────────────────────────────┘  │  │
│  └────────────────────────────────────────────────────────┘  │
└──────────────────────────────────────────────────────────────┘

Common Mistakes

  • "A TM accepts L, so L is decidable." Only if the TM halts on every input. Accepting L only makes L RE.

  • Running recognizers one after the other. For union (and for the complement theorem) the first one might loop. Interleave their steps.

  • "Undecidable means no TM accepts it." No: undecidable (non-recursive) languages like ATM are still RE.

  • "Every subset of a decidable language is decidable." False: every language over Σ is a subset of the decidable language Σ*.

  • Thinking "decidable" is about one instance. Decidability is about a whole infinite family of instances. Any single yes/no question (say, "does this particular TM halt on this particular input?") is trivially decidable: one of the two machines "always accept" or "always reject" answers it correctly, even if we do not know which.

  • Mixing up the directions of the complement theorem. L recursive ⇔ L and L̄ both RE. Not "L RE ⇒ L̄ RE".


Practice and GATE-Style Questions

Q1. L1 is recursive and L2 is RE but not recursive. Which of the following are necessarily RE: (a) L1 ∪ L2 (b) L1 ∩ L2 (c) L̄2 (d) L2 − L1 (e) L1 − L2?

(a) RE (L1 is also RE). (b) RE. (c) Not RE: if it were, L2 would be recursive by the complement theorem. (d) L2 ∩ L̄1, where L̄1 is recursive, hence RE: RE. (e) L1 ∩ L̄2: not necessarily RE. Take L1 = Σ*; then it is L̄2, which is not RE.

Q2. Both L and L̄ are recursively enumerable. What can you conclude?

L is recursive (and so is L̄). Run both recognizers in parallel; exactly one accepts.

Q3. Which of these problems are decidable: (a) EDFA (b) EQDFA (c) ACFG (d) ECFG (e) EQCFG?

(a) to (d) are decidable (reachability, product + emptiness, CYK, generating symbols). (e) is undecidable.

Q4. Why does the decider for L1* (L1 recursive) halt, and why would the same construction not prove that RE languages are closed under star by running pieces one at a time?

For a recursive L1, each check of a piece halts, and there are only 2|w|−1 ways to cut w, so the whole search halts. For an RE L1, checking one piece may loop forever, blocking all other cuts. RE languages are closed under star, but the proof must check all cuts in parallel or guess the cut nondeterministically.

Q5. Is the set of all TMs countable? Is the set of all languages over {a}?

TMs: countable (each has a finite binary encoding). Languages over {a}: uncountable. They correspond to subsets of {ε, a, aa, ...}, i.e. to infinite 0/1 sequences. So even over a one-letter alphabet, some languages are not RE.

Q6. A recognizer M for L has been simulated on w for 106 steps without halting. Someone also has a recognizer M' for L̄, which has not accepted w in 106 steps either. What do you know?

Nothing yet about w, but you do know L is recursive, and the parallel simulation of M and M' is guaranteed to finish eventually on w with the correct answer.

Q7. Interview: why is ADFA decidable while ATM (asked in the next chapter) is not, when both just ask "does the machine accept w"?

A DFA always halts after exactly |w| steps, so simulation is a decider. A TM can run forever, and simulation alone cannot tell "has not halted yet" from "will never halt". The next chapter proves that no cleverer method can work either.


Summary

  • Recursive (decidable): some TM accepts L and halts on every input. RE (semi-decidable): some TM accepts L, possibly looping on strings not in L.

  • Regular ⊂ CFL ⊂ CSL ⊂ Recursive ⊆ RE (the last inclusion is proper: next chapter).

  • Decidable: ADFA, ANFA, AREX, EDFA, EQDFA, ACFG, ECFG. Undecidable: EQCFG.

  • Recursive languages are closed under union, intersection, complement, difference, concatenation, star, reversal and inverse homomorphism, but not arbitrary homomorphism.

  • RE languages are closed under union (by parallel simulation), intersection, concatenation, star, homomorphism, but not complement.

  • L is recursive ⇔ L and L̄ are both RE. So if L is RE but not recursive, L̄ is not RE.

  • L is RE ⇔ some enumerator lists it; an infinite L is recursive ⇔ some enumerator lists it in shortlex order.

  • TMs are countable and languages are uncountable, so non-RE languages exist.

A decider always answers; a recognizer only promises to say "yes". Two recognizers, one for "yes" and one for "no", run side by side make a decider, and that single idea organises everything about recursive and recursively enumerable languages.