5 (Лабораторная работа №5)

Лабо ато иан абота 14я б по ии матике; 8 ак льгот 1 к с 1 семест 2007708 чебного го а Программирование машин Тьюринга Составить программу лля машины Тьюринга в четверках выполнения задазпюго действия. Отладку и тестирование программы проводичь в среде интерактивного действующего макета Зп4.

Алфавит МТ определяется заданием Использование дополнительных несобственных букв (кроме 2) нежелательно и должно быль обосновано В начальном состоянии головка МТ находится на пустой ячейке непосредственно справа от запнсазппях на ленте аргументов. В коне пюм состоянии головка МТ должна находиться на пустой ячейке непосредствешю справа от результата (последнего преобразоватпюга или вновь сфорьзнров иного слова) Вычисления в программе, как правила, лолзкны быть нормированньвпч !аргументы паоле рабаты программы сохранюотся на лепте в неизменном виде и не остается промежуточшлх результатов); иенормировшнпяе вычисления, особешю в просп зх случаях.

считаются недочетом и являются дастато пплм основшлгем для снижения оценки. Перел составлением ачгоритма лля маплпшз Тьюринга необходимо подготовить тесты для него — прелставительный набор различных входных сооббщеций, лля которых известен правичьньй ответ, вкчючая значения па границах области определения вычислимой фучлаии и за ее пределами В отчете по данной работе необходимо привести диаграмму Тьюринга, эквивалентную реализованной программе № Действие (звездочкаьзи помечены более трудные задачи) 1 Кодирование числа в римской записи по Цезарю (в алфавите !1, У, Х, 1,, С, П, М) ) 2 Умножение однозначных чисел в усеченной римской системе счисления 3* Проверить палиндромию двоичного числа 4* Вычисление двоичного логарифма двоичного числа. 5 Натурализация двоичного числа в позициозпюй записи (перевод в натуральную систему счисления Я).

бее Задание 5 с логарифмической сложностью 7 Восстановление целого числа в восьмеричной системе счисления по обратному коду 8 Восстановление целого числа в восьмеричной системе счисления по дополнительному казб 9 Уменьшение на единицу целога неотрицательного числа в восьмеричной системе счисления 10 Увеличение на едзпппзу целого неотрицательного числа в восьмеричной системе счисления 11 Получение двоичного числа, противоположного данному, в обратной кодировке.

12 Получение двоичного числа, противоположного лингаму, в лополннтельной кодировке. 13* Вычислезие разности двух двоичных чисел без знака, при условии, что первое число больше второго. 14" Задача 13 с логарифмической сложностью 15" Задача 13, ответ — модуль разности 1бее Задача 14, ответ — модуль разности 17 Копирование трои пюго числа со знаком. 18 Реверс троичпого числа со знаком (запись цифр в обратном порядке). 19' Зеркальное отражение двух двоичных слов относительно промежутка мевау пизнз. 20 Перевод числа из двоичной системы счисления в восьмеричную.

21 Перевод числа из восьмеричной системы счисления в двоичную. 22 Перевод числа из трои пчой системы счисления в девятеричную 23 Перевод числа из девятеричной системы с нюлепия в троичную. 24" Перевод числа из двоичной системы счисления в восьмери пзую с логарифмической сложпостыа. 25е Перевод числа из восьмеричной системы счисления в двоичн~ю с логарифмической сложностью. 26' Перевод числа из чроичной системы счисления в девячеричнута с логарифмической сложностью. 27* Перевод числа из деви еричпой системы счисления в троичную с логарифмической сло)кносчч,ю.

28 Вычисление двоичного логического слвиз а второго числа влево на число разрядов, равное первому. 29 Вычисление двоичного логического сдаю а первого числа вправо на число разрядов, равное второьш. 30' Вычислегие двоичного арифметического сдвига второго числа влево на число разрядов, равное первому. 31' Вы пзслезие двоичного арифметического сдвига первого числа вправо на число разрядов, равное второму. 32е Вычисление двоичного циклического сдвиг а второго числа влево на число разрядов, равное первому. 33* Вычислсгие двоичного циклического едина первого числа вправо на число разрядов, равное второму. 34в* Выделение разрядов первого двоичного числа по маске, задагнюй вгорым числом 35'* Выделение разрядов второго двоичного числа по маске, заданной первым числом.

36' Вычисление поразрядной кокьюнкпии двух двоичных чисел. 37" Вычисление поразрядной дизъюнкции двух двоичных чисел. 38"* Обмен мествмв двух двоичгплх чисел 39 Нормированное вычисление суммы лвух лвоичных чисел без знака.

40" е Залача 39 с логарифмической слакнаспла. 41 Генерация двух чисел из четных и нечетных разрядов лвоичного числа. 42* Генерация лвух чисел из разрядов двоичного числа, пахолящихся на четных н нечецллх позициях. 43 Обмен местами четных и нечетных разрядов дюи пюго числа.

