Лекция № 3. Машины Тьюринга

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

2. Не распознаваемость самоприменимости машины Тьюринга

Формализация понятия «алгоритм» на основе так называемых машин Тьюринга была предложена английским математиком Аланом Тьюрингом в 1936 году. С тех пор эта абстрактная математическая модель широко применяется в теории алгоритмов для исследования вербальных алгоритмов. Переходя к неформальному описанию машин Тьюринга, отметим следующее.

А.Тьюринг

В состав любой машины Тьюринга входит бесконечная в обе стороны лента, разделенная на ячейки, и головка, способная передвигаться вдоль ленты вправо и влево (см. рис. 4).

Ý – головка

Рис. 4. Представление машины Тьюринга.

В ячейку ленты может быть записана буква из алфавита A ={a₀, a₁, a₂, … a_n}. Для каждой машины Тьюринга этот алфавит, называемый внешним, вообще говоря, свой. Но принято резервировать символ a₀ для обозначения пустой ячейки при определении внешнего алфавита любой машины. Будем также считать, что непустое слово в алфавите A–{a₀} воспринимается любой машиной в стандартном положении, если головка находится напротив крайней справа ячейки ленты из тех, в которых записано слово[5] (см. рис. 5).

a0

a0

a0

a0

a0

A0

a0

a0

Ý – головка

Рис. 3. Стандартное положение в машине Тьюринга

(внешний алфавит A ={a₀, 0,1})

Работа любой машины Тьюринга осуществляется дискретным образом – шагами (тактами). В каждом такте головка располагается напротив какой-либо ячейки, «обозревая» ее. При этом она может «читать», имеющуюся в ячейке букву; записать в ячейку букву (из алфавита A), предварительно стерев старую; сдвигаться на одну ячейку влево или вправо.

Полагается, что при каждом такте работы машина находится в каком-то состоянии, обозначаемом буквой q_i из алфавита внутренних состояний – Q ={q₀, q₁, q₂, ….q_m}. Каждая машина Тьюринга имеет свой собственный алфавит внутренних состояний, но принято считать, что символом q₀ в таком алфавите обозначается состояние остановки, а символом q₁ – начальное состояние. Из состояния q₁ машина начинает работать, а попав в состояние q₀, прекращает работу.

Работа любой машины Тьюринга осуществляется по своей собственной программе или в соответствии с функциональной схемой, представляющей собой совокупность выражений T(i, j) (1£i£m, 0£j£n, i,jÎZ), именуемыми командами, каждая из которых может иметь следующий вид (см. таблицу 1).

Функциональная схема машины Тьюринга (программа) может быть записана в виде последовательности команд или в виде таблицы (см. пример 3.1.1).

Таким образом, та или иная машина Тьюринга полностью определяется:

а) внешним алфавитом A ={a₀, a₁, a₂, … a_n};

б) алфавитом внутренних состояний Q ={q₀, q₁, q₂, ….q_m};

в) программой (функциональной схемой).

Таблица 1

Команды машины Тьюринга
Формат команды	Описание команды
qiaj →qkapЛ	В ячейке, которую «обозревает» головка, стирается буква aj. Вместо нее в эту ячейку записывается буква ap. Из состояния qi машина переходит в состояние qk. Головка сдвигается на одну ячейку влево (Л).
qiaj →qkapП	В ячейке, которую «обозревает» головка, стирается буква aj. Вместо нее в эту ячейку записывается буква ap. Из состояния qi машина переходит в состояние qk. Головка сдвигается на одну ячейку вправо (П).
qiaj → qkap	В ячейке, которую «обозревает» головка, стирается буква aj. Вместо нее в эту ячейку записывается буква ap. Из состояния qi машина переходит в состояние qk. Головка остается на месте.

Говорят, что слово a перерабатывается машиной Тьюринга в слово b, если от слова a, воспринимаемого в начальном состоянии q₁, машина после выполнения конечного числа команд программы приходит к слову b, воспринимаемому в положении остановки.

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

Q A	q1	q2	q3
a0		q31П	q1a0Л
	q2a0Л	q21Л	q31П
*	q0a0	q2*Л	q31*П

Слово, воспринимаемое в начальном состоянии q₁ имеет вид:

*

q1

Ý

Определим, в какое слово переработает это слово машина.

Так машина находится в состоянии q_{1 ,} обозревая ячейку в которой находится 1, то первой должна быть выполнена команда, стоящая на пересечении столбца q₁ и строки 1 функциональной схемы. Это команда q₂a₀Л. После ее выполнения машина перейдет в следующее состояние:

*

a0

q2

Ý

После выполнения следующей команды q₂*Л (записанной на пересечении столбца q₂ и строки 1) машина перейдет в следующее состояние:

*

a0

q2

Ý

На пересечении столбца q₂ и строки 1 в функциональной схеме машины Тьюринга записана команда q₂1Л, выполнение которой приведет к состоянию:

*

a0

q2

Ý

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

q₂1→q₂1Л

*

a0

q2

Ý

q₂a₀→q₃1П

*

a0

q3

Ý

q₃1→q₃1П

*

a0

q3

Ý

q₃1→q₃1П

*

a0

q3

Ý

q₃*→q₃*П

*

a0

q3

Ý

q₃a₀→q₁a₀Л

*

a0

q1

Ý

q₁*→q₀a₀

q1

Ý

Таким образом, машина Тьюринга, определенная приведенной выше функциональной схемой, перерабатывает слово 11*1 в слово 111. Взяв в качестве исходных слов 111*111, 111*11 и т.п., можно усмотреть определенную закономерность в работе машины.

Определение 3.1.1. Пусть на некотором множестве слов алфавита {a₁, a₂, … a_l} задана функция k переменных, значениями которой являются слова в том же алфавите. Предположим, что имеется машина Тьюринга с алфавитом A={a₀, a₁, a₂, … a_l} (n³l), которая любой набор из k слов, входящий в область определения функции, записанный последовательно с промежутком в одну ячейку между словами, перерабатывает в слово, являющееся значением функции на этом наборе. А на любом наборе из k слов, не входящих в область определения функции, машина работает бесконечно. Тогда про такую машину Тьюринга говорят, что она вычисляет данную функцию, а сама функция называется вычислимой по Тьюрингу.

Дата добавления: 2014-01-06