Материал: Ответы на экзаменационные вопросы по математической логике

25. Машина Тьюринга. Тьюринговая функциональная схема. Точное определение алгоритма. Тезис Тьюринга

Автоматизм, необходимый при реализации алгоритма, естественно привёл к мысли о передаче функции человека, реализующего алгоритм, машине. Эту идею предложили в 30-е годы прошлого века почти одновременно американский математик Эмиль Пост и английский математик Алан Тьюринг.

Рассмотрим один из вариантов, который носит название «машина Тьюринга».

Машина Тьюринга (МТ) — математическая модель идеализированного вычислительного устройства.

Устройство машины Тьюринга включает в себя:

1.Внешний алфавит, то есть конечное множество символов = {0, 1, … , }. В этом алфавите в виде слова кодируется та информация, которая подаётся в машину, то есть конечная последовательность символов алфавита. Машину перерабатывает эту информацию в новое слово.

2.Внутренний алфавит машины состоит из символов: {0, 1, … , , , , } . Символы 0, 1, … , — конечное число состояний машины, то есть возможных реакций МТ на любой символ внешнего алфавита.

Два состояния имеют особое назначение: 1 — начальное состояние машины (в этом состоянии машина начинает работать), 0 — заключительное состояние (стопсостояние; остановка).

Символы , , — это символы сдвига на 1 ячейку соответственно влево , на месте

и вправо .

Если нет состояния 1, то машина не начнёт работу, а если нет состояния 0, то машина не остановится, то есть зациклится.

3.Бесконечная в обе стороны лента, разбитая на ячейки (клетки). Это — внешняя память машины. В каждую ячейку может быть записан только один символ внешнего алфавита. Не пустым, то есть заполненным, может быть только конечное

число клеток. Пустую клетку обозначают символом 0 (иногда, если 0 не является символом алфавита, то вместо 0 пишут 0).

4.Управляющая (считывающая) головка. Она передвигается вдоль ленты и может останавливаться против какой-то клетки, то есть «считывать» символ в этой клетке. За один шаг головка может сдвинуться лишь на одну ячейку влево или на месте или вправо, что обозначается символами , , соответственно.

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

К началу работы машины на ленту подаётся начальная информация и управляющая головка, как правило, находится у крайнего правого (или левого) символа всех непустых клеток с указанием начального состояния 1 . Это так называемая начальная конфигурация.

Работа МТ складывается из тактов (шагов).

За один шаг машина может в данной ячейке:

•Написать один символ или оставить прежний в данной ячейке.

•Перейти в новое состояние или остаться в прежнем.

•Сдвинуться по ленте на одну клетку влево (или вправо) или остаться на месте.

Взависимости от того, какая была подана начальная информация , то есть

какая была начальная конфигурация, возможны 2 случая:

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

останавливается в некоторой конфигурации, то есть переходит в стоп-состояние 0. При этом на ленте оказывается изображённой некоторая информация . В этом случае говорят, что МТ применима к информации и перерабатывает её в , то есть существует и работает алгоритм перевода в .

2.МТ не останавливается, то есть не переходит в состояние 0 , как говорят, «зацикливается». В таком случае говорят, что данная МТ неприменима к информации .

Вкаждый момент работы МТ конфигурация записывается следующим образом:

{1, 2, … , , … , }

Это означает, что до 1 и после ячейки пустые, то есть в них стоят 0 (или 0), а в ячейках 1, … , могут быть как нулевые, так и ненулевые символы внешнего алфавита. При этом машина находится в состоянии .

Схему работы МТ, то есть алгоритма можно записать как программу МТ, то есть как конечное число шагов (тактов), каждый из которых записывается в виде:

→ ( , , )

Здесь 5 символов, 2 — из внешнего ( , ), 3 — из внутреннего ( , ( , , ), ) алфавитов. Такой шаг означает, что символ в ячейке, возле которой стоит управляющая головка, заменяется на символ , МТ из состояния переходит в состояние и при этом головка или сдвигается на 1 клетку влево ( ) или вправо ( ) или остаётся на месте ( ).

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

Пример. Дана Тьюринговая функциональная схема:

0 — символ пустой клетки.

Рассмотрим, как по такой программе работает МТ. Пример 1.

Пусть начальная конфигурация: {0, 0, 2, 2 , 0}

1

2 1 → 2 1, получаем: {0, 0, 2 , 2, 0}

1

2 1 → 2 1, получаем: {0, 0 , 2, 2, 0}

1

0 1 → 2 3, получаем: {0 , 2, 2, 2, 0}

3

0 3 → 0 0, получаем: {0, 2 , 2, 2, 0}

0

То есть МТ переработала слово 2 2 в слово 2 2 2. Пример 2.

Пусть начальная конфигурации: {0, 1, 1, 2, 2 , 0}

1

2 1 → 2 1, получаем: {0, 1, 1, 2 , 2, 0}

1

2 1 → 2 1, получаем: {0, 1, 1 , 2, 2, 0}

1

1 1 → 1 2, получаем: {0, 1, 1, 2 , 2, 0}

2

2 2 → 1 2, получаем: {0, 1, 1, 1 , 2, 0}

2

1 2 → 2 1, получаем: {0, 1, 1, 2 , 2, 0}

1

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

{0, 1, 1, 2, 2, 0}.

Тезис Тьюринга. Всякий алгоритм может быть задан посредством тьюринговой функциональной схемы и реализован в соответствующей МТ.

{0 0 0 0 0 0}

0

2.( ) = + , МТ { , } для вычисления этой функции задаётся Тьюринговая схема с двумя состояниями { 0, 1}:

1 1 0 1 1

Посмотрим, как работает эта МТ:

{0 0 1 1 0 0}

1

{0 0 1 1 0 0}

1

{0 0 1 1 0 0}

1

{0 1 1 1 0 0}

0

Вданном случае из 11 (то есть 1) получили 111 (то есть 2) (к слову: 1 – это 0).

3.( , … , ) = , МТ { , }.

Начальная информация — должны быть заданы 1, … , .

На ленте в алфавите {0,1} это группы 1, разделенные одной пустой клеткой, то есть 0.

Если две или более пустых клеток, то слева или справа от них только пустые клетки, то есть они показывают «границы» информации.

Например, конфигурация такая:

{0,0 , 1,1, … ,1 , 0, 1,1, … ,1 , 0, 1,1, … 1 , 0, 1,1, … 1 , 0,0}

То есть заданы значения аргументов функции 4-х переменных — начальная конфигурация. Наша МТ после окончания работы должна выдать значение

1( 1, … , ) = 1.

Пусть 1 — сохранение 1 в 1, 2 — обнуление 1 у остальных аргументов, 3 — определение границ, то есть конца информации, 0 — стоп-состояние.

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

Посмотрим, как работает данная МТ. Пусть начальная конфигурация:

{0,0, 1 , 1,0,1,1,1,0,1,0,0}

1

1 1 → 1 1, {0,0,1, 1 , 0,1,1,1,0,1,0,0}

1