Definition 8.1.3: a move of a Turing machineT = (S, _______, s0, b, R) is denoted by a pair of instantaneous descriptions; for IDs I1 and I2 we say I1 leads to I2 in T, I1_| I2, if either
(1) I1 = _1_2 _k-1s_k _n, and either
(a) _(s,_k) = and I2 = _1_2 _k-1Ys'_k+1 _n, or (b) k>1, _(s,_k) = and I2 = _1_2 s'_k-1Y_k+1 _n,
or
(2) I1 = _1_2 _k-1_k _ns, and either
(a) _(s,b) = and I2 = _1_2 _k-1_k _nYs', or
(b) n1, _(s,b) = and I2 = _1_2 _k-1_k s'_nY.
Previous slide | Next slide | Back to first slide | View graphic version |