Skip to content
Tutorials Center
My learning

Topics

Lesson 39 of 59 ยท Decidability and Computability

Countability, Diagonalization and Decidable Problems

Why most languages are unrecognizable: countable and uncountable sets, Cantor's diagonal argument, and a tour of decidable problems for DFAs and CFGs in Python.

Before proving that specific problems are undecidable, we need a clean way to compare sizes of infinite sets. The tool is the idea of countability, due to Georg Cantor. It will deliver the first and most dramatic result of this chapter: there are languages that no Turing machine can recognize, because there are simply more languages than machines.

Countable sets

A set is countable if its elements can be listed in a sequence x1, x2, x3, โ€ฆ in which every element appears at some finite position. Equivalently, there is a one-to-one correspondence with the natural numbers โ„•. Finite sets are countable. Surprising infinite examples:

  • The even numbers: 2n pairs with n, so there are "as many" even numbers as natural numbers.
  • The integers โ„ค: list 0, 1, โˆ’1, 2, โˆ’2, โ€ฆ.
  • Pairs of natural numbers โ„• ร— โ„•: walk the grid diagonal by diagonal. The Cantor pairing function (a, b) โ†ฆ (a + b)(a + b + 1)/2 + b is a bijection.
  • The rational numbers โ„š (pairs of integers, with duplicates removed).
  • All strings over a finite alphabet ฮฃ*: list by length, and alphabetically within each length (shortlex order): ฮต, 0, 1, 00, 01, 10, 11, 000, โ€ฆ.

The last one is the one that matters for us. Every Turing machine has a finite description, a string over some fixed alphabet, so the set of all Turing machines is countable. Consequently the set of recognizable languages is countable: each corresponds to at least one machine.

Python Listing strings and pairs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Uncountable sets and the diagonal argument

Not every infinite set is countable. Cantor's diagonal argument shows that the set of all infinite binary sequences, equivalently the set of all subsets of โ„•, is uncountable.

Proof. Suppose we had a complete list of infinite binary sequences s1, s2, s3, โ€ฆ. Write them as rows of a table and define a new sequence d by flipping the diagonal: the i-th digit of d is the opposite of the i-th digit of s_i. Then d differs from s_i in position i, for every i, so d appears nowhere in the list. This contradicts the assumption that the list was complete.

flowchart TB
    T["Table: row i = the language L_i, column j = is string j in L_i?"] --> D["Diagonal entry (i, i)"]
    D --> F["Flip every diagonal entry"]
    F --> N["New language D: differs from every L_i at string i"]

The same trick, applied to a list of languages, produces a language missing from the list.

Python Diagonalization on a finite table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For languages: every language L โІ ฮฃ* corresponds to its characteristic sequence, with a 1 at position i if the i-th string of ฮฃ* is in L. So the set of all languages has the same size as the set of infinite binary sequences, and is uncountable.

Theorem. There are languages that are not recursively enumerable.

Proof. Turing machines can be listed, so recognizable languages are countable. All languages are uncountable. Hence some languages are not recognizable.

This argument is non-constructive: it proves such languages exist without naming one. The next lesson gives concrete examples, by applying the same diagonal idea to machines themselves.

Decidable problems about automata and grammars

A "problem" in this context is a language of encoded objects: for example A_DFA = { โŸจB, wโŸฉ : B is a DFA that accepts w }. Many natural questions about simple machines are decidable. A decider is an algorithm that always halts.

Problem Statement Decidable? Idea
A_DFA Does DFA B accept w? Yes simulate B
A_NFA, A_REX same, for NFAs and regular expressions Yes convert to DFA, then simulate
E_DFA Is L(B) empty? Yes is any final state reachable?
EQ_DFA Do two DFAs accept the same language? Yes search for a reachable pair where exactly one is accepting
A_CFG Does CFG G generate w? Yes CYK algorithm, or bounded derivation
E_CFG Is L(G) empty? Yes mark variables that can produce terminals
EQ_CFG Do two CFGs generate the same language? No -
ALL_CFG Does G generate every string? No -
A_TM Does Turing machine M accept w? No halting problem
E_TM, EQ_TM emptiness or equality for Turing machines No by reduction

So finite automata have decidable everything. Context-free grammars have decidable membership and emptiness, but not equivalence. Turing machines have decidable almost nothing of interest.

Python Deciders for DFA and CFG problems

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All five procedures always halt, which is exactly what "decidable" means: the reachability searches visit finitely many states; the grammar derivation is bounded by |w| because (without ฮต-rules) forms never shrink, and the productive-variable search stops when nothing changes.

What's next

Everything in the table's "No" rows is proved by one chain of ideas: the diagonal argument, applied to Turing machines, gives the halting problem; reductions then spread undecidability to other problems. We start with the halting problem itself.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is the set of all Turing machines countable?

    Machines can be encoded as strings, and all strings can be listed in shortlex order.
  2. 2. What does the diagonal argument produce when applied to a list of languages?

    Flipping the diagonal gives a language that disagrees with every listed language somewhere.
  3. 3. Which problem is decidable?

    Emptiness of a DFA is a reachability question on a finite graph.
  4. 4. What follows from 'languages are uncountable, machines are countable'?

    There are more languages than machines, so at least one language has no machine.

Summary

  • A set is countable if its elements can be listed; strings, machines, integers, pairs and rationals are countable.
  • Cantor's diagonal argument shows that the set of all languages is uncountable, so some languages are not RE.
  • Membership, emptiness and equivalence are decidable for DFAs; membership and emptiness for CFGs; equivalence of CFGs is undecidable.
  • Almost every interesting question about Turing machines is undecidable.

Next: The halting problem