Turing (т. алгоритмов)

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

Определение 1. Машина Тьюринга (МТ) определяется следующими данными:

1)конечным алфавитом A = {a0, a1, ..., an}, где a0 – символ пустой ячейки;

2)конечным множеством внутренних состояний Q = {q0, q1, ..., qm}, где q0 – состояние остановки:

попав в него, машина прекращает работу; q1 – начальное состояние: в этом состоянии машина начинает работать;

3) программой (или функциональной схемой), т.е. совокупностью выражений T (i, j), i = 1, ..., m, j =

1, ..., n (обычно записываемой в виде таблицы, т.е. матрицы), называемых командами, каждое из которых имеет один из следующих видов:

T(i, j)

T(i, j)

T(i, j)

: qiaj → qkalS,	0 ≤ k ≤ m,
: qiaj → qkalR,	0 ≤ l ≤ n,
: qiaj → qkalL.

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

... ... ...

В каждой ячейке записана ровно одна буква из алфавита A (запись буквы a0 означает, что ячейка пуста), причем символы, отличные от a0, записаны в конечном числе ячеек. В каждый момент времени (такт работы МТ) машина находится в одном из состояний из множества Q и "обозревает" только одну ячейку ленты (т.е. "читает"информацию, записанную в ячейке). По команде

T (i, j) : qiaj → qkalX (где X = R, или X = L, или X = S),

означающей, что МТ находится в состоянии qi и обозревает ячейку, в которой записана буква aj , МТ в обозреваемой ячейке стирает букву aj и записывает в нее букву al. Затем МТ переходит к обозреванию ячейки, находящейся слева или справа от предыдущей, если X = L или X = R соответственно, либо же продолжает обозревать предыдущую ячейку, если X = S; при этом состояние машины меняется на qk.

Если k 6= 0, то после выполнения указанной команды МТ на следующем шаге (такте) переходит к выполнению команды T (k, l). Если же qk = q0, то машина останавливается, так как по определению ни одна команда программы не начинается с q0.

Полное описание состояния машины Тьюринга в данный момент времени задается словом вида P qiaj R, где qi – состояние машины в данный момент, aj – символ, записанный в обозреваемой ячейке, а P и R – слова, записанные левее и правее этой ячейки. Такое слово P qiaj R называется конфигурацией, описывающей состояние машины Тьюринга в данный момент. При этом будем говорить, что машина T

находится в конфигурации P qiaj R.

Среди внутренних состояний машины Тьюринга T часто выделяют еще и начальное состояние q1.

Пусть E – слово во внешнем алфавите A машины Тьюринга T . Запишем слово E последовательно на ленту и приведем машину T в конфигурацию q1 a0 E.

Если машина Тьюринга T , начав работать в конфигурации q1a0E, через конечное числов тактов работы перейдет в конфигурацию вида Dq0B (здесь имеется в виду, что обозревается первый символ слова B), то слово DB называется результатом применения к слову E машины Тьюринга T . В противном случае мы говорим, что машина T к слову E не применима. Другими словами, мы считаем, что машина T вычисляет некоторую словарную функцию fT (x), значением которой при x = E является слово DB, причем, эта функция определена только для тех слов E, при которых машина остановится.

Применение машин Тьюринга к словам. Вычислимые по Тьюрингу функции

Договоримся о некоторых общепринятых соглашениях: символ a0 будем обозначать 0, символ a1 – 1, для любой буквы a через am будем обозначать слово длины m, все буквы которого – это a, т.е. слово вида a . . . a.

|{z}

m

Машины Тьюринга можно использовать для вычисления функций, аргументы и значения которых пробегают слова в данном алфавите, содержащемся в алфавите ленточных символов. В частности, речь может идти о вычислении функций от натурального аргумента. При этом натуральное число n представляется словом n¯ длины n в однобуквенном алфавите {1}, т.е. словом 1n.

Определение 2. Мы говорим, что машина Тьюринга T вычисляет данную функцию f(x1, x2.., xk), eсли, начав работу в конфигурации q101n1 01n2 0...01nk , (n1, n2.., nk) Nk, она останавливается в том

1

2

и только том случае, если f(n1, n2.., nk) определено, и при этом заключительное состояние имеет вид

q001f (n1,n2..,nk)0.

