Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

185 Выяснить , применимы ли следующие машины Тьюринга к заданным словам . 1) q 0 0q 2 0R q 0 1q 0 1R q 2 0q 3 0R q 2 1q 2 1L q 3 0q*0S q 3 1q 2 1R P 1 =1110111=1 3 01 3 , P 2 =10[01] 2 1; 2) q 0 0q 2 1R q 0 1q 3 0R q 2 0q 3 1L q 2 1q 2 1S q 3 1q 0 1S P 1 =1 3 01 2 , P 2 =1 6 ; 3) q 0 0q 0 1R q 0 1q 2 0R q 2 0q 0 1R q 2 1q 3 1L q 3 0q 0 1L P 1 =101 2 , P 2 =1 2 0 2 1. 40. Построить в алфавите { 0,1 } машину Тьюринга с пяти - символьными командами , обладающую следующим свойством : 1) машина применима к любому непустому слову в алфавите { 0,1 }; 2) машина неприменима ни к какому непустому слову в алфавите { 0,1 } и зона работы на каждом слове - бесконечная ; 3) машина неприменима ни к какому непустому слову в алфавите { 0,1 } и зона работы на каждом слове ограничена одним и тем же числом ячеек , не зависящим от выбранного слова ; 4) машина применима к словам вида 1 3n , n ≥ 1, и неприменима к словам вида 1 3n+a , n ≥ 1 , а =1,2. 41. Построить в алфавите { 0,1 } машину Тьюринга с пяти - символьными командами , переводящую конфигурацию К 0 в К *. 1) К 0 = q 0 1 n К *= q*1 n 01 n (n ≥ 1); 2) К 0 = q 0 0 n 1 n К *= q*[01] (n ≥ 1); 3) К 0 = 1 n q 0 0 К *= q*1 2n (n ≥ 1). 42. Машину Тьюринга можно задать с помощью следующей таблицы : q 0 q 1 q i q n S 0 S 1