Definition 8.4.1: Let _= {0,1} and consider a Turing machine T = (S, _, _, _, s0, b, R). We can assume that R contains a single state. We define a sequence encode(T)__* that provides a complete description of T as a binary sequence as follows:
• choose a numbering of the states S as
• choose a numbering of the tape symbols _ as <_1, _2, … , _n> where 0 = _1, 1 = _2, b = _3, and encode each tape symbol as its unary number,
• number the directions l as D1 and r as D2,
• encode a transition _(si,_j) = (sp,_q,Dr) as 0i10j10p10q10r,
• encode T as 111code111code211 … 11codek111 where codei (1Š i Š k) are the encoded transitions of T.
Previous slide | Next slide | Back to first slide | View graphic version |