Адание на лабораторную работу

Необходимо написать программу для машины Тьюринга, реализующую вычисление арифметической функции согласно выданному варианту задания. Должна быть составлена совокупность команд P. Для выполнения данного задания следует использовать приложение Algo2000.

Аргументы задаются набором ”1”. Пример 2*3, будет выглядеть следующим образом 11*111.

Работа машины Тьюринга должна начинаться со стандартной начальной конфигурации и заканчиваться стандартной конечной конфигурацией.

Рассмотрим пример для функции .

Рисунок 2. Программа для МТ в Algo2000

На рисунке 2 представлено окно приложения Algo2000 с программой для машины Тьюринга, реализующей вычисление функции .

Формат команды применяемый в Algo2000

,

где:

— символ который будет записан в обозреваемую ячейку,

— направление сдвига{<,>},

— состояние в которое перейдет МТ.

Во второй части лабораторной работы требуется создать программу на языке высокого уровня имитирующую работу машины Тьюринга.

3. Требования к программе:

· входная лента машины Тьюринга должна считываться из файла;

· программа для машины Тьюринга должна считываться из файла;

· алфавит должен считываться из файла;

· результат работы программы должен выводиться в файл;

· результат должен содержать следующие элементы:

o состояние ленты перед выполнением каждой команды;

o указание положения головки на ленте;

o выполненную команду;

o пример:

— состояние ленты перед выполнением команды;

^ — положение головки на ленте;

— выполняемая команда;

— состояние ленты перед выполнением команды;

^ —положение головки на ленте.

· в программе должен быть реализован контроль возможных ошибок машины Тьюринга (не задан переход, отсутствует символ в алфавите и др.).

4. Требования к входным данным:

· Совокупность команд:

o Формат записи команд определяется согласно форме (1) (см. выше);

o Каждая команда на отдельной строке.

· Алфавит:

o Символы внешнего алфавита, перечислены в файле через пробел.

одержание отчета

· Цель работы

· Основные сведения из теории

· Постановка задачи

· Совокупность команд для машины Тьюринга

· Листинг программы на языке высокого уровня с комментариями

· Пример результата выполнения

· Вывод

6. Контрольные вопросы:

· Дать определение

o Символ λ

o Внешний алфавит

o Внутренний алфавит

o Полное состояние

o Стандартная начальная конфигурация

o Стандартная конечная конфигурация

o Машина Тьюринга

· Описать принцип функционирования

· Сопоставить

o внешний алфавит

o перечень команд

o внутренний алфавит

o начальное состояние

· Что означает термин «Машина Тьюринга правильно вычисляет значение вычислимой функции»?

7. Варианты заданий:

Задание на удовлетворительно

Задание на хорошо

Задание на отлично

8. Список литературы по теме работы:

1. Алферова З.В. Теория алгоритмов …(см прикрепленный файл с литературой)

2. Кузнецов О.П., Адельсон-Вельский …(см прикрепленный файл с литературой)

3. Эббинхауз Г. Д., Якобс К., Ман Ф. К. Машины Тьюринга и рекурсивные функции. 1972, - С. 264

4. Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Глава 8. Введение в теорию машин Тьюринга // Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1