ПомощьЭмулятор машины Тьюринга tu

Краткое описание действующего макета машины Тьюринга tu

Интерактивный полноэкранный макет машины Тьюринга tu реализован на ЭВМ DEC (Compaq, HP) PDP-11, VAX-11, Alpha в среде HP True64 UNIX или Free/NetBSD с терминалами VT-1xx/2xx/3xx/4xx/5xx. Запуск макета осуществляется из интерпретатора команд UNIX:

  tu имя_файла_с_программой.tu

Макет реализует следующий вариант определения МТ:

  • лента МТ «бесконечна» только в однин (правый) конец;
  • программа МТ состоит из четверок , где q — символ старого состояния, а — обозреваемая буква, v — символ действия: записываемая буква или команда перемещения, q' — символ нового состояния;
  • поддерживаются следующие команды перемещения:

    • > — сдвиг на одну ячейку вправо (знак > реализует символ движения вправо на одну ячейку r);
    • < — сдвиг на одну ячейку влево (знак < реализует символ движения вправо на одну ячейку l);
    • = — сохранение текущего положения;
    • # — останов макетной МТ (классическая команда останова (q, a, a, q) также реализована).

    Ограничения реализации для текстовых терминалов 80x24: объем программы — до 168 команд, длина активного терминала на графическом мониторе в среде X Window System. При этом перед вызовом tu необходимо соответствующим образом увеличить размеры окна текстового терминала и уменьшить (в особо тяжелых случаях) размер шрифта в этом окне. Для корректного отображения русских букв на текстовых терминалах вместо tu вызывается tu.koi8r.

Программы МТ хранятся в текстовых файлах с расширением .tu и кодируются по следующим правилам:

  • состояния МТ обозначаются двузначными неотрицательными шестнадцатиричными числами (от 00 до FF). МТ всегда начинает работать с нулевого состояния;
  • буквы рабочего алфавита выбираются из знаков, имеющихся на клавиатуре, за исключением знаков <, >, =, #, изображающих символы действия МТ. Несобственная буква λ кодируется пробелом;
  • каждая команда располагается в отдельной строке, начиная с 1-й позиции. Компоненты команды разделяются замятыми. В команде не должно быть пробелов, кроме тех, которые имеют смысл пустых ячеек ленты МТ;
  • в тексте программы не должно быть пустых строк.

Вводить и редактировать текст программы МТ рекомендуется с помощью самого интерпретатора МТ, в котором для этого имеются все необходимые средства; переход в режим редактирования: автоматически при ошибке в программе, по Tab в процессе выполнения программы и по Return в других случаях. Поскольку программа МТ является текстовым файлом, она также может быть набрана в любом редакторе текстов (emacs, ted, vim, ...) со строгим соблюдением формата.

Во время работы маекта экран дисплея имеет следующую структуру:

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

Макет предоставляет пользователю следующие возможности:

  • пошаговая интерпретация команд программы;
  • быстрая интерпретация команд без остановок;
  • редактирование программы МТ, в том числе, интерактивное создание новой программы.

Макет поддерживает следующие горячие клавиши:

  • переход к пошаговой интерпретации программы <пробел>
  • переход к быстрой интерпретации программы
  • прекращение интерпретации и переход к редактированию, а также запись редактируемой программы на диск
  • прекращение работы макета Ctrl+C

Пример программы МТ:

  00, ,-,00  00,|,/,00
  00,-,\,00  00,/, ,01
  00,\,|,00  01, ,>,00

Для протоколирования работы МТ необходимо текст отлаженной программы поместить в файл типа tu, например с именем l5.tu, а входные данные к ней — в файл l5.tst, и в режиме протоколирования вызвать пакетную версию интерпретатора МТ turun:

  tulip имя-файла.tu имя-файла-с-тестами.tst

Макет МТ разработан в 1987 году студеном Лукашевичем С. Ю. Описание подготовлено проф. Зайцевым В. Е., доц. Журавлевой Т. Э. и ст. преп. Сеницким П. А. на основе курсовой работы Лукашевича С. Ю. и одного из Этюдов для программистов Ч. Уэзерелла. — М.: Мир, 1982. Перенос на DEC Alpha выполнил Сеницкий П. А., модификацию для программ болього размера в окнах X Window System, четверочную и пакетную версии реализовал ст. преп. Лебедев А. В. Примеры переработаны ст. преп. Перетягиным И. А., студ. Марухиным А. В. и др.

Для домашних работ могут использоваться другие системы Тьюринговских вычислений в среде MS-DOS и Windows: tu05m; здесь реализованы и четверки, большие номера состояний!, DDT, мультимодельная система Рыбакова К. А., программа Семенова А. В. («4», на MS Visual Basic 6.0!). В среде UNIX для Alpha есть и пятерочная версия макета (tu5 и tutu). Есть версия tu4 для FreeBSD (выполнимый файл, кодировка сообщений KOI8-R), а также для Linux (Intel).