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

184 30. Составить команды машины Тьюринга , которая будет считать записанные подряд ( без пропусков ) палочки и запишет их число : 1) в двоичной системе счисления ; 2) в троичной системе счисления ; 3) в системе счисления с основанием п . 31. На ленте записано число в системе счисления с основанием п . Составить команды машины Тьюринга , которая запишет число 1) непосредственно следующее за данным ; 2) непосредственно предшествующее денному . 32. На ленте записано некоторое число слов Р 1 , Р 2 ,…, Р k в алфавите А , разделенных звездочками ( ∗ , ∗∉ А ) . Составить команды машины Тьюринга , которая считала бы количество слов и записывала бы их число : 1) в алфавите { 1 } ; 2) в двоичной системе счисления ; 3) в троичной системе счисления ; 4) в системе счисления с основанием п . 33. Построить машину Тьюринга , которая приписывала бы справа от любого слова Р в алфавите А слово aab(a,b ∈ A) . 34. Выяснить в какое слово перерабатывается слово rm ∗ машиной Тьюринга : q 0 1S 0 q 0 q 1 ∗ Rq 1 q 2 ∗ Lq 2 q 0 S 0 Rq 1 q 1 S 0 1q 2 q 2 S 0 Rq 0 q 1 1Rq 1 q 2 1Lq 2 . ( начальной конфигурацией является конфигурация q 0 nm ∗ ). 35. Построить машину Тьюринга для умножения на 2 . 36. Построить машину Тьюринга для вычисления целой части частного при делении на 3 . 37. Построить машину Тьюринга для вычисления  x-y  . 38. На ленте записано некоторое число палочек ( без пропусков ). Составить команды машины Тьюринга , которая стирает каждую третью палочку , двигаясь слева направо , стирает каждую третью палочку из оставшихся и т . д . При этом машина должна указать последнюю стираемую палочку . 39. Машины Тьюринга , заданные с помощью команд вида q i S j S k q r q i S j R q r q i S j L q r , можно задать с помощью пятисимвольных команд вида q i S j q r S k Q, объединяющей две команды q i S j S k q m и q m S k Q q r , где Q=R, Q=L или Q=S; при Q=S читающая головка не передвигается ни влево и ни вправо .