Next: The language Ld is
Up: A non-r.e. language: Ld
Previous: definition of wi and Mj
Imagine i and j are arranged in an infinite table, where the
entries in the table are boolean values indicating the acceptance of
word wi by TM Mj. The diagonal of this table (i=j) are the
entries for which the binary code of wi and Mj are the same.
The language Ld is defined as those wi for which the (i,i)
table entry is 0 (false), i.e Ld contains only those strings
which do not code for TMs accepting themselves.
root
6/10/1998