The emptiness problem for Turing machines (also raised for grammars, etc.): given a Turing machine T, is L(T) = _?
The language version of this problem is Le = {encode(T) | L(T) = _}, where Turing machine T is encoded by previously discussed means.
The non-emptiness problem for Turing machines (also raised for grammars, etc.): given a Turing machine T, is L(T) ° _?
The language version of this problem is Lne = {encode(T) | L(T) ° __}, where Turing machine T is encoded by previously discussed means.
Previous slide | Next slide | Back to first slide | View graphic version |