Лабораторная работа №2 "Конструирование Машины Тьюринга"

Цель: закрепить навыки конструирования Машины Тьюринга.

Вид работы: индивидуальный.

Время выполнения: 4 часа.

Теоретические сведения:

Машина Тьюринга состоит из следующих частей:

1. Информационной ленты, представляющей бесконечную память машины. Это бесконечная лента, разделенная на ячейки. В каждой ячейке можно поместить лишь один символ из возможного их множества S={S₁,S₂,….,S_m},которое составляет внешний алфавит МТ. В этом алфавите один из символов (пусть это будет S₁) соответствует пустому символу.

2. Считывающей головки – чувствительного специального элемента, способного обозревать содержимое ячеек. Лента может перемещаться вдоль головки так, что в каждый момент времени головка обозревает одну ячейку.

3. Управляющего устройства (УУ), которое в каждый момент времени находится в некотором состоянии. Число состояний конечно. Обозначим множество состояний как {q₁,q₂,…,q_n}. Среди состояний одно соответствует заключительному, при котором МТ останавливается. УУ связано со считывающей головкой.

Кроме того, УУ вырабатывает три команды на перемещение ленты: П, Л, Н, где

П – переместиться на соседнюю справа ячейку;

Л – переместиться соседнюю слева ячейку;

Н – продолжать обозревать ту же ячейку.

Совокупность символов {q₁,q₂,…,q_n} и {П,Л,Н} образуют внутренний алфавит МТ.

Работа машины происходит в дискретном времени. В начальный момент времени в ограниченный участок ленты записано слово в алфавите S, представляющее исходное условие задачи. В остальных ячейках предполагается записанным пустой символ. Управляющее устройство находится в начальном состоянии q₁. На каждом шаге работы МТ обозревает на ленте символ S_k и в зависимости от него и от состояния q_i, переходит в состояние q_j, заменяет S_k на символ S_l и передвигает ленту (либо нет) на одну ячейку.

Каждая элементарная операция имеет вид

q_iS_k  q_jS_l П(Л,Н).

Множество элементарных операций упорядочено и образует абстрактную программу, которая представляет алгоритм.

Считывающая головка и управляющее устройство образуют логический блок, который представляет собой (2,3)-полюсник.

Конструирование Машины Тьюринга включает в себя следующие 2 этапа:

1. Словесное описание алгоритма решения задачи.

2. Перевод описания алгоритма на язык машины Тьюринга.

Ход работы:

Составить словесный алгоритм и программу для конструирования Машины Тьюринга для конкретной функции.

Задания к работе:

Вариант №1. F(x)=x+3

Вариант №2. F(x)=x -1

Вариант №3. F(x)=x -2

Вариант №4. F(x)=x+4

Вариант №5. F(x)=x -4

Вариант №6. F(x)=x+5

Вариант №7. F(x)=x -5

Вариант №8. F(x)=x+2

Вариант №9. F(x)=x -3

Вариант №10. F(x)=x+6

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

1. Опишите состав машины Тьюринга.

2. Опишите схему работы машины Тьюринга.

3. Перечислите этапы конструирования машины Тьюринга.

Рекомендуемая литература: 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.8, 2.3, 2.4, 2.5.

Лабораторная работа №3 "Вычислимые по Тьюрингу функции"

Цель: отработать навыки конструирования машины Тьюринга и определения вычислимых по Тьюрингу функций.

Вид работы: индивидуальный.

Время выполнения: 4 часа.