lec15

Кафедра Прикладной математики Института информационных технологий РТУ МИРЭА

Дисциплина

«Математическая логика и теория алгоритмов»

2022-2023 уч.г.

Наполнение курса

2

Лекция 15.

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

15.1.Определение и задание машины Тьюринга.

15.2.Вычисления на Машине Тьюринга.

15.3. Геделевская нумерация.

Пост (1936) и Тьюринг (1937) независимо друг от друга предложили уточнение понятия алгоритма как процесса, который может совершаться подходяще устроенной "машиной". Машины, введенные Постом и Тьюрингом, отличались не очень существенно и в дальнейшем стали называться машинами Тьюринга.

Машина Тьюринга Т – это модель абстрактного вычислителя (исполнителя).

Машина Тьюринга (МТ) задается как пятерка объектов Т={A,Q,F,G,H}. Входной и выходной алфавит: A,

множество состояний: Q, функция выхода: F, функция перехода: G,

функция управления: H, (H={R,L,S}: right, left, stop).

Работа машины Тьюринга.

Имеется бесконечная лента, разделенная на ячейки. В ячейках выписывается пустой символ □ или другая буква алфавита A.

На каждом шаге машина, находящаяся в состоянии q прочитывает входную букву a, переходит в новое состояние q´ согласно функции G, печатает вместо прочитанной буквы a новую букву a´ согласно функции F и реализует управляющее воздействие h (сдвигается вправо, влево или остается на месте) в зависимости от функции H.

!!! Машину Тьюринга нельзя реализовать именно из-за бесконечности ее

ленты. В этом смысле она мощнее любой вычислительной машины.

6

Способы задания машины Тьюринга.

1) Автоматная таблица:

на пересечении i-той строки (аi) и j-того столбца (qj) записывается новая буква аʹ, новое состояние qʹ и управляющий символ h.

2) Программно:

команда машины Тьюринга – запись вида:

aiqj aʹqʹh

Команда описывает работу МТ в один из тактовых моментов времени. Список какого-либо множества команд будем называть программой (или

списком).

!!! Команды не обязательно содержат в левых частях все возможные сочетания (a,q), а только реально встречающиеся в процессе работы.

7

Утверждение 15.1. Головка машины Тьюринга есть конечный автомат. Из описания машины Т следует, что головку машины можно рассматривать как конечный автомат М, у которого А=А, Q=Q, Y=A x {R,L,S}, функции F(a,q), G(a,q) определяются из программы работы машины Тьюринга:

Если команда имеет вид aiqj aʹqʹh, то

F(a,q) = aʹh,

G(a,q) = qʹ.

Утверждение 15.2. Функционирование любого конечного автомата можно смоделировать на машине Тьюринга. Пусть конечный автомат М={A,Q,Y,G,F}.

Утверждение 15.3. Возможности машины Тьюринга больше чем у конечного автомата.

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

8

Вычисления на машинах Тьюринга (определения).

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

αqiβ,

где α – то слово, что находится строго слева от головки на листе, β – то слово, что находится справа (включая обозреваемую ячейку).

Конфигурация Т, в которой головка смотрит на первую (левую) ячейку массива информации, записанной на ленте, называется правильной конфигурацией.

!!! Обычно требуют, чтобы машина Т начинала и заканчивала работу в правильных конфигурациях.

Задать МТ – значит задать последовательность конфигураций. Переход от одной конфигурации к другой описывается командами.

9