Информатика ← ЛабораторныеЛабораторная работа №5

Программирование машин Тьюринга

Задание

Составить программу в четвёрках для машины Тьюринга выполнения заданного действия. Отладку и тестирование проводить в среде интерактивного действующего макета tu4. Алфавит МТ определяется заданием. Использование дополнительных несобственных букв (кроме λ) нежелательно и должно быть обосновано.

В начальном состоянии головка МТ находится на пустой ячейке непосредственно справа от записанных на ленте аргументов. В конечном состоянии головка МТ должна находиться на пустой ячейке непосредственно справа от результата (последнего преобразованного или вновь сгенерированного слова).

Вычисления в программе, как правило, должны быть нормированными (аргументы после работы программы сохраняются на ленте в неизменном виде и не остаётся промежуточных результатов); ненормированные вычисления, особенно в простых случаях, считаются недочётом и являются достаточным основанием для снижения оценки.

Перед составлением алгоритма для машины Тьюринга необходимо подготовить тесты для него — представительный набор различных входных сообщений, для которых известен правильный ответ, включая значения на границах области определения вычислимой функции и за её пределами. В отчёте по данной работе необходимо привести диаграмму Тьюринга, эквивалентную реализованной программе.

Варианты заданий

(Звездочками помечены более трудные задачи.)

  1. Вычисление поразрядной конъюнкции двух двоичных чисел.
  2. Вычисление поразрядной дизъюнкции двух двоичных чисел.
  3. Обмен местами двух двоичных чисел.
  4. Нормированное вычисление суммы двух двоичных чисел без знака.
  5. **Задача 4 с логарифмической сложностью.
  6. Генерация двух чисел из четных и нечетных разрядов двоичного числа.
  7. *Генерация двух чисел из разрядов двоичного числа, находящихся на четных и нечетных позициях.
  8. Обмен местами разрядов двоичного числа, находящихся на четных и нечетных позициях.
  9. Зеркальное отражение цифр двоичного числа относительно его середины.
  10. Вычисление логического произведения (&& в Си) двоичных чисел.
  11. *Вычисление наибольшего общего делителя двух чисел в натуральной системе счисления.
  12. *Вычисление наименьшего общего кратного двух чисел в натуральной системе счисления.
  13. *Проверка делимости на три.
  14. Вычисление двоичного логического сдвига второго числа влево на число разрядов, равное первому.
  15. Вычисление двоичного логического сдвига первого числа вправо на число разрядов, равное второму.
  16. *Вычисление двоичного арифметического сдвига второго числа влево на число разрядов, равное первому.
  17. *Вычисление двоичного арифметического сдвига первого числа вправо на число разрядов, равное второму.
  18. *Вычисление двоичного циклического сдвига второго числа влево на число разрядов, равное первому.
  19. *Вычисление двоичного циклического сдвига первого числа вправо на число разрядов, равное второму.
  20. *Выделение разрядов первого двоичного числа по маске. Заданной вторым числом.
  21. *Выделение разрядов второго двоичного числа по маске, заданной первым числом.
  22. Закодировать двоичное число азбукой Морзе.
  23. *Умножение двух чисел в кардинальной системе счисления {|}.
  24. Кодирование числа в римской записи по Цезарю (в алфавите {I, V, X, L, C, D, M}).
  25. Умножение однозначных чисел в усеченной римской системе счисления.
  26. *Проверить палиндромию двоичного числа.
  27. *Вычисление двоичного логарифма двоичного числа.
  28. Натурализация двоичного числа в позиционной записи (перевод в натуральную систему счисления {|}).
  29. **Двоичное сложение двоичного и четверичного числа.
  30. Восстановление целого числа в восьмеричной системе счисления по обратному коду.
  31. Восстановление целого числа в восьмеричной системе счисления по дополнительному коду.
  32. Уменьшение на единицу целого неотрицательного числа в восьмеричной системе счисления.
  33. Увеличение на единицу целого неотрицательного числа в восьмеричной системе счисления.
  34. Получение двоичного числа, противоположного данному, в обратной кодировке.
  35. Получение двоичного числа, противоположного данному, в дополнительной кодировке.
  36. *Вычисление разности двух двоичных чисел без знака, при условии, что первое число больше второго.
  37. **Задача 36 с логарифмической сложностью.
  38. *Задача 36, ответ — модуль разности.
  39. **Задача 37, ответ — модуль разности.
  40. Копирование троичного числа со знаком.
  41. Реверс троичного числа со знаком (запись цифр в обратном порядке).
  42. *Зеркальное отражение двух двоичных слов относительно промежутка между ними.
  43. Перевод числа из двоичной системы счисления в восьмеричную.
  44. Перевод числа из восьмеричной системы счисления в двоичную.
  45. Перевод числа из троичной системы счисления в девятеричную.
  46. Перевод числа из девятеричной системы счсиления в троичную.
  47. *Перевод числа из двоичной системы счисления в восьмеричную с логарифмической сложностью.
  48. *Перевод числа из восьмеричной системы счисления в двоичную с логарифмической сложностью.
  49. *Перевод числа из троичной системы счисления в девятеричную с логарифмической сложностью.
  50. *Перевод числа из девятеричной системы счисчления в троичную с логарифмической сложностью.
  51. Проверка делимости на 9.
  52. *Проверка делимости на 11.
  53. **Четверичное сложение двоичного и четверичного числа.

Пример: программа ненормированного сложения двоичных чисел без знака с комментариями и со скобками.

(00, ,<,01)             (03,1,<,03)     (05, ,>,00)             (04, ,1,05)           (07, ,#,07) стоп
(01,0,1,02) перенос -1  (03, ,<,04)     (00,1,>,00)             (01, ,>,06)
(02,1,<,01) перенос -1  (04,0,1,05) +1  (00,0,>,00)             (06,1,>,06)
(01,1,0,03) -1          (05,0,>,05)     (04,1,0,02) перенос +1  (06, ,<,07)
(03,0,<,03)             (05,1,>,05)     (02,0,<,04) перенос +1  (07,1, ,06) стирание

Ссылки

  1. Оригинальный текст лабораторной
  2. Веб-интерпретатор МТ
  3. Инструкция к эмулятору МТ tu4 (tu) и пакетной версии интерпретатора МТ (turun)
  4. Логические выражения (конъюнкция и дизъюнкция)