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$$ is a TM and $$L(M)$$ is a regular language$$}$$. $$REGULAR_{TM}$$ is undecidable. TODO