5.1 Undecidable Problems from Language Theory

定理5.1（halting problem）

$HALT_{TM}=\{<M,w>|M$ is a TM and $M$ halts on input $w\}$

$HALT_{TM}$ is undecidable.

证明方法：反证，若decidable，则能构造出$A_{TM}$也decadable，矛盾。

定理5.2

$E_{TM}$ is undecidable.

定理5.3

$REGULAR_{TM}=\{<M>|M$ is a TM and $L(M)$ is a regular language$\}$.

$REGULAR_{TM}$ is undecidable.

TODO