Упражнения. 1. Применить машину Тьюринга

1. Применить машину Тьюринга

а) 1 2 3 4 5

0 0П2 0П2 1М0 0П4 1Л5

1 1П4 1П2 0Л3 1П4 0М0

– – -Л3 1М0 -Л5 – к слову 0010, 1100

б)

0 0П2 0П2 -Л5 1М0 1П5

1 1ПА 1П2 -Л4 0Л4 0П5

– -М0 -Л3 – – 1М0 к слову 00101, 01000,

2. Построить МТ, которая выполняет вычитание х – 2 для х >2.