Математическая логика и теория алгоритмов

3) Q'oOq'oli? qolqiOR q20qQlR q^OqalL P2=lVl. 40. Построить в алфавите {0,1} машину Тьюринга с пятисим- вольными командами, обладающую следующим свойством: 1) машина применима к любому непустому слову в алфавите {0,1}; 2) машина не применима ни к какому непустому слову в алфа­ вите {0,1} и зона работы на каждом слове - бесконечная; 3) машина не применима ни к какому непустому слову в алфа­ вите {0,1} и зона работы на каждом слове ограничена одним и тем же числом ячеек, не зависящим от выбранного слова; 4) машина применима к словам ввда 1^", и>1, и не применима словам вида «>], д=1,2, 41. Построить в алфавите {0,1} машину Тьюринга с пятисим- вольными командами, переводящую конфигурацию Ко в К*: 1) i^o = ?ol" ;^*=?*1"01" {п>\у, 2) K, = q,Q"l" K*"=q*[Q\] ("SI); 3) i^o =i > 0 K*=^q*\^" (и^,1). 42. Машину Тьюринга можно задать с помощью следующей таблицы: Яо 9i So S^ Si gAQ Sn, 274