Diagonalization and the Limits of Enumerability

Hello! Welcome to the tenth lesson in our course on the theory of computation.

In our last lesson, we put together the Chomsky Hierarchy, which provided a comprehensive map of language classes from regular to recursively enumerable (RE). We saw that each level of the hierarchy corresponds to a more powerful model of computation. This led us to a natural and profound question: does this map cover everything? Or are there problems so complex that they lie outside even the most powerful class, beyond what any Turing Machine can recognize?

Today, we will answer that question with a definitive "yes." Our learning outcome is to: Use a diagonalization argument to prove that not all languages are recursively enumerable. We will introduce one of the most powerful and elegant proof techniques in computer science and mathematics, a method that allows us to reason about the limits of the infinite.

Framing the Problem: Is the Map Complete?

Recall the hierarchy of languages we established. At the top sit the Recursively Enumerable (RE) languages, which are precisely the set of languages that can be recognized by a Turing Machine.

Hierarchy of Formal Languages — This diagram shows the nested classes of languages. Our goal today is to prove that the outermost region, "Non-recursively enumerable languages," is not empty.

To prove that there are languages outside the RE class, we need to show that there's a mismatch between the number of available Turing Machines and the number of possible languages. To do this, we first need a way to compare the "sizes" of infinite sets.

Part 1: Counting the Infinite

What does it mean for two infinite sets to be the same size? Or for one to be "bigger" than another? The key idea is to see if we can create a one-to-one correspondence (a bijection) between their elements.

A set is countably infinite (or just countable) if its elements can be listed out in a sequence, mapping each one to a unique positive integer (1, 2, 3, ...). The set of all integers and even the set of all rational numbers are countable.
A set is uncountable if it is so large that no such list could ever be complete. No matter how you try to list its elements, you will always miss some.

To get a firm grasp on these definitions, watch the first part of the following video from MIT OpenCourseWare.

S01.8 Countable and Uncountable Sets

This video provides a clear definition of countable and uncountable sets, with several illustrative examples that build intuition.

Please watch from the beginning to 06:18. Focus on the core idea: a set is countable if you can devise a scheme to list all its elements one by one. Notice how even seemingly 'larger' sets like all pairs of integers can be shown to be countable.

Part 2: The Diagonalization Argument

How do we prove a set is uncountable? The classic method is Georg Cantor's diagonalization argument. It's a beautiful proof by contradiction. In essence, you assume the set is countable (i.e., a complete list of its elements exists), and then you use the list itself to construct a new element that, by its very construction, cannot be on the list.

The following video masterfully explains this argument using the set of infinite binary sequences as an example. This is a crucial example for us, as we will soon see that languages can be represented in a very similar way.

What A General Diagonal Argument Looks Like (Category Theory)

This video from the Thricery channel breaks down the diagonalization argument. The first part provides the core intuition, which is exactly what we need for our proof about languages.

Please watch from 01:00 to 04:51. The key is to understand how the 'special sequence' is constructed by flipping the bits along the diagonal of the supposed complete list. This guarantees it differs from every sequence on the list.

The logic is as follows:

Assume you have a complete list that enumerates every infinite binary sequence.
Construct a new sequence by looking at the n-th digit of the n-th sequence in your list and flipping it (0 becomes 1, 1 becomes 0).
This new sequence cannot be on the list. Why? It can't be the first sequence, because it differs in the first position. It can't be the second sequence, because it differs in the second position. In general, it can't be the n-th sequence, because it differs in the n-th position.
This is a contradiction. The new sequence is a valid infinite binary sequence, but it's not on our supposedly complete list. Therefore, the initial assumption must be false, and the set is uncountable.

Part 3: The Proof that Not All Languages Are RE

Now we can assemble our tools to prove the main result. The proof rests on comparing the "size" of two sets:

The set of all Turing Machines (which corresponds to the set of all RE languages).
The set of all possible languages.

We will show that the first set is countable, while the second is uncountable.

Countablility and Diagonalization

This document from Arjun Chandrasekhar's course notes concisely lays out the two halves of our proof. It formally connects the concepts of countability and diagonalization to Turing Machines and languages.

Please read Sections 3 ('Uncountable Sets') and the Corollary 3.1 that follows it. Focus on two key arguments: first, how languages can be represented by infinite binary strings (making the set of languages uncountable); and second, the final conclusion that compares the countable set of TMs to the uncountable set of languages.

Let's walk through the argument step-by-step.

Step 1: The Set of All Turing Machines is Countable

A Turing Machine is defined by a finite set of states, a finite alphabet, and a finite set of transition rules. As you've seen in your work with compilers and development tools, any program or algorithm can be represented as a text file—a finite string of characters.

The same is true for a Turing Machine. We can devise an encoding scheme to represent any TM as a single, finite binary string. For example, we could assign numbers to states, tape symbols, and directions (L/R) and write them out.

Since every Turing Machine can be represented by at least one finite binary string, we can list all TMs by listing all binary strings in order of length, and for each length, in lexicographical order. We would throw out any strings that aren't valid TM encodings. This process creates an exhaustive list of all possible Turing Machines.

Because we can list them, the set of all Turing Machines is countable. This implies that the set of all recursively enumerable languages is also countable.

Step 2: The Set of All Languages is Uncountable

This is where diagonalization comes in. Let's consider languages over a simple alphabet like $Σ = {0, 1}$ .
First, we can list all possible strings in $Σ^{*}$ in a fixed, lexicographical order: $ϵ, 0, 1, 00, 01, 10, 11, 000, \dots$ . Let's call them $w_{1}, w_{2}, w_{3}, \dots$ .

Now, any language $L$ over $Σ$ can be uniquely represented by an infinite binary string (its characteristic sequence), where the i-th bit is 1 if $w_{i} \in L$ and 0 if $w_{i} \in / L$ .

