Countable vs uncountable; diagonalization

1. Why are TMs countable?
   Stuck? Peek at 4.4 Encoding TMs, the universal TM, and the Church–Turing thesis

   • ⟨M⟩: binary code of transitions (0ⁱ1 0ʲ1 0ᵏ1 0ˡ1 0ᵐ, separated by 11). TMs are countable.
   • Universal TM U: simulates M on w; L(U) = {⟨M,w⟩ : M accepts w} is RE.
   • Church–Turing thesis: algorithm ⇔ TM (thesis, not theorem).

   Read lesson 4.4

2. What is a bijection?
   Stuck? Peek at 0.2.2 Functions, relations and equivalence classes

   • Relation ⊆ A × B. Function: every input exactly one output. Partial function: some inputs have none.
   • #functions A→B = |B|^|A|. #one-to-one (|A| ≤ |B|) = |B|·(|B|−1)···. #relations on n-set = 2^(n²).
   • Equivalence = reflexive + symmetric + transitive. Classes partition the set; number of classes = index.
   • Finer relation (refinement) ⇒ more classes; every fine class sits inside a coarse class.

   Read lesson 0.2.2

3. Shortlex order lists Σ* how?
   Stuck? Peek at 0.3.2 Σᵏ, Σ*, Σ⁺ and languages

   • |Σᵏ| = |Σ|ᵏ; Σ⁰ = {ε}; Σ* = ⋃ Σᵏ (k ≥ 0); Σ⁺ = Σ* − {ε}.
   • #strings of length ≤ n over k symbols = (kⁿ⁺¹ − 1)/(k − 1); binary: 2ⁿ⁺¹ − 1.
   • Language = any subset of Σ*. ∅ (no strings) ≠ {ε} (one string). Exactly r of one symbol in length n (binary): C(n, r).
   • Shortlex order lists every string at a finite position.

   Read lesson 0.3.2

Here is the shortest proof that some problems have no algorithm: count. There are only countably many programs (each is a finite string), but uncountably many problems (sets of strings). More problems than programs — so most problems have no program at all. This lesson makes “countably many” and “uncountably many” precise, using Cantor’s diagonal trick, the same trick that proves the halting problem undecidable.

Are there “more” even numbers than natural numbers, fewer, or the same number?

Prediction check

The same. n ↦ 2n pairs every natural number with exactly one even number (a bijection). For infinite sets, “same size” means “a bijection exists”, and a part can be as big as the whole.

Countable sets

Countable: ℕ, the integers (0, 1, −1, 2, −2, …), pairs ℕ × ℕ (walk the diagonals), Σ* (shortlex order), the set of all TMs (list their codes), every language’s set of strings.

Uncountable sets and Cantor’s diagonal

Proof: suppose the languages could be listed L₁, L₂, …. Build D = { wᵢ : wᵢ ∉ Lᵢ } — for each i, D disagrees with Lᵢ about the string wᵢ. So D is not on the list, contradicting that the list was complete. ∎

More languages than machines

TMs are countable; languages are uncountable. Each TM recognizes one language, so only countably many languages are RE. Therefore uncountably many languages are not RE — in fact “almost all” languages have no recognizer, let alone a decider.

Diagonalization as a technique

Whenever a list claims to contain every object of some kind, build an object that differs from the i-th one at position i. If your object belongs to the kind, the list was incomplete. Next lesson aims this weapon at Turing machines themselves.

Putting it together

• Countable means listable; Σ* and the set of TMs are countable.
• The diagonal argument shows P(Σ*) is not.
• So almost all languages have no recognizer.

countable:   ℕ  ℤ  ℚ  ℕ×ℕ  Σ*  {all TMs}  {all RE languages}  {all regular languages}
uncountable: P(ℕ)  ℝ  P(Σ*) = {all languages}  {infinite binary sequences}

Counting proves non-RE languages exist but names none. Next: diagonalize against TMs directly to get concrete ones — L_d, and then the most famous of all, the halting problem.

1. MSQ

   Which sets are countable?

   1. Σ*
   2. the set of all TMs
   3. the set of all languages over Σ
   4. ℕ × ℕ
2. MCQ

   The counting argument shows:

   1. every language is RE
   2. some languages are not RE
   3. the halting problem is RE
   4. Σ* is uncountable
3. MCQ

   Cantor’s diagonal language D = { wᵢ : wᵢ ∉ Lᵢ } differs from Lᵢ:

   1. nowhere
   2. at the string wᵢ
   3. at every string
   4. only on ε
4. MCQ

   The set of all languages over the alphabet {a} is:

   1. finite
   2. countably infinite
   3. uncountable
   4. empty

• countable set
• bijection with ℕ
• uncountable set
• Cantor’s diagonal argument
• diagonalization
• counting argument (non-RE languages exist)

1. Is Σ* countable?
   Reveal answer

   Yes (shortlex).
2. Is the set of all languages over Σ countable?
   Reveal answer

   No — it is P(Σ*), uncountable.
3. Why must non-RE languages exist?
   Reveal answer

   TMs are countable; languages are uncountable.