44 Зеркальное отражение цифр двоичного числа относительно его серелюпя 45 Вы пюление логического праизведешьч ( йй в Си) двоичных чисел. 46**" Вычисление нанболыпего общего делителя двух исел в натуральной системе счисления. 47ее Вычисление наименьшего общего крапюго двух чисел в натуральной системе счисления. 48 Закодировать двоичное число азбукой Морзе.

49"* Умножение двух чисел в кардинальной шютсме счисления Я. Пример: программа иелврмирвввннигв сложения двоичных чисел без знака с коммеитврвялвз я ео екабкиззи 100,, <, 01) (03, 1, <, 03) 105,, >, 00) (04, , 2, 05) (07. . . 07) стоп 101, О, 1, 02) перенос-! (03,, <, 04) (00, 1, >, 00) (О1,, >, 06) (02, 1, <, О1) перенос! (04 0 1 05) . 1 (00, О, >, 00) 106,1,>,06) (01, 1, О, 03) -1 (05 0 ь 05) (04, 1, О, 02) перенос -1 (03,0,<,03) (05, 1, >, 05) 102, О, <, 04) перенос 1 107, 1,, 06) старание Варианты заданий составлены проф.

Зайцевым В.Е., ст. преть Сенипким П.А., Псрстягиным И А. и доц. Сошниковым Д.В. Краткое описание действующего макета машины Тьюринга Кегп гп Интерактивный полноэкранный макет машины Тьюринга !п4 реашззован на ЭВМ ВЕС (Со!враг!, НР) РОР-11, ЪгАХ-11, А1рйа в среде ГДн)1Х с терминалами ЪТ-1ххг2ххгбххг4ххг5хх. Запуск макета осуществляется из игнсрпретатора команд 13)нг)Х: ги4или файла с ггрограымог).ггг Макет реализует следующий вариант определенна МТ: ° по!па МТ теоретически бесконечна только в один !правый) конец; ° программа МТ сосюгп из четверок <г),а,у,г)'> где г) - старое состояние, а - обозреваемая буква, у — символ действия: записываемая буква или команда перемещения, г)' - новое состояние; ° поддерживаются следующие команды перемещения: > - сдвиг иа одну ячейку вправо ( знак > реализует символ движения вправо на одну ячейку г ); < - сдвиг на одну ячейку влево ( знак < реализует символ движения влево на одну ячейку 1): = - сохранение текущего положения; гг - останов макетной МТ (классическая комакда осталова (г).

а, а, г)) также реализована). Ограничения реализации для текстовых терминалов 80х24: объем программы — до 168 команд, длина активного у габт!си ленты — 80 ячеек. С программами более чем пз 168 команд необходимо работать в окне текстового терминала на графическом мониторе в среде Х зу'1пг)отк буиепз, При этом перед вызовом гп4 необходимо соответствующим образом увеличить размеры окна тексгового терминала и уменьшить (в особо тяжелых случаях) размер шрифта в этом окне. Для коррскпюго отображения русских букв вмссго гн4 вызывается гн4-1яо8859-5. При использовании разрешения экрана текстового терминала отличного от 80х24, к примеру, 132х48 необходимо указать соответствующие позиционные параметры 1п4: си4 15п41.

Гы 132 48. Программы МТ хранятся в текстовых файлах с расширением Лн и кодируются по следующим правилам: состояния МТ обозначаются двузначными не отрицшельными шестнадцатеричными числами (от 00 до РР). МТ всегда начинает работать с нулевого состояния; ° буквы рабочего алфавита выбираются нз знаков. имеющихся на клавиатуре, за исключением знаков < > = гг, изображающих символы действия МТ. Несобсгиенная буква 1 кодируется пробелом; каждая команда располагается в отдельной строке, начиная с 1-й позиции. Компоненты команды разделяются запятыми.

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

у)пг....) со си!рог!зги собзлкзсгпяпньз ггзодззатп. Во время работы макета экран дисплея имеет слелуюцпю структуру: ° в верхней строке отображается текущее состояние ленты МТ; ° в третьей строке содержится подсказка но горячим клавишам макета; в остальных строках отображается ~скет программы МТ. Макет предоставляет пользователю след)ющие возможности: ° пошаговая интерпретация команд программы; быстрая интерпретация команд без остановок; ° редактирование программы МТ, в том числе, интерактивное создание новой программы.

Макет поддерживает след)чощис горячие клавиши: ° переход к пошаговой июерпрегации программы <пробел> (на ПЕС А!рЬа переход к пошаговому выполнению из режима быстрой интерпретации происходит с некоторой инерцией) ° переход к быстрой интерпретации программы ° прекращение интерпретации и переход к редактированию. а также запись редакгируемой программы на диск ТаЬ ° прекращение работы макета Сгг! 1 С Пример программы МТ: оо, , †,оо оо,г,у,оо 00, †,ч,оо 00,/, ,01 00,1,1,00 01, ,>,00 Для протоколирования работы МТ необходимо текст отлаженной программы поместить в файл 15.ги, а тесты к ней — в файл 15.гяг, и в режиме протоколирования вызвать пакетную версию интерпретатора МТ гн11р.