<aside> 💡 Goal: to prove $\text{decidable $\subset$ RE $\subset$ all languages}$

</aside>

I. RE < All Languages

Countable and Uncountable Sets

The natural numbers $N = \{1,2,3,…\}$ are countable

Definition: a set $S$ is countable if it is finite, or it is infinite and there is a bijection

$$ f: N\rightarrow S $$

<aside> 📖 Theorem: the real numbers $R$ are NOT countable (they are “uncountable”).

</aside>

Wikiwand

<aside> 📖 Theorem: there exist languages that are not Recursively Enumerable.

</aside>

• Lemma: the set of all TMs is countable
• Lemma: the set of all languages is uncountable

The Halting Problem

$$ \text{HALT} = \{\langle M,~x\rangle |\text{~TM $M$ halts on input }x\} $$

<aside> 📖 Theorem: HALT is not decidable (undecidable).

</aside>

1. Suppose TM $H$ decides HALT

   a. if $M$ halts on $x$, $H$ accept

   b. if $M$ does not halt on $x$, $H$ reject

2. Define new TM $H'$: on input <M, x>

   1. if H accepts <M, x>, then loop
   2. if H rejects <M, x>, then halt

%%{
init : { 
	"theme" : "default", 
	"flowchart" : { "curve" : "" }
}
}%%

flowchart LR

classDef blue fill:#2374f7,stroke:#000,stroke-width:2px,color:#fff
classDef pink fill:#eb3dd6,stroke:#000,stroke-width:2px,color:#fff
classDef orange fill:#fc822b,stroke:#000,stroke-width:2px,color:#fff
classDef red fill:#ed2633,stroke:#000,stroke-width:2px,color:#fff
classDef green fill:#16b522,stroke:#000,stroke-width:2px,color:#fff

m[< M, x >] --> hh{halt?}
hh --> |Yes| h11[H.accept]:::green
hh --> |No| h12([H.reject]):::red
h11 --> h21([H'.loop]):::red
h12 --> h22[H'.halt]:::green