Theorem 9.2.5: Lne is (partial) Turing-recognizable.
Theorem 9.2.6: Le is not total Turing-recognizable (i.e., the emptiness problem is undecidable).
Corollary 9.2.7: Lne is not total Turing-recognizable (i.e., the non-emptiness problem is undecidable), and Le is not (partial) Turing-recognizable.
Theorem 9.2.9: it is undecidable for Turing machine Twhether or not L(T) is regular.
Previous slide | Next slide | Back to first slide | View graphic version |