For example:

The language $L = {0, 00, 01}$ would have a characteristic sequence starting 0101100... (assuming the order above, where $w_{1} = ϵ, w_{2} = 0, w_{3} = 1, w_{4} = 00, \dots$ ).
A different language would have a different characteristic sequence.

Since every possible infinite binary string defines a unique language, the set of all possible languages corresponds directly to the set of all infinite binary strings. As we learned from the diagonalization argument, the set of infinite binary strings is uncountable. Therefore, the set of all languages is also uncountable.

This table provides a powerful visualization of how to apply diagonalization directly to languages.

Cantor Diagonalization Table — This image shows a hypothetical list of all languages (L1, L2, ...). Each row is the characteristic sequence for that language. By constructing a new language `L_evil` that flips the diagonal entries, we create a language that cannot be on the list, proving the set of all languages is uncountable.

Step 3: The Conclusion

We have established that:

The set of all RE languages is countable.
The set of all possible languages is uncountable.

There are simply not enough Turing Machines to recognize every possible language. There are infinitely more languages than there are machines. Therefore, there must exist languages that are not recursively enumerable.

A More Constructive Proof

The argument above is a "cardinality argument." It's powerful but a bit abstract. We can also use diagonalization to construct an explicit example of a language that is not RE.

Consider the diagonal language, $L_{d}$ . Let's order all TM encodings as $w_{1}, w_{2}, \dots$ and let $M_{i}$ be the TM with encoding $w_{i}$ .

We define $L_{d}$ as follows:

L_{d} = {w_{i} ∣ the TM M_{i} does not accept the input string w_{i}}

In other words, $L_{d}$ contains the encoding of a TM if and only if that TM rejects its own encoding.

Now, let's use proof by contradiction to show $L_{d}$ is not RE.

Assume $L_{d}$ is RE.
If it is, there must be some Turing Machine, say $M_{k}$ , that recognizes it. So, $L (M_{k}) = L_{d}$ .
Now, the crucial question: What does $M_{k}$ do with its own encoding, $w_{k}$ ? Is $w_{k} \in L_{d}$ ?
- Case A: Suppose $w_{k} \in L_{d}$ .
  Since $L (M_{k}) = L_{d}$ , this means $M_{k}$ accepts $w_{k}$ . But by the definition of $L_{d}$ , for a string $w_{i}$ to be in $L_{d}$ , the machine $M_{i}$ must not accept $w_{i}$ . For $i = k$ , this means $M_{k}$ must not accept $w_{k}$ . This is a contradiction.
- Case B: Suppose $w_{k} \in / L_{d}$ .
  Since $L (M_{k}) = L_{d}$ , this means $M_{k}$ does not accept $w_{k}$ . But by the definition of $L_{d}$ , if $M_{k}$ does not accept $w_{k}$ , then its encoding $w_{k}$ should be in the language $L_{d}$ . This is also a contradiction.

Since both possibilities lead to a contradiction, our initial assumption must be false. Therefore, $L_{d}$ is not recursively enumerable. We have found our concrete example of a language that no Turing Machine can recognize.

The following text formalizes this exact argument.

Module 9

This excerpt from course notes from the University of Waterloo provides a formal walkthrough of the constructive diagonalization proof we just discussed. The language it calls L_NSA (for 'non-self-accepting') is exactly the diagonal language L_d.

Please read sections 9.11 ('An undecidable language') and 9.12 ('L_NSA is not the language of any Turing machine'). This will solidify your understanding of the contradiction.

Test your understanding!

Let's consider the complement of the diagonal language, $L_{d}$ . This language is defined as:
$L_{d} = {w_{i} ∣ the TM M_{i} accepts the input string w_{i}}$
This is often called the "self-accepting" language. We just proved $L_{d}$ is not RE. What can we say about $L_{d}$ ? Is it recursively enumerable?

Show answer

Yes, $L_{d}$ is recursively enumerable. We can construct a Turing Machine that recognizes it. This machine is a variation of the Universal Turing Machine (UTM). Given an input string $w$ , it first checks if $w$ is a valid encoding of a TM, say $M_{w}$ . If it is, it then simulates $M_{w}$ on the input $w$ . If the simulation halts and accepts, our machine accepts. If the simulation rejects or loops, our machine can also loop. This behavior perfectly matches the definition of a recognizer for $L_{d}$ .

This is a fascinating result: we have an RE language ( $L_{d}$ ) whose complement ( $L_{d}$ ) is not RE. This will have important implications for decidability, which we'll explore soon.

Conclusion

Today, we've journeyed to the absolute limits of computation. By wielding the powerful tool of diagonalization, we have formally proven that there are problems that are fundamentally unsolvable by any algorithm or Turing Machine.

Key Takeaways:

Countable vs. Uncountable: We can compare the sizes of infinite sets. The set of Turing Machines is countable, but the set of all languages is uncountable.
Cardinality Mismatch: The uncountability of languages compared to the countability of TMs is a proof that some languages must not be recursively enumerable.
Diagonalization: This proof-by-contradiction technique is the key. It works by assuming a complete list exists and then constructing an element that differs from every item on the list.
The Diagonal Language ( $L_{d}$ ): We constructed a specific, concrete language that is not RE by diagonalizing over the behavior of all Turing Machines on their own encodings.

Preview of the Next Lesson:
We have successfully proven that undecidable problems exist. In our next lesson, we will focus on the most famous undecidable problem of all: the Halting Problem. We will provide a formal proof of its undecidability, which builds directly on the diagonalization concepts we learned today. From there, we will learn a new technique, reducibility, which will allow us to prove that many other important problems are also undecidable by showing they are "at least as hard as" the Halting Problem.

Recommended resources