Практическая работа №4 Количество часов, отводимых на выполнение практической работы 2ч
Тема:Решение задач по теме «Машины Тьюринга»
Цель:наработка навыка конструирования машин Тьюринга и применения машин к словам.
Общие теоретические сведения:
Машина Тьюринга включает в себя:
1. Внешний алфавит - конечное множество символов 
. В этом алфавите в виде слова кодируется та информация, которая подается в машину. Машина перерабатывает информацию, поданную в виде слова, в новое слово. Обычно символ Внешний алфавит - конечное множество символов 
обозначает пробел.
2. Внутренний алфавит - конечное множество символов 
. Для любой машины число состояний фиксировано. Два состояния имеют особое назначение 
- начальное состояние машины, 
- заключительное состояние (стоп-состояние).
3. Операторы перемещения Т={Л, П, Н}. Л, П, Н – это символы сдвига «влево», «вправо» и «на месте».
4. Бесконечная лента Бесконечная лента характеризует память машины. Она разбита на клеточки. В каждую клеточку может быть записан только один символ из внешнего алфавита.
5. Управляющая головка. Управляющая головка (УГ) передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т. е. считывать символ
6. Управляющая головка. Управляющая головка (УГ) передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т. е. считывать символ.
7. Работа машины Тьюринга:
8. Информация, хранящаяся на ленте, является набором символов из внешнего алфавита. Начальное состояние управляющей головки характеризуется символом внутреннего алфавита . Работа машины складывается из тактов. В течение любого такта машина Тьюринга осуществляет следующие действия: машина Тьюринга находится во внутреннем состоянии 
, считывает входной символ 
и по таблице работы совершает операцию сдвига 
, переходя в состояние 
, при этом входное слово заменяется на 
:
9. 
10. Если в результате операции машина перейдет в состояние , то работа машины останавливается. Если состояние недостижимо, то значит по данному входному слову машина Тьюринга не достигает конечного состояния и алгоритма для данного входного слова не существует.
Задание на практическую работу:
Вариант №1
ВАРИАНТ 2
Технология работы:
Задание №1
Выбрать тестовое слово, подходящее к условия данной задачи.
Составить алгорит по которому данное слов преобразуется в желаемое.
Составить порограмму машины тьюрига.
Проверить правильность составления машины на контрольном слове
Ззадание №2
Данное слово разместить на ленте, установить УГ в указанное место. Поэтапно выполнять программу машины исходя из правил.
Контрольные вопросы:
1. Необходимость уточнения понятия алгоритма.
2. Машина Тьюринга.
3. Машина Тьюринга и современные ЭВМ.
4. Основная гипотеза теории алгоритмов (тезис Тьюринга).
5. Операции над машинами Тьюринга..
6. Вычислимость функций на машине Тьюринга.
7. Теорема Поста.
8. Алгебраически неразрешимые проблемы.
9. Неразрешимость проблемы самоприменимости.
10. Понятие сложности вычисления.
Список рекомендуемой литературы
1. Математическая логика и теория алгоритмов : учеб. пособие для студ. высш. учеб. заведений / В. И. Игошин. — 2-е изд., стер. — М. : Издательский центр «Академия», 2008. — 448 с.
- Тишин В. В. Дискретная математика в примерах и задачах. — СПб.: БХВ-Петербург, 2008. — 352 с: ил. — (Учебная литература для вузов)