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

30. Составить команды машины Тьюринга, которая будет считать записанные подряд (без пропусков) палочки и запишет их число: 1) в двоичной системе счисления; 2) в троичной системе счисления; 3) в системе счисления с основанием п. 31. На ленте записано число в системе счисления с основанием п. Составить команды машины Тьюринга, которая запишет число 1) непосредственно следующее за данным; 2) непосредственно предшествуюш,ее денному. 32. На ленте записано некоторое число слов Pi,P2,...,Pk в алфавите А, разделенных звездочками (* *0А). Составить команды машины Тьюринга, которая считала бы количество слов и записывала бы их число: 1) в алфавите {1}] 2) в двоичной системе счисления; 3) в троичной системе счисления; 4) в системе счисления с основанием п. 33. Построить машину Тьюринга, которая приписывала бы справа от любого с л о в а в алфавите^ слово aab(a,beA). 34. Выяснить в какое слово перерабатывается слово т * г машиной Тьюринга: qolsoqo qi*rqi q2*lq2 qosorqi qisolq2 q2sorqo qilRqi q2lLq2. (начальной конфигурацией является конфигурация qom*n). 35. Построить машину Тьюринга для умножения на 2. 36. Построить машину Тьюринга для вычисления целой части частного при делении на 3. 37. Построить машину Тьюринга для вычисления | х-у \. 38. На ленте записано некоторое число палочек (без пропусков). Составить команды машины Тьюринга, которая стирает каждую третью палочку, двигаясь слева направо, стирает каждую третью палочку из оставшихся и т.д. При этом машина должна указать последнюю стираемую палочку. 39. Машины Тьюринга, заданные с помош,ью команд вида qisjsi(cif qisjr qr qisjl q^, можно задать с помош,ью пятисимвольных команд вида qisjqrsjcq, объединяющей две команды qiSj-Skq^ и qmSkQ q^ где Q=R, Q=L или Q=S; при Q=S читающая головка не передвигается ни влево и ни вправо. 184