В случае функции одного переменного начальная конфигурация имеет вид q101n0.

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

Тезис Черча (или тезис Черча–Тьюринга) состоит в том, что

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

Введем еще одно определение.

Определение 4. Пусть f – k-местная (частичная) функция с областью определения D(f) Nk.

Машина Тьюринга T правильно вычисляет функцию f(x1, . . . , xk), если:

1)машина T вычисляет функцию f(x1, . . . , xk);

2)в заключительном состоянии машина обозревает ту же ячейку ленты, что и в начальном (будем называть эту ячейку первой);

3)в процессе выполнения программы головка машины не сдвигается левее первой ячейки.

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

Теорема 1. Всякая вычислимая по Тьюрингу функция правильно вычислима.

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

Счетность множества машин Тьюринга. Существование невычислимых функций

Программу всякой машины Тьюринга можно интерпретировать как слово в некотором конечном алфавите. Это можно сделать, например, так. Пусть A = {0, 1, 2, ..., 9, a, q, R, L, S, →, |} – алфавит. Он содержит 17 символов. Рассмотрим программу машины Тьюринга, например, такую:

q1a1 → qkalR, q1a2 → qiaj L,

...

qman → qratS.

Запишем теперь все команды в одну строчку, разделяя их символом | и заменяя нижние индексы на равные им числа, но расположенные уже на уровне основного текста:

q1a1 → qkalR|q1a2 → qiajL|...|qman → qratS.

Мы получили слово в алфавите A. По этому слову программа машины Тьюринга восстанавливается однозначно. Но очевидно, что не всякое слово из A является программой некоторой машины Тьюринга.

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

Теорема 2. Множество машин Тьюринга счетно.

C другой стороны, имеет место следующее утверждение.

Предложение 1. Множество (арифметических) функций несчетно.

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

	f1, f2, ..., fn, ...
Определим функцию		1, если fn(n) = 0.
f(n) =
		0, если fn(n) = 1,

3

Функция f принадлежит M, так как принимает значения только 0 и 1, но она отлична от любой функции fi, i N. Действительно, f(i) = 0, если fi(i) = 1, и f(i) = 1, если fi(i) = 0. Мы получили противоречие.

C

Из теоремы 2 и предложения 1 следует

Теорема 3. Существует функция, не вычислимая по Тьюрингу.

Замечание. Пусть Θ – множество машин Тьюринга. Оно счетно согласно предложению 2. Существует вычислимая нумерация

ϕ : N → Θ

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

Проблемы самоприменимости и остановки

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

Пусть зафиксирована некоторая вычислимая нумерация машин Тьюринга.

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

Проблема самоприменимости является частным случаем проблемы остановки и заключается в том, чтобы определить, применима ли машина к своему номеру.

Будем рассматривать только машины с алфавитом A = {a0, a1} = {0, 1}.

Теорема 4. Невозможен алгоритм, распознающий по произвольному натуральному числу n, является ли это число номером самоприменимой машины Тьюринга.

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

Доказательство. Предположим противное, и пусть M0 – множество номеров самоприменимых машин Тьюринга. Тогда по тезису Черча существует машина T0, вычисляющая функцию

χ(x) =	1,	если x M0;
	0	в противном случае

(характеристическую функцию множества M0). Это означает, что машина T0 слово, состояшее из x единиц перерабатывает в 1, если x M0, и в 0, если x не принадлежит M0. Построим новую машину T1 следующим образом. В программе машины T0 заменим все вхождения символа q0 на qr, где qr не содержится среди состояний T0, и добавим следующие команды:

qr0 → qr+10R, qr+11 → qr+11S, qr+10 → q0L1.

Нетрудно видеть, что машина T1 работает бесконечно на входе x, если x M0, и печатает 1, если x не

принадлежит M0.
Пусть x1 – номер машины T1. Если x1 M0, то T1	– самоприменимая машина, но это невозможно,
так как T1 не применима к элементам множества M0	. Если x не принадлежит M0, то T1 не является
самоприменимой, но это противоречит тому, что T1 применима к элементам, не принадлежащим M0. C
Теорема 5. Существует машина Тьюринга с неразрешимой проблемой остановки.
Доказательство. В качестве такой машины можно взять машину, перечисляющую множество M0
номеров самоприменимых машин.	C