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

Выяснить, применимы ли следующие машины Тьюринга к заданным словам. 1) qoOq20R qolqolr q20q30r q2lq2ll qsOq^OS q3lq2lR Pi=1110111=1^0l\ P2=10[0lfl; 2) qoOq2lR qolqsOR qioqsll q2lq2ls qjlqolS P, = l'Ol\ P2=l': 3) qoOqolR qoiqiOR qiOqolR q2lq3ll qsOqolL Pi=10l\ P2=1^0^1. 40. Построить в алфавите {0,1} машину Тьюринга с няти-символьными командами, обладающую следующим свойством: 1) машина применима к любому непустому слову в алфавите {0,1}; 2) машина неприменима ни к какому непустому слову в алфавите {0,1} и зона работы на каждом слове - бесконечная; 3) машина неприменима ни к какому непустому слову в алфавите {0,1} и зона работы на каждом слове ограничена одним и тем же числом ячеек, не зависящим от выбранного слова; 4) машина применима к словам вида 7^", п>1, и неприменима к словам вида п>1,а=1,2. 41. Построить в алфавите {0,1} машину Тьюринга с пяти-символьными командами, переводящую конфигурацию Ко в \)Ko = qor K''=q''ror (п>1); 2)Ko = qoO''r K^=q^[01] (п>1); 3) Ко = rqoO 7^*= g*7^" (п>1). 42. Машину Тьюринга можно задать с помощью следующей таблицы: qo qi qn So Si 185