1.6. ПРОСТЕЙШАЯ МОДЕЛЬ ВЫЧИСЛЕНИЙ: МАШИНА ТЬЮРИНГА

Для доказательства того, что для вычисления данной функции требуется какое-то минимальное время, нужна некоторая модель, столь же общая, как те модели, которые у нас были, но более простая. Система команд должна быть ограничена, насколько возможно, хотя эта модель должна быть в состоянии не только вычислить все то, что может вычислить РАМ, но и сделать это "почти" так же быстро. Под словом "почти" мы будем подразумевать "полиномиальную связанность".

Определение. Говорят, что неотрицательные функции полиномиально связаны (эквивалентны), если найдутся такие полиномы что для всех справедливы неравенства

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

В настоящее время единственный класс функций, для которых мы можем применить такие общие вычислительные модели, как машины Тьюринга, чтобы получить нижние оценки вычислительной сложности, составляют "быстро растущие" функции. Например, в гл. 11 будет показано, что некоторые задачи требуют экспоненциальные время и память. (Функция называется экспоненциальной, если существуют такие постоянные что для всех, кроме конечного числа, значений Относительно полиномиальной связанности все экспоненциальные функции, по существу, одинаковы; любая функция, полиномиально связанная с экспоненциальной, сама экспоненциальна.

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

Определение. Многоленточная машина Тьюринга изображена на рис. 1.19. Она состоит из нескольких, скажем лент.

Рис. 1.19. Многоленточная машина Тьюринга.

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

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

1) изменить состояние управляющего устройства,

2) напечатать новые символы на лентах вместо старых в каких-нибудь или во всех клетках под головками,

3) сдвинуть какие-нибудь или все головки независимо друг от друга на одну клетку влево или вправо либо оставить на месте

Формально -ленточная машина Тьюринга задается семеркой

где

1) Q - множество состояний,

2) Т - множество символов на лентах,

3) I — множество входных символов, ,

4) b — пустой символ,

5) - начальное состояние,

6) - заключительное (или допускающее) состояние,

7) - функция переходов, она отображает некоторое подмножество множества т. е. по произвольному набору из состояния и символов на лентах она выдает новое состояние и пар, каждая из которых состоит из нового символа на ленте и направления сдвига головки.

Пусть и машина Тьюринга находится в состоянии а ее головка на ленте обозревает символ Тогда за один шаг эта машина Тьюринга переходит в состояние заменяет на и сдвигает головку на ленте в направлении (или в соответствии с)

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

Рис. 1.20. Работа машины Тьюринга над цепочкой

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

Пример 1.8. Двухленточная машина Тьюринга на рис. 1.20 распознает палиндромы в алфавите следующим образом.

1) Первая клетка на ленте 2 отмечается специальным знаком х, и вход копируется с ленты 1, где он записан вначале (рис. 1.20, а), на ленту 2 (рис. 1.20, б).

2) Затем головка на ленте 2 сдвигается к х (рис. 1.20, в).

3) Повторяется такая процедура: головка на ленте 2 сдвигается вправо на одну клетку, а на ленте 1 — влево на одну клетку и соответствующие символы сравниваются. Если все символы совпадают, то вход является палиндромом и машина Тьюринга доходит до допускающего состояния В противном случае в некоторый момент очередной шаг машины Тьюринга будет не определен, а она остановится, не допустив входного слова.

Функция переходов соответствующей машины Тьюринга приведена на рис. 1.21.

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

Если мгновенное описание переходит в мгновенное описание за один шаг машины Тьюринга то пишут -читается "переходит в"). Если для некоторого то пишут Если либо либо то пишут

Данная -ленточная машина Тьюринга допускает слово где элементы из I, если для некоторых содержащих

Пример 1.9. На рис. 1.22 приведена последовательность мгновенных описаний машины Тьюринга, изображенной на рис. 1.21,

(см. скан)

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

которой подано на вход слово Так как заключительное состояние, эта машина Тьюринга допускает 010.

В дополнение к естественной интерпретации машины Тьюринга как устройства, допускающего какой-то язык, ее можно рассматривать как устройство, которое вычисляет некоторую функцию Аргументы этой функции кодируются на входной ленте в виде слова х со специальным маркером отделяющим их друг от друга. Если машина Тьюринга останавливается, имея на ленте, выделенной в качестве выходной, целое число у (значение функции), то полагают Таким образом, процесо вычисления мало отличается от процесса допускания языка.

Временная сложность машины Тьюринга равна наибольшему числу шагов, сделанных ею при обработке входа длины (для всех входов длины Если на каком-нибудь входе длины машина Тьюринга не останавливается, то для этого значение не определено.

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

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