Q165: Encoding of a TM

Posted on by bytesoftheday

Question 165: Suppose one transition of Turing machine

Encoding_TM_2

for some integers i, j, k, l and m is encoded in binary form as 0i 1 0j 1 0k 1 0l 1 0m. Here, X1 denotes 0, X2 denotes 1 for binary alphabet. Regarding direction, D1 = L and D2 = R. And, the code for entire TM M consists of all of the codes for the transitions C1, C2, … , Cn in some order separated by pairs of 1’s:

C1 1 1 C2 1 1 . . . . Cn-1 1 1 Cn

What will be the encoding of the following Turing machine as per above technique:

Encoding_TM_1

Options:

  1. 0101000101001100010101001001100010010010100110001000100010010
  2. 01001000101001100010101001001100010010010100110001000100010010
  3. 010010001010011000101010010011000100100101001110001000100101010
  4. 01001101001100010101001001100010010010100110001000100010010

Solution: The correct answer is the second one. The first transition is “0100100010100”, second transition is “0001010100100”, third transition is “00010010010100” and fourth is “0001000100010010”. They are all separated by “11”.