# Turing Machine Encoding and Complement of the Diagonal Language

In trying to understand how Turing Machine encoding works, there is a question that I have come across that goes something like this:

Given that the diagonal language, $L_d = \{ w_i \mid w_i \space is \space not \space accepted \space by \space M_i \}$, what is the first string of the encoding of the complement of $L_d$ which is $\bar{L_d}$?

I am assuming also that this is operating with the alphabet of $\Sigma = \{0, 1\}$. Is there any way that it is even possible? I am confused also since $L_d$ is an undecidable language how this is possible?

Also by encoding I think that the question is referring to binary encoding with a tape alphabet $\{0, 1, B\}$ with Turing machine $M$ defined as:

$M = < Q, \{0, 1\}, \{0, 1, B\},\delta,q_1,B,\{q_2\} >$

with moves defined by:

$\delta(q_i,X_j) = (q_k,X_n,D_m) \rightarrow 0^i10^j10^k10^n10^m$

where $X_1 = 0, X_2 = 1, X_3 = B$ and Direction is given by: $D_1 = L, D_2 = R$,

and the Binary encoding of $M$ as $<M>$: $111 \space move_1 \space 11 \space move_2 \space 11 \space ... \space 11 \space move_{last} \space 111$

Update: If my understanding is correct, the correct encoding should represent a Turing machine which accepts every string since originally we do not accept any string? How would one go about formulating an encoding for such a Turing machine? Does it have to be a unique encoding, or does it just imply that any Turing machine that accepts every string is valid?

• I'm afraid you're using non-standard notation. $M_i$ is probably the $i$th Turing machine, $w_i$ its description (i.e. $\langle M_i \rangle$). What do you mean by the encoding of $\overline{L_d}$? How do you encode infinite objects? Perhaps the question asked for the first word in $\overline{L_d}$ which is also an encoding of some Turing machine. – Yuval Filmus Nov 12 '13 at 0:01
• I think the question asks for the first string, which I suppose could be interpreted as the first word as you have pointed out. Also I updated the question to show what I mean by encoding, which is essentially a binary encoding of the Turing machine. – rsxjan Nov 12 '13 at 1:19
• In that case, I suggest you go through the first few TM encodings in lexicographic order, looking for the first one which is not in $L_d$. (It will probably be a machine accepting every string.) – Yuval Filmus Nov 12 '13 at 9:25
• I tried to follow this line of logic but haven't been able to come up with a unique solution. How would one go about finding the first encoding not in $L_d$? Would a correct encoding just be any binary encoding that accepts every string? I'm not sure what would be the correct way? – rsxjan Nov 12 '13 at 19:22
• You would go over all encodings in lexicographic order. For each one, you would check whether it's not in $L_d$. The first one which is not in $L_d$ is the answer. – Yuval Filmus Nov 12 '13 at 21:33

## 1 Answer

The following hint repeats my comments and assumes that the question asks for the first encoding of a Turing machine which is in $\overline{L_d}$.

Hint: Make a list of the first few encodings of Turing machines, in lexicographic order. For each one, check whether it's in $\overline{L_d}$. The first one which is in $\overline{L_d}$ is the answer.

By the way, how does your encoding handle termination? Does it mark accepting/rejecting states in some way, or does it use another convention?

• With regards to termination and accept/reject states, 111 at the start of the string is the beginning of the binary encoding of $<M>$ and again at the end of the string it denotes the end. The moves (or the states) are binary numbers with 11 between them as a delimiter. – rsxjan Nov 12 '13 at 22:27
• So how do you know if $M$ accepts a certain string? Does it need to get to a special state? You haven't explained that part. – Yuval Filmus Nov 12 '13 at 23:14
• It is assumed that $M$ accepts a certain string, otherwise there would not be an encoding for the Turing machine altogether. Or at least this is my understanding of the problem. – rsxjan Nov 12 '13 at 23:21
• Let me rephrase my question. The description of a Turing machine $M$ doesn't contain the information of which states are accepting and which are rejecting, or which states are terminal (if you're using a different termination convention). In particular, this encoding is not a complete description of the Turing machine, and so doesn't really encode one particular Turing machine. Perhaps they forgot something somewhere? Or maybe there is some other convention explaining this? Unless you understand how the encoding describes $M$, you cannot solve the question. – Yuval Filmus Nov 12 '13 at 23:40
• I think that $M$ as a Turing machine here is defined as $M = < Q, \{0, 1\}, \{0, 1, B\},\delta,q_1,B,\{q_2\} >$ (updated above) for this question. However it still seems rather arbitrary to me so I'm not sure if this answers the question of which states are accepting and which are rejecting. – rsxjan Nov 12 '13 at 23:49