Definition 8.4.2: for _ = {0,1) the diagonal language Ld ___* is defined as follows:
• let
• regard each positive integer i as a description of Turing recognizer Ti if encode(Ti) = the binary expansion of i; if there is no such Turing recognizer, regard i as a description of the Turing machine with no transitions,
• then Ld = {wi | wi_L(Ti)}.
Theorem 8.4.9: the diagonal language Ld is not a partial Turing-recognizable language.
Previous slide | Next slide | Back to first slide | View graphic version |