next up previous contents
Next: The language Ld is Up: A non-r.e. language: Ld Previous: definition of wi and Mj

acceptance table

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.