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

      Комментарии к записи Адание на лабораторную работу отключены

Необходимо написать программу для машины Тьюринга, реализующую вычисление арифметической функции согласно выданному варианту задания. Должна быть составлена совокупность команд 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

Статьи к прочтению:

Задания к лабораторной работе№1 в GNS3


Похожие статьи: