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

36. Построить машину Тьюринга для вычисления целой части частного при делении на 3. 37. Построить машину Тьюринга для вычисления U-}' 1. 38. На ленте записано некоторое число палочек (без пропусков). Составить команды машины Тьюринга, которая стирает каждую тре­ тью палочку, двигаясь слева направо, стирает каждую третью палочку из оставшихся и т.д. При этом машина должна указать последнюю стираемую палочку. 39. Машины Тьюринга, заданные с помощью команд вида qtSjSkqr qiSjR qr qjSjL (]r, можно задать с помощью пятисимвольных команд вида q,SjqAQ, объединяющих две команды qiSjSkq^ и qmSkQqn где Q-R, Q=L или Q —S; при Q=S читающая головка не передвигается ни влево и ни вправо. Выяснить, применимы ли следующие машины Тьюринга к за­ данным словам: 1) qoOqjOR go^q\lR qjOqsOR qjlqi^L qiOq*OS q^lq^lR 2) qoQqilR qolqsOR qiOqsiL ?2l?2l5' qslqolS P,=1110111=1^01^ P2=10[0lfl; 273