Машина Тьюринга задается следующей функциональной схемой

Запишем последовательность конфигураций:
111*11q11→111*1q21a0→111*q211a0→111q2*11a0→11q21*11a0
→1q211*11a0→q2111*11a0→q2a0111*11a0→1q3111*11a0
→11q311*11a0→111q31*11a0→1111q3*11a0→1111*q311a0
→1111*1q31a0→1111*11q3a0→1111*1q11a0→1111*q21a0a0
→1111q2*1a0a0→111q21*1a0a0→11q211*1a0a0→1q2111*1a0a0
→q21111*1a0a0→q2a01111*1a0a0→1q31111*1a0a0→11q3111*1a0a0
→111q311*1a0a0→111q311*1a0a0→1111q31*1a0a0→11111q3*1a0a0
→11111*q31a0a0→11111*1q3a0a0→11111*q11a0a0→11111q2*a0a0a0
→1111q21*a0a0a0→111q211*a0a0a0→11q2111*a0a0a0→1q21111*a0a0a0
→q211111*a0a0a0→1q311111*a0a0a0→11q31111*a0a0a0
→111q3111*a0a0a0→1111q311*a0a0a0→11111q31*a0a0a0→111111q3*a0a0a0
→111111*q3a0a0a0→111111q1*a0a0a0→111111q0 a0a0a0a0
в) 111*1
Запишем последовательность конфигураций:
111*q11→111q2*a0→11q21*a0→1q211*a0→q2111*a0→q2a0111*a0
→1q3111*a0→11q311*a0→111q31*a0→1111q3*a0→1111*q3a0
→1111q1*a0→1111q0a0a0
ж) *1111
Запишем последовательность конфигураций:
*111q11→*11q21a0→*1q211a0→*q2111a0→ q2*111a0→ q2a0*111a0
→1q3*111a0→1*q3111a0→1*1q311a0→1*11q31a0→1*111q3a0
→1*11 q11a0→1*1q21a0a0→1*q211a0a0→1q2*11a0a0→ q21*11a0a0
→ q2a01*11a0a0→1q31*11a0a0→11q3*11a0a0→11*q311a0a0→11*1q31a0a0
→11*11q3a0a0→11*1q11a0a0→11*q21a0a0a0→11q2*1a0a0a0
→1q21*1a0a0a0→ q211*1a0a0a0→q2a011*1a0a0a0→1q311*1a0a0a0
→11q31*1a0a0a0→111q3*1a0a0a0→111*q31a0a0a0→111*1q3a0a0a0
→111*q11a0a0a0→111q2*a0a0a0a0→11q21*a0a0a0a0→1q211*a0a0a0a0
→ q2111*a0a0a0a0→ q2a0111*a0a0a0a0→1q3111*a0a0a0a0
→11q311*a0a0a0a0→111q31*a0a0a0a0→1111q3*a0a0a0a0 a0a0a0a0
→1111*q3a0a0a0a0→1111q1*a0a0a0a0→1111q0a0a0a0a0a0