ГЛАВА 8. Введение в теорию машин Тьюринга

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

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

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

8.1. Задачи, не решаемые компьютерами

Цель этого раздела — с помощью С-программирования неформально доказать, что существуют задачи, которые невозможно решить, используя компьютер. Мы рассмотрим частную задачу распознавания, является ли текст hello, world первым, что печатает С-программа. Можно подумать, будто имитация любой программы всегда позволит ска­зать, что она делает, однако в реальности нам придется «бороться» с программами, кото­рые работают невообразимо долго, прежде чем что-нибудь вывести на печать. Эта про­блема — незнание момента, в который что-то произойдет, если вообще произойдет, — является основной причиной нашей неспособности распознать, что делает программа. Однако доказательство того, что не существует алгоритма решения указанной задачи распознавания, весьма сложно и требует определенного формализма. В этом разделе предпочтение отдается формальным доказательствам, а не интуиции.

8.1.1. Программы печати „Hello, world»

На рис. 8.1 показана первая С-программа, представленная в классической книге Кер- нигана и Ритчи.^[1] Несложно обнаружить, что данная программа печатает hello, world и останавливается. Она настолько прозрачна, что обычно знакомство с языками про­граммирования начинается демонстрацией того, как на этих языках написать программу печати hello, world.

main() {

printf(«hello, world\n»);

}

Рис. 8.1. Программа Кернигана и Ритчи, приветствующая мир

Однако есть и другие программы, которые тоже печатают hello, world, причем отнюдь не очевидно, что они делают именно это. На рис. 8.2 представлена еще одна про­грамма, которая, возможно, печатает hello, world. Она получает на вход п и ищет положительные целые решения уравнения х» + у» = z». Если находит, то печатает hello, world. Не обнаружив целых х, у и г, удовлетворяющих данному уравнению, она про­должает поиск до бесконечности и никогда не печатает hello, world.

Для того чтобы понять, как работает эта программа, сначала заметим, что ехр явля­ется встроенной функцией вычисления экспоненты. Основной программе нужно искать тройки (х, у, z) в порядке, гарантирующем, что каждая тройка в конце концов достигает­ся. Для корректного поиска используется четвертая переменная, total, которая ини­циируется значением 3 и увеличивается в while-цикле каждый раз на 1, так что ее значе­ние в конце концов достигает любого натурального числа. Внутри while-цикла total разделяется на три положительных целых х, у и z, причем х изменяется в for-цикле от 1 до total-2, у внутри этого for-цикла изменяется от 1 до total-x-1, а остаток значе­ния total, между 1 и total-2, становится значением г.

Во внутреннем цикле для тройки (х, у, z) проверяется равенство х^п + у^п = z. Если оно выполняется, то печатается hel 1о, world, а если нет — не печатается ничего.

int exp(int i, n)

/* вычисление i в степени n */ {

int ans, j; ans = 1;

for (j=l; j<=n; j++) ans *= i; return(ans);

main () {

int n, total, x, y, z; scanf(«%d», n); total = 3; while (1) {

for (x=l; x<=total-2; x++)

for (y=l; x<=total-x-l; y++){ z = total — x — y;

if (exp(x,n) + exp(y,n) == exp(z,n)) printf(«hello, world\n»);

}

total++;

}

}

Puc. 8.2. Великая теорема Ферма, выраженная в программе приветствия мира

Если прочитано значение 2, то программа находит набор значений total = 12, х ~ 3, р 4 и z = 5, для которого х^п + у¹ = z». Таким образом, если на входе 2, то программа дей­ствительно печатает hello, world.

Однако для любого п > 2 программа никогда не найдет тройку положительных целых, удовлетворяющих хⁿ+yⁿ-zⁿ, и hello, world напечатано не будет. Интересно, что еще несколько лет назад не было известно, печатает ли данная программа hello, world, т.е. имеет ли уравнение х^п + у^п = z» для некоторого большого п. Утверждение, что это уравнение не имеет решений, было сформулировано Ферма более 300 лет назад, но до недавних пор доказательство не было найдено. Данное утверждение часто называ­ется «великой теоремой Ферма» («Fermat’s last theorem»).

Определим проблему «hello, world» следующим образом. По данной С-программе и ее входу определить, печатает ли она в качестве первых 12 символов hello, world. В дальнейшем для краткости утверждение о том, что программа печатает hello, world, употребляется в смысле,- что она печатает hel 1о, world как первые 12 символов.

Поскольку математикам понадобилось более 300 лет для решения вопроса, выражен­ного простенькой 22-строчной программой, то представляется правдоподобным, что об­щая задача распознавания, печатает ли hello, world данная программа с данным входом, должна быть действительно сложной. Таким образом, любую задачу, не решен­ную математиками до сих пор, можно поставить как вопрос вида «печатает ли hello, world данная программа с данным входом?». Было бы замечательно, если бы нам уда­лось написать программу, которая проверяет любую программу Р и ее вход / и определя­ет, печатается ли hello, world при выполнении Р со входом /. Мы докажем, что та­кой программы не может быть.

Почему должны существовать неразрешимые проблемы

Нелегко доказать, что какая-то определенная проблема, например, обсуждаемая здесь проблема «hello, world», должна быть неразрешимой. Однако легко понять, почему почти все проблемы должны быть неразрешимыми в рамках любой системы, вклю­чающей программирование. Вспомним, что «проблема»— это в действительности вопрос о принадлежности цепочки языку. Множество различных языков над любым алфавитом, в котором более одного символа, несчетно} Таким образом, невозможно пронумеровать языки натуральными числами так, чтобы каждый язык получил но­мер, и каждое число было назначено одному языку.

С другой стороны, программы, будучи конечными цепочками в конечном алфавите (обычно это подмножество алфавита ASCII), допускают такую нумерацию, т.е. обра­зуют счетное множество. Их можно упорядочить по длине, а программы одной дли­ны расположить в лексикографическом порядке. Таким образом, можно говорить о программе с номером 1, 2 и вообще с номером /.

В результате можно утверждать, что проблем существует «бесконечно больше», чем программ. Если случайно выбрать язык, то почти наверняка он окажется неразреши­мой проблемой. И то, что проблемы в большинстве своем кажутся разрешимыми, обусловлено лишь редкостью обращения к случайным проблемам. Наоборот, мы склонны к изучению относительно простых, хорошо структурированных проблем, и, действительно, они часто разрешимы. Однако даже среди проблем, которые интере­суют нас и допускают ясную и краткую формулировку, можно найти много неразре­шимых, и в том числе проблему «hello, world».

8.1.2. Гипотетическая программа проверки приветствия мира

Докажем невозможность создания программы проверки приветствия мира (печати «hello, world») методом от противного. Предположим, что существует программа, ска­жем, Н, которая получает на вход программу Р и ее вход / и сообщает, печатает ли Р, имея на входе /, текст hello, world. Работа Н представлена на рис. 8.3. В частности, Н всегда печатает либо yes (да), либо по (нет), и ничего более.

Если проблема имеет алгоритм, подобный программе Я, который на любом экземп­ляре проблемы правильно отвечает «да» или «нет», то такая проблема называется «разрешимой». В противном случае проблема «неразрешима». Наша цель — доказать, что Я не существует, т.е. проблема «hello, world» является неразрешимой.

Программа обнаружения «hello, world»

Я

Рис. 8.3. Гипотетическая программа обнаружения «hello, world»

Для доказательства этого утверждения методом от противного внесем в Я несколько изменений, построив в итоге программу Н₂, и докажем, что ее не существует. Поскольку изменения, вносимые в Я, можно совершить с любой С-программой, единственным со­мнительным утверждением будет существование Я, т.е. утверждение, которое мы и оп­ровергнем.

Для простоты доказательства сделаем несколько допущений о С-программах. Эти ги­потезы упрощают, а не усложняют работу Я, поэтому, если доказать, что программы проверки «hello, world» не существует для таких ограниченных С-программ, то для более широкого класса программ такой программы проверки тем более не может быть. Итак, допустим следующее.

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

Все символы печатаются с помощью функции print f, без использования putchar () и других.

Теперь предположим, что Я существует. Наша первая модификация изменяет выход по, который является откликом Я, когда ее входная программа Р со своим входом / не печатает hello, world. Как только Я печатает «п», нам становится понятно, что далее рано или поздно появится «о».^[2] Таким образом, каждый вызов printf в Я изменим так, чтобы вместо «п» печаталось hello, world. Другие вызовы, которые печатают «о» без «п», опускаются. В результате получим программу H_t, которая ведет себя точно так же, как и Я, но печатает hello, world вместо по (рис. 8.4).

Следующее преобразование программы несколько сложнее. Оно, по сути, представ­ляет собой прием, позволивший Алану Тьюрингу доказать свой результат о неразреши­мости для машин Тьюринга. Поскольку нас в действительности интересуют программы,

Она получает на вход только Р, а не Р и I.

Она отвечает, что сделала бы Р, если бы ее входом была она сама, т.е. что выдала бы H_t, имея на входе Р в качестве как программы, так и входа /.

Для создания программы Н₂, представленной на рис. 8.5, внесем в Н, следующие

изменения.

которые получают на вход другие программы и что-то о них сообщают, ограничим Hi следующим образом.

Вначале Н₂ считывает весь вход Р и запоминает его в массиве А, выделяя память под массив с помощью malloc^[3].

Затем Н₂ имитирует H_h но вместо чтения из Р или / программа Н₂ читает из копии в массиве А. Для запоминания мест в Р и /, до которых дочитала H_t, Н₂ может содер­жать два курсора, отмечающих позиции в А.

Теперь все готово для доказательства того, что Н₂ не существует. Таким образом, не существует Hi и, аналогично, Я. Для того чтобы в этом убедиться, нужно представить себе, что делает Н₂, когда получает себя в качестве входа (рис. 8.6). Напомним, что Н₂, получив некоторую программу Р на вход, печатает yes, если Р печатает hello, world, получая себя в качестве входа. Кроме того, Н₂ печатает hello, world, если Р, получив себя на вход, не выдает hello, world в качестве начала своего выхода.

Предположим, что Н₂ в рамке (см. рис. 8.6) печатает yes. Тогда Н₂ в рамке говорит о сво­ем входе Н₂, что Н₂, получая себя в качестве входа, выдает вначале hello, world. Но мы только что предположили, что выход Н₂ начинается текстом yes, а не hello, world.

Таким образом, получается, что выходом программы в рамке (см. рис. 8.6) является не yes, a hello, world, поскольку возможно либо одно, либо другое. Но если Н₂, по­лучая себя на вход, печатает hello, world, то выходом программы в рамке на рис. 8.6 должно быть yes. Каким бы ни был предполагаемый выход Н₂, доказано, что она печатает противоположное.

Описанная ситуация противоречива, и мы приходим к выводу, что Н₂ не может суще­ствовать. Это опровергает предположение о существовании Я. Таким образом, доказано, что ни одна программа Я не может сказать, печатает ли данная программа Р со входом I текст hello, world.

8.1.3. Сведение одной проблемы к другой

Печатает ли данная программа в начале своего выхода текст hello, world? Мы уже знаем, что ни одна компьютерная программа этот вопрос разрешить не может. Про­блема, которую нельзя разрешить с помощью компьютера, называется неразрешимой. Формальное определение «неразрешимого» будет дано в разделе 9.3, а пока этот термин используется неформально. Предположим, что нам нужно определить, разрешима ли не­которая новая проблема. Мы можем попытаться написать программу для ее разрешения, но, если нам непонятно, как это сделать, мы можем попробовать доказать, что такой программы не существует.

Неразрешимость новой проблемы можно было бы доказать аналогично тому, как это было сделано для проблемы «hello, world»: предположить, что программа разрешения существует, и построить противоречивую программу, которая должна делать одновре­менно две взаимно исключающие вещи, как программа Н₂. Однако если у нас есть про­блема, неразрешимость которой установлена, то нам не обязательно вновь доказывать противоречивость. Достаточно показать, что если новая проблема имеет решение, то его можио использовать для разрешения уже известной неразрешимой проблемы. Такой подход представлен на рис. 8.7 и называется сведением Pi к Р₂.

Предположим, нам известно, что проблема Р] неразрешима, а Р₂ — новая проблема, неразрешимость которой нужно доказать. Допустим, что существует программа, которая

представлена ромбом с отметкой «разрешить» (см. рис. 8.7) и печатает yes или по в за­висимости от того, принадлежит или нет ее входной экземпляр проблемы Р₂ языку этой проблемы.^[4]

yes

Экземпляр Л

Построить —►Экземпляр

по

Рис. 8.7. Если бы можно было разрешить проблему Р₂, то ее решение мы могли бы использовать для разрешения проблемы Р]

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

Применить алгоритм построения к данному экземпляру проблемы Р,, т.е. к строке w, которая может принадлежать или не принадлежать языку P_h и получить строку jc.

Проверить, принадлежит ли jc языку Р₂, и перенести ответ на и» и Pi.

Пример 8.1. Применим описанный метод для доказательства, что вопрос «вызывает ли когда-нибудь программа Q с данным входом у функцию f оо» неразрешим. Заметим, что в Q может не быть функции f оо, и в этом случае задача решается просто. Однако она становится сложной, если Q имеет функцию foo, но с у на входе может как достичь, так и не достичь вызова foo. Поскольку нам известна только одна неразрешимая про­блема, роль Р1 на рис. 8.7 играет проблема «hello, world». В качестве Р₂ выступает опи­санная только что проблема «calls-foo». Предположим, что существует программа раз­решения этой проблемы. Наша задача — построить алгоритм, который преобразует про­блему «hello, world» в проблему «calls-foo».

Действительно ли компьютер может делать все это?

Если присмотреться к программе, представленной на рис. 8.2, можно спросить, дей­ствительно ли она находит контрпримеры к великой теореме Ферма. Как-никак, це­лые числа в типичном компьютере имеют всего 32 бит, и если самый маленький контрпример содержит числа, измеряемые биллионами, то произойдет ошибка пере­
полнения, прежде чем отыщется решение. И вообще, компьютер со 128 Мбайт опера­тивной памяти и 30-гигабайтным диском имеет «всего» 25 6^30128000000 состояний и яв­ляется, таким образом, конечным автоматом.

Однако рассмотрение компьютера как конечного автомата (или мозга как конечного автомата, откуда, кстати, происходит идея КА) непродуктивно. Число состояний на­столько велико, а пределы настолько размыты, что прийти к каким-либо полезным заключениям невозможно. В действительности, есть все причины поверить в то, что при желании множество состояний компьютера можно расширять до бесконечности. Например, целые числа можно представить в виде связанных списков цифр произ­вольной длины. Если память исчерпывается, программа печатает запрос на замену заполненного диска новым, пустым. И такие запросы могут повторяться по мере на­добности сколько угодно раз. Такая программа будет намного сложнее, чем приве­денная на рис. 8.2, но все равно мы сможем ее написать. Подобные приемы позволят любой другой программе обойти ограничения на размер памяти, величину целых чи­сел и другие параметры.

Итак, имея программу Q и ее вход у, мы должны построить программу R и ее вход z так, чтобы R со входом z вызывала f оо тогда и только тогда, когда Q со входом у печа­тает hello, world. Конструкция проста.

Если Q имеет вызываемую функцию f оо, переименовать ее и все ее вызовы. Оче­видно, новая программа Q, выполняет то же самое, что и Q.

Добавить в Q, функцию f оо. Эта функция не делает ничего и не вызывается. Полу­ченная программа называется Q₂.

Изменить Q₂ так, чтобы первые 12 символов ее печати запоминались в глобальном массиве А. Пусть полученная программа называется Q₃.

Изменить Q₃ так, чтобы после каждого выполнения инструкции печати с использо­ванием массива А проверялось, напечатано ли не менее 12 символов, и если так, то не образуют ли первые 12 символов текст hello, world. В этом случае вызвать новую функцию f оо, добавленную в п. 2. Полученная программа есть R, а ее вход z совпадает су.

Предположим, что Q со входом у печатает hello, world в качестве начала своего выхода. Тогда построенная R вызывает f оо. Однако если Q со входом у не печатает сна­чала hello, world, то R со входом z никогда не вызывает fоо. Если можно решить, вызывает ли R со входом z функцию f оо, то можно и решить, печатает ли Q со входом у сначала hello, world. Поскольку нам известно, что алгоритма решения проблемы «hello, world» нет, и все 4 этапа построения R по Q можно выполнить, отредактиро­вав код, то предположение о том, что программа разрешения проблемы «calls-foo» суще­ствует, ложно. Такой программы нет, и данная проблема неразрешима. □

Направление сведения является важным

Обычная ошибка — пытаться доказывать неразрешимость проблемы Р₂ путем сведе­ния ее к известной неразрешимой проблеме Р_h т.е. доказывать утверждение «если Pi разрешима, то Р₂ разрешима». Это утверждение, безусловно, истинное, бесполезно, поскольку предпосылка «Pi разрешима» ложна.

Единственный путь доказать, что новая проблема Р₂ неразрешима, состоит в том, чтобы свести к ней уже известную неразрешимую проблему, т.е. доказать утвержде­ние «если Pi неразрешима, то Р₂ неразрешима». Поскольку неразрешимость P_t уже установлена, приходим к выводу, что Р₂ неразрешима.

8.1.4. Упражнения к разделу 8.1

8.1.1. Сведите проблему «hello, world» к каждой из следующих проблем. Исполь­зуйте неформальный стиль данного раздела для описания правдоподобных пре­образований программ и не беспокойтесь о реальных пределах размеров файла или памяти в компьютерах:

а) (!*) по данной программе и ее входу определить, останавливается ли она ко­гда-нибудь, т.е. не зацикливается ли при данном входе;

б) по данной программе и ее входу определить, печатает ли она вообще что- нибудь;

в) (!) по данным двум программам и входу определить, порождают ли они один и тот же выход при данном входе.

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

Цель теории неразрешимых проблем состоит не только в том, чтобы установить су­ществование таких проблем (что само по себе не просто), но также в том, чтобы обеспе­чить программистов информацией, какие задачи программирования можно решить, а ка­кие нельзя. Теория также имеет огромное практическое значение, когда рассматривают­ся проблемы, которые хотя и разрешимы, но требуют слишком большого времени для их решения (см. главу 10). Эти проблемы, называемые «трудно разрешимыми», или «труднорешаемыми», подчас доставляют программистам и разработчикам систем боль­ше хлопот, чем неразрешимые проблемы. Причина в том, что неразрешимые проблемы редко возникают на практике, тогда как трудно разрешимые встречаются каждый день. Кроме того, они часто допускают небольшие модификации условий или эвристические решения. Таким образом, разработчику постоянно приходится решать, относится ли данная проблема к классу труднорешаемых и что с ней делать, если это так.

Нам нужен инструмент, позволяющий доказывать неразрешимость или трудноре- шаемость повседневных вопросов. Методика, представленная в разделе 8.1, полезна для вопросов, касающихся программ, но ее нелегко перенести на проблемы, не связанные с программами. Например, было бы нелегко свести проблему «hello, world» к про­блеме неоднозначности грамматики.

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

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

8.2.1. Поиски решения всех математических вопросов

В начале XX столетия великий математик Д. Гильберт поставил вопрос о поисках ал­горитма, который позволял бы определить истинность или ложность любого математи­ческого утверждения. В частности, он спрашивал, есть ли способ определить, истинна или ложна произвольная формула в исчислении предикатов первого порядка с целыми числами. Исчисление предикатов первого порядка с целыми (арифметика) достаточно мощно, чтобы выразить утверждения типа «эта грамматика неоднозначна» или «эта про­грамма печатает hello, world». Поэтому, окажись предположение Гильберта пра­вильным, данные проблемы были бы разрешимыми.

Однако в 1931 г. К. Гедель опубликовал свою знаменитую теорему о неполноте. Он доказал, что существует истинная формула первого порядка с целыми, которую нельзя ни доказать, ни опровергнуть в исчислении предикатов первого порядка над целыми. Его техника доказательства похожа на конструкцию противоречивой программы Н₂ из раз­дела 8.1.2, но имеет дело с функциями целого аргумента, а не с С-программами.

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

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

8.2.2. Описание машин Тьюринга

Машина Тьюринга изображена на рис. 8.8. Машина состоит из конечного управления, которое может находиться в любом из конечного множества состояний. Есть лента, разби­тая на клетки; каждая клетка может хранить любой символ из конечного их множества.

Конечное управление

1

	В	в		X		X		X	в	в
								п

Рис. 8.8. Машина Тьюринта

Изначально на ленте записан вход, представляющий собой цепочку символов конеч­ной длины. Символы выбраны из входного алфавита. Все остальные клетки, до беско­нечности, слева и справа от входа содержат специальный символ, называемый пустым символом, или пробелом. Он является не входным, а ленточным символом. Кроме вход­ных символов и пробела возможны другие ленточные символы.

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

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

Изменить состояние. Следующее состояние может совпадать с текущим.

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

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

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

M=(Q, X, Г, 5, q₀, В, F), компоненты которой имеют следующий смысл. Q — конечное множество состояний конечного управления. 2 — конечное множество входных символов.

Г — множество ленточных символов’, Е всегда есть подмножество Г. 5— функция переходов. Аргументами S(q,X) являются состояние q и ленточный символ X, а значением, если оно определено, — тройка (р, Y, D). В этой тройке р есть сле­дующее состояние из Q, Y— символ из Г, который записывается вместо символа в обозреваемой клетке, a D — направление сдвига головки «влево» или «вправо», обо­значаемое, соответственно, как L или R. q₀ — начальное состояние из Q, в котором управление находится в начале. В — пустой символ, или пробел. Этот символ принадлежит Г, но не X, т.е. не является входным. Вначале он записан во всех клетках, кроме конечного их числа, где хра­нятся входные символы. Остальные символы называются значащими. F — множество заключительных, или допускающих, состояний; является подмножеством Q.

8.2.3. Конфигурации машин Тьюринга

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

Кроме ленты, нужно представить конечное управление и позицию головки. Для этого состояние помещается непосредственно слева от обозреваемой клетки. Во избежание не­однозначности получаемой цепочки, состояния обозначаются символами, отличными от ленточных. Таким образом, для представления МО используется цепочка Х,Х₂…Х^ iqXX: i—X„. Здесь q— состояние МТ, головка обозревает /-ю слева клетку, а Х,Х₂…Х„ представляет собой часть ленты между крайними слева и справа значащими символами. Как исключение, если головка находится слева или справа от значащих символов, неко­торое начало или окончание X_tX₂.. .Х„ пусто, a i имеет значение, соответственно, 1 или п.

Переходы МТ М = (Q, 2, Г, 5, q₀, В, F) описываются с помощью отношения (- , ис-

м

пользованного для МП-автоматов. Подразумевая МТ М, для отображения переходов ис­пользуем |-. Как обычно, для указания нуля или нескольких переходов МТ М использу- * *

ется отношение I- или I-. и

Пусть 8{q,X) = (р, Y, L), т.е. головка сдвигается влево. Тогда

Х/Х₂—X, jqXXi/…Х„ h Х-1Х-2—₂pX, iYX,.i —X„. м

Заметим, как этот переход отображает изменение состояния на р и сдвиг головки на клетку /’ — 1. Здесь есть два важных исключения.

Если /’ = 1, то М переходит к пробелу слева от Xj. В этом случае

qX,X₂…X„ h pBYX₂…X„.

м

Если i = п и Y= В, то символ В, заменяющий Х„, присоединяется к бесконечной после­довательности пробелов справа и не записывается в следующем МО. Таким образом,

Х]Х₂—Х„ jqX„ [- Х_:Х₂—Х„ ₂рХ„ j.

м

Пусть теперь S(q, X) = (p,Y, R), т.е. головка сдвигается вправо. Тогда

Х)Х₂…X, iqXX, !■■ -Х„ XjX₂…X, jYpX,,Х„.

м

Этот переход отражает сдвиг головки в клетку / + 1. Здесь также есть два важных исключения.

Если i = п, то (/’+ 1)-я клетка содержит пробел и не является частью предыдущего МО. Таким образом,

X,X₂..X_n iqX„ |- Х,Х₂… Х„ jYpB. м

Если /’= 1 и Y= В, то символ В, записываемый вместо X_h присоединяется к беско­нечной последовательности пробелов слева и опускается в следующем МО. Таким образом,

qX,X₂…X_n b рХ₂…Х„.

м

Пример 8.2. Построим машину Тьюринга и посмотрим, как она ведет себя на типич­ном входе. Данная машина Тьюринга будет допускать язык {0ⁿlⁿ | п > 1}. Изначально на ее ленте записана Конечная последовательность символов 0 и 1, перед и за которыми на­ходятся бесконечные последовательности пробелов. МТ попеременно будет изменять О на X и 1 на Y до тех пор, пока все символы 0 и 1 не будут сопоставлены друг другу.

Более детально, начиная с левого конца входной последовательности, МТ циклично меняет 0 на X и движется вправо через все символы 0 и Г, пока не достигнет 1. Она ме­няет 1 на К и движется вправо через все символы К и 0, пока не найдет X. В этот момент она ищет 0 непосредственно справа и, если находит, меняет его на X и продолжает про­цесс, меняя соответствующую 1 на У.

Если непустой вход не принадлежит 0*1*, то МТ рано или поздно не сможет совер­шить следующий переход и остановится без допускания. Однако если она заканчивает работу, изменив все символы 0 на Л’ в том же цикле, в котором она изменила последнюю 1 на Y, то ее вход имеет вид 0^П1^П, и она его допускает. Формальным описанием данной МТ является

М= ({q₀, q,, <72, q₃, qA, {0, 1}, {0, l,X, Y, В}, 8, q₀, В, {q,}), где 5 представлена в таблице на рис. 8.9.

Состояние	0 1	Символ	У	В
Яо	(qhX,R) —	—	(Яз, Y, R)	—
Я1	(qj,0,R) (q2,Y,L)	—	(<q„ Y, R)	—
Я2	(Я2, 0, L) —	04o,X,R)	042,Y,L)	—
Яз	— —	—	(Яз, Y, R)	(qj, B, R)
Я4	— —	—	—	—

Рис. 8.9. Машина Тьюринга, допускающая {<У’I» | п > 1}

В процессе вычислений М часть ленты, на которой побывала ее головка, всегда содер­жит последовательность символов, описываемую регулярным выражением                         Таким образом, там есть последовательность символов X, заменивших 0, за которыми идут сим­волы 0, еще не измененные наХ Затем идут символы У, заменившие 1, и символы 1, еще не замененные Y. За этой последовательностью еще могут находиться символы 0 и 1.

Состояние q₀ является начальным, и в него же переходит М, возвращаясь к крайнему слева из оставшихся символов 0. Если М находится в состоянии q₀ и обозревает 0, то в со­ответствии с правилами (см. рис. 8.9) она переходит в состояние q_t, меняет 0 наХч сдвига­ется вправо. Попав в состояние q_it М продолжает движение вправо через все символы 0 и У. Если М видит X или В, она останавливается («умирает»). Однако, если М в состоянии q, видит 1, она меняет ее на У, переходит в состояние q₂ и начинает движение влево.

Находясь в состоянии q₂, М движется влево через все символы 0 и Y. Достигая край­него справа X, который отмечает правый конец блока нулей, измененных на X, М воз­вращается в состояние q₀ и сдвигается вправо. Возможны два случая.

1. Если Мвидит 0, то она повторяет описанный только что цикл.
2. Если же М обозревает Y, то она уже изменила все нули на X. Если все символы 1 за­менены Y, то вход имел вид 0^П1^П, и М должна допускать. Таким образом, М перехо­дит в состояние q₃ и начинает движение вправо по символам Y. Если первым после Y появляется пробел, то символов 0 и 1 было поровну, поэтому М переходит в состоя­ние q₄ и допускает. Если же М обнаруживает еще одну 1, то символов 1 слишком много, и М останавливается, не допуская. Если М находит 0, то вход имеет ошибоч­ный вид, и М также «умирает».

Приведем пример допускающего вычисления М на входе 0011. Вначале М находится в состоянии q₀, обозревая 0, т.е. начальное МО имеет вид <7₀0011. Полная последователь­ность переходов образована следующими МО.

<7оОО 11 |-^7/011 |- XOq, 11 j- Xq₂0Y\ |- q₂X0Y\ |- Xq₀OY\ j- XXq_tYl (- XXYq,\ (- XXq₂YY f- Xq^XYY (- XXq₀YY h XXYq₃Y |- XXYYq₃B XXYYBq₄B

Рассмотрим поведение M на входе 0010, который не принадлежит допускаемому языку.

<7₀0010 Xqу010 |- XOq, 10 [- Xq₂0Y0 [- qXOYO |-

Xq_o0Y0 h XXq,Y0 [- XXYqfi |- XXY0q,B

Это поведение похоже на обработку входа 0011 до МО XXYq,0, где М впервые обозрева­ет последний 0. М должна двигаться вправо, оставаясь в состоянии q_t, что приводит к МО XXY0q,B. Однако у Мв состоянии qi по символу В перехода нет, поэтому она оста­навливается, не допуская.

8.2.4. Диаграммы переходов для машин Тьюринга

Переходы машин Тьюринга можно представить графически, как и переходы МП- автоматов. Диаграмма переходов состоит из множества узлов, соответствующих состояни­ям МТ. Дуга из состояния q в состояние р отмечена одним или несколькими элементами вида X/ YD, где X и Y— ленточные символы, a D — направление (L или R). Таким образом, если 8(q, Х)= (p,Y, D), то отметка X/ YD находится на дуге из q в р. Направление на диа­граммах представляется не буквами LnR,a стрелками <— и —», соответственно.

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

Пример 8.3. На рис. 8.10 представлена диаграмма переходов для машины Тьюринга из примера 8.2. Ее функция переходов изображена на рис. 8.9. □

Пример 8.4. Сегодня машины Тьюринга рассматриваются чаще всего в качестве «распознавателей языков» или, что равносильно, «решателей проблем». Однако сам

Тьюринг рассматривал свою машину как вычислитель натуральнозначных функций. В его схеме натуральные числа представлялись в единичной системе счисления, как бло­ки из одного и того же символа, и машина вычисляла, изменяя длину блоков или строя новые блоки где-нибудь на ленте. В данном простом примере будет показано, как ма­шина Тьюринга может вычислить функцию -, которая называется монусом (monus) или усеченной разностью (proper subtraction) и определяется соотношением т — п — гаах(/и — п, 0), т.е. т — п есть т-п, если т > п, и 0, если т < п.

Г/Г— 0/0-                   г/г<- Х/Х-+

МТ, выполняющая эту операцию, определяется в виде М= ({go, q_h …, q₆), {0, 1}, {0, 1, В}, S, q₀, В). Отметим, что, поскольку МТ не используется для допускания входа, множество допус­кающих состояний не рассматривается. М начинает с ленты, состоящей из О»¹10″ и про­белов вокруг, и заканчивает лентой cm — п символами 0, окруженными пробелами.

М циклически находит крайний слева из оставшихся 0 и заменяет его пробелом. За­тем движется вправо до 1. Найдя 1, М продолжает движение вправо до появления 0, ко­торый меняется на 1. Затем М возвращается влево в поисках крайнего слева 0, который идентифицируется после того, как М выходит на пробел и сдвигается вправо на одну клетку. Повторения заканчиваются в одной из следующих ситуаций.

Г/Г-

‘ г

Г/Г- Рис. 8.10. Диаграмма переходов МТ, допускающая цепочки вида ff’l»

1. В поисках 0 справа М встречает пробел. Это значит, что все п нулей в 0″ изменены на 1, и п+ 1 нулей в О»¹ заменены пробелами. Тогда М изменяет п + 1 единицу на пробелы и добавляет 0, оставляя т-п нулей на ленте. Поскольку в этом случае т > п, то т — п = т — п.
2. Начиная цикл, М не может найти 0, чтобы заменить его пробелом, поскольку первые т нулей уже изменены на В. Это значит, что п>т,пт — и = 0. М заменяет все ос­тавшиеся символы 1 и 0 пробелами и заканчивает работу с пустой лентой.

На рис. 8.11 представлены правила функции переходов S, а на рис. 8.12— ее диа­грамма. Роль каждого из семи ее состояний описывается следующим образом.

Состояние	0	Символ 1	В
Яо	(Яь В, R)	(Я5, В, R)	—
Я1	(Я,, 0, R)	(Я2, 1 ,Ю	—
Я2	(Яз, 1 ,L)	(Я2,1 ,R)	(Я4,В,1)
Яз	(Яз, 0, L)	(Яз, 1 ,L)	(Яо, В, R)
Я4	(Я4, 0, L)	(Я4, В, L)	(Яб, 0, R)
Яз	(Я5, в, R)	(Я5, В, R)	(Яб, в, R)
Яб	—	—	—

Рис. 8.11. Машина Тьюринга, вычисляющая функцию усеченной разности

S/S- 1 /В-                               1 /В- Рис. 8.12. Диаграмма переходов для МТ из примера 8.4

q₀ — данное состояние начинает цикл и прерывает его, когда нужно. Если М обозревает О, цикл должен повториться. О меняется на В, головка сдвигается вправо, и М пере­ходит в состояние qj. Если же М обозревает 1, то все возможные соответствия меж­ду двумя группами нулей на ленте установлены, и М переходит в состояние q_} для опустошения ленты.

q 1 — в этом состоянии М пропускает начальный блок из 0 в поисках 1. Найдя ее, М пере­ходит в состояние q₂.

q₂ — М движется вправо, пропуская группу из 1 до появления 0. 0 меняется на 1, головка сдвигается влево, и М переходит в состояние q₃. Однако возможно также, что после блока из единиц символов 0 уже не осталось. Тогда М в состоянии q₂ обнаруживает В. Возникает ситуация 1, описанная выше, где п нулей второго блока использованы для удаления п из т нулей первого блока, и вычитание почти закончено. М перехо­дит в состояние q₄, предназначенное для преобразования всех 1 в пробелы, а одного пробела — в 0.

q₃ — М движется влево, пропуская 0 и 1 до появления пробела. Тогда М сдвигается

вправо и возвращается в состояние q₀, начиная новый цикл. q₄ — вычитание закончено, но один лишний 0 из первого блока был ошибочно заменен пробелом. М движется влево, заменяя все 1 пробелами, до появления В. Последний меняется на 0, и М переходит в состояние q₆, где и останавливается. q₅ — это состояние достигается из q₀, если обнаруживается, что все 0 из первого блока заменены пробелами. В случае, описанном выше в 2, усеченная разность равна 0. М заменяет все оставшиеся 0 и 1 пробелами и переходит в состояние q₆. q₆ — единственной целью этого состояния является разрешить М остановиться после выполнения работы. Если бы вычисление разности было подпрограммой другой, более сложной функции, то qe начинало бы следующий шаг этого более объемного вычисления.

□

8.2.5. Язык машины Тьюринга

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

Более формально, пусть М = (Q, 2, Г, 8, q₀, В, F) — машина Тьюринга. Тогда L(M)

представляет собой множество цепочек w из 2*, для которых q₀w |- ар(3 при некотором состоянии р из F и произвольных ленточных цепочках а и /3. Это определение было при­нято при обсуждении машины Тьюринга в примере 8.2, допускавшей цепочки вида 0″1^п.

Языки, допустимые с помощью машин Тьюринга, часто называются рекурсивно пе­речислимыми , или РП-языками. Термин «рекурсивно перечислимые» происходит от вы­числительных формализмов, предшествовавших машинам Тьюринга, но определявших тот же класс языков или арифметических функций. Обсуждение источников этого тер­мина представлено во врезке в разделе 9.2.1.

Соглашения по обозначениям машин Тьюринга

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

• Строчные буквы из начала алфавита обозначают входные символы.
• Прописные буквы, обычно из конца алфавита, используются для ленточных сим­волов, которые иногда могут быть и входными. Однако для пробела всегда ис­пользуется В.
• Строчные буквы из конца алфавита обозначают цепочки входных символов.
• Греческие буквы используются для цепочек ленточных символов.
• Буквы р, qи другие около них в алфавите обозначают состояния.

8.2.6. Машины Тьюринга и останов

Существует еще одно понятие «допустимости» для машин Тьюринга — допустимость по останову. Говорят, что машина Тьюринга останавливается, если попадает в состоя­ние q, обозревая ленточный символ X, и в этом положении нет переходов, т.е. S(q, X) не определено.

Пример 8.5. Машина Тьюринга М из примера 8.4 была построена для того, чтобы допускать язык; она не рассматривалась с точки зрения вычисления функции. Заметим, однако, что М останавливается на всех цепочках из символов 0 и 1, поскольку независи­мо от входной цепочки машина М в конце концов удаляет вторую группу нулей^[5], если может ее найти, достигает состояния q₆ и останавливается. □

Всегда можно предполагать, что МТ останавливается, если допускает. Таким обра­зом, без изменения допускаемого языка можно сделать 8{q, X) неопределенной, если q — допускающее состояние. Итак,

• предполагается, что МТ всегда останавливается в допускающем состоянии.

К сожалению, не всегда можно потребовать, чтобы МТ останавливалась, если не до­пускает. Язык машины Тьюринга, которая в конце концов останавливается независимо от того, допускает она или нет, называется рекурсивным, и его важные свойства будут рассматриваться, начиная с раздела 9.2.1. Машина Тьюринга, которая всегда останавли­вается, представляет собой хорошую модель «алгоритма». Если алгоритм решения дан­ной проблемы существует, то проблема называется «разрешимой», поэтому машины

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

8.2.7. Упражнения к разделу 8.2

Укажите конфигурации МТ (рис. 8.9) при обработке следующего входа:

а) (*) 00;

б) 000111; в) 00111.

(!) Постройте машины Тьюринга для следующих языков:

а) (*) множество цепочек с одинаковыми количествами символов 0 и 1;

б)    {aⁿb^ac^a\n> 1};

в) {ww^R | w — произвольная цепочка из символов 0 и 1}.

Постройте машину Тьюринга, которая на вход получает натуральное число N и добавляет к нему 1 в двоичной записи. Точнее, изначально на ленте стоит знак $, за которым записано N в двоичном виде. Вначале головка в состоянии д₀ обозревает $. Ваша машина должна остановиться с двоичной записью N+ 1 на ленте, обозревая ее крайний слева символ и находясь в состоянии q_f. При

необходимости можно удалить $, например, <у₀$10011 $<^10100 или *

<у₀$ 11111 h <7/100000:

а) укажите переходы вашей МТ и объясните назначение каждого состояния;

б) укажите последовательность МО вашей МТ при обработке входа $111.

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

Графиком функции / называется множество всех цепочек вида [x,y(x)], где х — неотрицательное целое число в двоичной записи, a fix) — значение функции / на аргументе х (также двоичное).

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

С помощью неформальных, но четких конструкций выполните следующее:

а) покажите, как по данной МТ, вычисляющей/ построить МТ, которая допус­кает график/в качестве языка;

б) покажите, как по данной МТ, допускающей график/ построить МТ, которая вычисляет /;

в) функция называется частичной, если она может быть неопределенной для некоторых аргументов. Распространяя идеи этого упражнения на частичные функции, мы не требуем, чтобы МТ, вычисляющая/ останавливалась, если ее вход лс— одно из чисел, для которых fix) не определена. Работают ли ва­ши конструкции для пунктов а и б, если функция /частична? Если нет, объ­ясните, как их нужно изменить, чтобы они работали.

8.2.5. Рассмотрим машину Тьюринга

М= ({q₀, q,, q₂, <?/}, {О, 1}, {0, 1, В}, 8, q₀, В, {qfi).

Неформально, но четко опишите язык ЦА/), если 5 состоит из следующего мно­жества правил:

а) (*) S(q₀, 0) = (q,, 1, R); 8(q_h 1) = (q₀, 0, /?); 8(q_h В) = (q_fi B, R)’

б)  8(q₀, 0) = (q„ B, R); 8(q₀, 1) = (q_h B, R); 8(q_h 1) = (q_h B, R); 8(q_h В) = (q_f, B, R);

в) (!) 8(q₀, 0) = (q_h 1, R); 8(q„ 1) = (q₂, 0, L)\ S(q₂, 1) = (q₀, 1, RУ, 8(qj,B) = (q_f,B,R).

8.3. Техника программирования машин Тьюринга

Наша цель — обосновать, что машину Тьюринга можно использовать для вычисле­ний так же, как и обычный компьютер. В конечном счете, мы хотим убедить вас, что МТ равна по своей мощи обычному компьютеру. В частности, она может выполнять некото­рые вычисления, имея на входе другие машины Тьюринга, подобно тому, как описанная в разделе 8.1.2 программа проверяла другие программы. Именно это свойство «интро- спективности» как машин Тьюринга, так и компьютерных программ позволяет доказы­вать неразрешимость проблем.

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

8.3.1. Память в состоянии

Конечное управление можно использовать не только для представления позиции в «программе» машины Тьюринга, но и для хранения конечного объема данных. Рис. 8.13 ил­люстрирует этот прием, а также идею многодорожечной ленты. При этом конечное управле­ние содержит не только «управляющее» состояние q но и три элемента данных А, В и С. Дан­ная техника не требует никакого расширения модели МТ; мы просто рассматриваем состоя­ние в виде кортежа. На рис. 8.13 состояние имеет вид \q, А, В, С]. Такой подход позволяет описывать переходы более систематично, что зачастую проясняет программу МТ.

Состояние	Ч
Память	А	В	С

Дорожка 1 Дорожка 2 Дорожка 3

Рис. 8.13. Машина Тьюринга с памятью в конечном управлении и несколькими дорожками

Пример 8.6. Построим МТ

м= (Q, {0, 1}, {0, 1, В), 5, [q₀, В], В, {[q,, В]}), которая запоминает в своем конечном управлении первый увиденный символ (0 или 1) и проверяет, не встречается ли он еще где-нибудь во входной цепочке. Таким образом, М допускает язык 0Г+10*. До пускание регулярных языков (вроде данного) не сужает воз­можностей машин Тьюринга, а служит лишь простым примером.

Множество состояний Q есть {q₀, qi} х {0, 1 ,В}, т.е. состояния рассматриваются как пары из двух следующих компонентов.

Управляющая часть (qo или qi) запоминает, что делает МТ. Управляющее состояние q₀ сигнализирует о том, что М еще не прочитала свой первый символ, a q_t — что уже прочитала, и проверяет, не встречается ли он где-нибудь еще, продвигаясь вправо до достижения пустой клетки.

В части данных хранится первый увиденный символ (0 или 1). Пробел В в этом ком­поненте означает, что никакой символ еще не прочитан.

Функция переходов <5 определена следующим образом.

5([q₀, В], а) = ([q_t, a], a, R) для а = 0 или а= 1. Вначале управляющим состоянием является q₀, а частью данных— В. Обозреваемый символ копируется во второй компонент состояния, и М сдвигается вправо, переходя при этом в управляющее со­стояние q_t.

5([q_h а], а) = ([q_h а], а , R), где а — «дополнение» а, т.е. О при а = 1 и 1 при а = 0. В состоянии qi машина М пропускает каждый символ 0 или 1, который отличается от хранимого в состоянии, и продолжает движение вправо.

3. <5{[q_t, a\, В) = ([q_h В], В, R) для a = О или а = 1. Достигая первого пробела, М перехо­дит в допускающее состояние [q_t, В].

Заметим, что М не имеет определения переходов <5([q_t, а], В) для а = 0 или а = 1. Таким об­разом, если М обнаруживает второе появление символа, который был записан в ее память конечного управления, она останавливается, не достигнув допускающего состояния. □

8.3.2. Многодорожечные ленты

Еще один полезный прием состоит в том, чтобы рассматривать ленту МТ как образован­ную несколькими дорожками. Каждая дорожка может хранить один символ (в одной клетке), и алфавит МТ состоит из кортежей, с одним компонентом для каждой «дорожки». Например, клетка, обозреваемая ленточной головкой на рис. 8.13, содержит символ [X, Y, Z). Как и па­мять в конечном управлении, множественные дорожки не расширяют возможностей машин Тьюринга. Это просто описание полезной структуры ленточных символов.

Пример 8.7. Типичное использование многодорожечных лент состоит в том, что од­на дорожка хранит данные, а другая — отметку. Можно отмечать каждый символ, ис­пользованный определенным образом, или небольшое число позиций в данных. Данный прием фактически применялся в примерах 8.2 и 8.4, хотя лента там и не рассматривалась явно как многодорожечная. В данном примере вторая дорожка используется явно для распознавания следующего языка, который не является контекстно-свободным.

Lwcw — {wcw | w принадлежит (0+1)⁺} Построим машину Тьюринга

М= (Q, Z, Г, <5, [q₀, В], [В, В], {[q₉, В]}), компоненты которой имеют следующий смысл.

Q— множество состояний, которое представляет собой {q_t,q₂, …,£/<*} х {0, 1, В), т.е. множество пар, состоящих из управляющего состояния q, и компонента данных 0, 1 или В. Вновь используется разрешенное выше запоминание символа в конечном управлении.

Г— множество ленточных символов {В, *} х {0, 1, с, В}. Первый компонент, т.е. дорож­ка, может быть пустым или «отмеченным», что представлено, соответственно, про­белом или *. Символ * используется для отметки символов первой и второй групп из 0 и 1, в итоге подтверждающей, что цепочки слева и справа от центрального мар­кера с совпадают. Второй компонент ленточного символа представляет то, чем как бы является сам по себе ленточный символ, т.е. [В, X] рассматривается как ленточ­ный символ X для Х= 0, 1, с, В. 2 — входными символами являются [В, 0] и [В, 1], которые, как только что указано, обо­значают, соответственно, 0 и 1. 5— функция переходов определена следующими правилами, в которых а и Ь могут обо­значать как 0, так и 1.

S([gi, В], [В, а\) = ([q₂, а], [*, а], R). В начальном состоянии М берет символ а (которым может быть 0 или 1), запоминает его в конечном управлении и переходит в управляющее состояние q₂. Затем «отмечает» обозреваемый символ, изменив его первый компонент с В на *, и сдвигается вправо.

<5([#2, я], [В, Ь]) = ([#2, а], [В, b], R). М движется вправо в поисках символа с. Напом­ним, что а и Ь независимо друг от друга могут быть 0 или 1, но не могут быть с.

8{[q₂, а], [В, с]) = (\q₃, а], [В, с], R). Обнаружив с, М продолжает двигаться вправо, но меняет управляющее состояние на q₃.

8({q₃, а], [*, Ь]) = ([q₃, а], [*, Ь], К). В состоянии q₃ продолжается пропуск всех отме­ченных символов.

5({q₃, а], [В, а]) = ([q₄, В], [*, а], L). Если первый неотмеченный символ, найденный М, совпадает с символом в ее управлении, она отмечает его, поскольку он является парным к соответствующему символу из первого блока нулей и единиц. М перехо­дит в управляющее состояние q₄, выбрасывая символ из управления, и начинает движение влево.

д(\д₄, В], [*, а]) = ({q₄. В], [*, а], L). На отмеченных символах Мдвижется влево.

S([q₄, В], [В, с]) = ([q₅, В], [В, с], L). Обнаружив символ с, М переходит в состояние q_s и продолжает движение влево. В состоянии q₅ она должна принять решение, зави­сящее от того, отмечен или нет символ непосредственно слева от с. Если отмечен, то первый блок из нулей и единиц уже полностью рассмотрен. Если же символ слева от с не отмечен, то М ищет крайний слева неотмеченный символ, запоминает его, и по­сле этого в состоянии qj начинается новый цикл.

8([q₅, В], [В, а]) = ([q₆, В], [В, а], L). Если символ слева от с не отмечен, начинается соответствующая ветка вычислений. М переходит в состояние q₆ и продолжает дви­жение влево в поисках отмеченного символа.

8{[q₆, В], [В, а]) = {[q₆, В], [В, а], L). Пока символы не отмечены, М остается в со­стоянии q₆ и движется влево.

8([q₆, В], [*, а]) = ([<?/, В], [В, а], R). Обнаружив отмеченный символ, М переходит в состояние qi и движется вправо, чтобы взять первый неотмеченный символ.

8([q₅, В], [*, а]) = ([q₇, В], [*, а], R). Теперь рассмотрим ветку вычислений, когда в состоянии q₃ непосредственно слева от с обнаружен отмеченный символ. Начинает­ся движение вправо в состоянии q₇.

S([q₇, В], [В, с]) = ([q_s, В], [В, с], R). В состоянии q₇ обозревается с. Происходит пере­ход в состояние q₈ и продолжается движение вправо.

8{[q_s, В], [*, а]) = ([q_s, В\, [*, a], R). В состоянии q₈ машина движется вправо, пропус­кая все отмеченные символы.

14. <5([g₈, В], [В, В]) = ([q₉, В], [В, В], R). Если М достигает пробела в состоянии q₈, не обнаружив ни одного неотмеченного символа, то она допускает. Если же она снача­ла находит неотмеченный символ 0 или 1, то блоки слева и справа от с не совпадают, и М останавливается без допускания.

□

8.3.3. Подпрограммы

Машины Тьюринга — это программы, и их полезно рассматривать как построенные из набора взаимодействующих компонентов, или «подпрограмм». Подпрограмма машины Тью­ринга представляет собой множество состояний, выполняющее некоторый полезный процесс. Это множество включает в себя стартовое состояние и еще одно состояние, которое не имеет переходов и служит состоянием «возврата» для передачи управления какому-либо множеству состояний, вызвавшему данную подпрограмму. «Вызов» подпрограммы возникает везде, где есть переход в ее начальное состояние. Машины Тьюринга не имеют механизма для запоми­нания «адреса возврата», т.е. состояния, в которое нужно перейти после завершения подпро­граммы. Поэтому для реализации вызовов одной и той же МТ из нескольких состояний мож­но создавать копии подпрограммы, используя новое множество состояний для каждой копии. «Вызовы» ведут в начальные состояния разных копий подпрограммы, и каждая копия «возвращает» в соответствующее ей состояние.

Пример 8.8. Построим МТ для реализации функции «умножение». Наша МТ начина­ет с 0^т 10″ 1 на ленте и заканчивает с 0^ШП. Опишем вкратце ее работу.

В начале каждого из т циклов работы лента содержит одну непустую цепочку вида 0⁽10^п10^кп для некоторого к¹.

За один цикл 0 из первой группы меняется на В, и п нулей добавляются к последней группе, приводя к цепочке вида 0’~¹10ⁿ10^(k+l)n.

В результате группа из п нулей копируется т раз с изменением каждый раз одного 0 в первой группе на В. Когда первая группа нулей целиком превратится в пробелы, в последней группе будет тп нулей.

Заключительный шаг — заменить пробелами 10″ 1 в начале, и работа закончена. «Сердцем» этого алгоритма является подпрограмма, которая называется Сору. Она

реализует шаг 2, копируя блок из п нулей в конец. Точнее, Сору преобразует МО вида 0^m«^kl_?/0ⁿ10^{(k 1)11} в МО 0^m~^kl<5^,j0ⁿ10^kn. Переходы подпрограммы Сору представлены на рис. 8.14. Она заменяет первый 0 маркером X, в состоянии q₂ движется вправо до появ­ления пробела, копирует в эту клетку 0, и в состоянии q₃ движется влево, пока не появит­ся маркер X. На маркере она переходит вправо и возвращается в q_t. Она повторяет дан­ный цикл до тех пор, пока в состоянии q, не встретит 1 вместо 0. Тогда она использует состояние q₄ для обратной замены маркеров Xнулями и заканчивает в состоянии q_s.

1/1 <-

Х/0*

Рис. 8.14. Подпрограмма Сору

О/О’

В/В­

Начало

О/в-

Копирование I

о/о-

в/в-

о/в-

Рис. S./5. Полная программа умножения использует подпрограмму Сору

Вся машина Тьюринга для умножения начинает в состоянии q₀. Вначале она за не­сколько шагов переходит от МО <g^r₍,0^rn10ⁿl к МО 0^{m l} 1с//0^п 1. Необходимые переходы пока­заны на рис. 8.15 слева от вызова подпрограммы; в них участвуют только состояния q₀ и q₆.

0/0-

Справа от вызова подпрограммы (см. рис. 8.15) представлены состояния q-r-qn■ Со­стояния q₇, qs и q₉ предназначены для получения управления после того, как Сору ско­
пировала блок из п нулей и находится в МО 0^{m k} 1 t/jOⁿ ] 0^kn. Эти состояния приводят к конфигурации ^₀0^{m k}10″0^kn. В этот момент опять начинается цикл, удаляется краинии слева 0 и вызывается Сору для нового копирования блока из п нулей.

Как исключение, в состоянии q₈ МТ может обнаружить, что все т нулей заменены пробелами, т.е. к = т. В данном случае производится переход в состояние qi₀. Это со­стояние с помощью состояния qn заменяет символы 10″1 в начале ленты пробелами, по­сле чего достигается состояние останова q_l2. В этот момент МТ имеет МО qaO™, и ее работа завершена. □

8.3.4. Упражнения к разделу 8.3

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

(!) Обычные операции в программах типа машин Тьюринга используют «сдвиг» («shifting over»). Предположим, в текущей позиции головки нужно создать до­полнительную клетку, в которую можно было бы записать некоторый символ. Однако изменять ленту таким способом нельзя. Придется сдвинуть содержимое ленты справа от головки на одну клетку вправо и затем вернуться к текущей по­зиции. Покажите, как выполнить данную операцию. Указание. Зарезервируйте специальный символ для отметки позиции, в которую нужно вернуться.

(*) Постройте подпрограмму перемещения головки МТ из ее текущей позиции вправо с пропуском нулей до достижения первой 1 или пробела. Если текущая позиция не содержит 0, то МТ останавливается. Можно предполагать, что лен­точными символами являются только 0, 1 и В (пробел). Используйте получен­ную подпрограмму для построения МТ, допускающей все цепочки из 0 и 1, в которых нет двух 1 подряд.

8.4. Расширения базовой машины Тьюринга

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

Затем рассматриваются недетерминированные машины Тьюринга — расширение ос­новной модели, в котором разрешается совершать любой из конечного множества пере­ходов в данной ситуации. Это расширение в некоторых случаях также облегчает «прог­раммирование» машин Тьюринга, не добавляя ничего к распознавательной мощности ба­зовой модели.

8.4.1. Многоленточные машины Тьюринга

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

Вход (конечная последовательность символов) размещен на первой ленте.

Все остальные клетки всех лент содержат пробелы.

Конечное управление находится в начальном состоянии.

Головка первой ленты находится в левом конце входа.

Головки всех других лент занимают произвольное положение. Поскольку все ленты, кроме первой, пусты, начальное положение головок на них не имеет значения (все клетки «выглядят» одинаково).

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

Управление переходит в новое состояние, которое может совпадать с предыдущим.

На каждой ленте в обозреваемую клетку записывается новый символ. Любой из них может совпадать с символом, бывшим там раньше.

3. Каждая из ленточных головок сдвигается влево или вправо или остается на месте. Головки сдвигаются независимо друг от друга, поэтому разные головки могут дви­гаться в разных направлениях, а некоторые вообще оставаться на месте.

Формальная запись переходов не приводится — ее вид является непосредственным обобщением записи для одноленточной МТ, за исключением того, что сдвиги теперь обозначаются буквами L, R или S. Возможность оставлять головку на месте не была пре­дусмотрена для одноленточных МТ, поэтому в их записи не было S. Постарайтесь сами представить подходящую запись МО (конфигураций) многоленточных МТ; формально она здесь также не приводится. Многоленточные МТ, как и одноленточные, допускают, попадая в допускающее состояние.

8.4.2. Эквивалентность одноленточных и многоленточных машин Тьюринга

Напомним, что рекурсивно перечислимые языки определяются как языки, допускае­мые одноленточными МТ. Очевидно, что многоленточные МТ допускают все рекурсив­но перечислимые языки, поскольку одноленточная МТ является частным случаем мно­голенточной. Но существуют ли не рекурсивно перечислимые языки, допускаемые мно­голенточными МТ? Ответом является «нет», и мы докажем это, показав, как многолен­точная МТ имитируется с помощью одноленточной.

Теорема 8.9. Каждый язык, допускаемый многоленточной МТ, рекурсивно перечислим.

Доказательство. Идею доказательства иллюстрирует рис. 8.17. Предположим, что язык L допускается ^-ленточной МТ М. Она имитируется с помощью одноленточной МТ N, лента которой состоит из 2к дорожек. Половина этих дорожек содержит ленты маши­ны М, а каждая из дорожек второй половины содержит один-единственный маркер, ука­зывающий позицию, в которой в данный момент времени находится головка соответст­вующей ленты. Рис. 8.17 соответствует тому, что к = 2. Вторая и четвертая дорожки хра­нят содержимое первой и второй лент машины М, дорожка 1 хранит позицию головки на ленте 1, а дорожка 3 — позицию на ленте 2.

Для имитации перехода МТ М головка МТ N должна посетить к головочных марке­ров. Чтобы не «заблудиться», N должна помнить, сколько маркеров находятся слева от ее головки каждый раз; этот учет ведется с помощью компонента конечного управления N. После посещения каждого головочного маркера и запоминания обозреваемого символа в компоненте управления N знает, какие символы обозреваются каждой из головок М. N также знает состояние М, которое запоминается в конечном управлении N. Таким обра­зом, N знает, какой переход сделает М.

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

nJ

‘ Г

				X
	Л,			Ах		А>
						X
		В1		Bi		в>

Рис. 8.17. Имитация двухленточной МТ с помощью одноленточной

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

Напоминание о конечности

Обычное заблуждение — путать значение, конечное в каждый момент времени, с конеч­ным множеством значений. Конструкция сведения многих лент к одной помогает оценить разницу между этими «конечностями». В данной конструкции использованы дорожки на ленте для запоминания позиций ленточных головок. Почему нельзя записать эти пози­ции в виде целых чисел в конечное управление? Будучи небрежным, кто-то мог бы ут­верждать, что после п переходов головки МТ находятся в позициях, отличающихся не более, чем на п от начальной, и поэтому достаточно записать целые не больше п. Проблема состоит в том, что, хотя позиции конечны в каждый момент времени, все множество позиций может быть и бесконечным. Если состояние должно представлять любую позицию головки, то в состоянии должен быть компонент данных, имеющий любое целое в качестве значения. Из-за этого компонента множество состояний должно быть бесконечным, даже если только конечное число состояний используется в любой конечный момент времени. Определение же машин Тьюринга требует, что­бы множество состояний было конечным. Таким образом, запомнить позицию лен­точной головки в конечном управлении нельзя.

8.4.3. Время работы и конструкция „много лент к одной»

Здесь представлено понятие, которое в дальнейшем окажется чрезвычайно важным, а именно: «временная сложность», или «время работы» машины Тьюринга. Временем ра­боты машины Тьюринга на входе w называется число шагов, которые М совершает до останова. Если М не останавливается на w, то время работы бесконечно. Временная сложность МТ М есть функция Г(и), которая представляет собой максимум времени ра­боты М на w по всем входам w длины п. Для МТ, не останавливающихся на всех своих входах, Т(п) может быть бесконечным для некоторых или даже для всех п. Однако осо­бое внимание будет уделено машинам Тьюринга, которые обязательно останавливаются на всех своих входах, и в частности, тем машинам, которые имеют полиномиальную временною сложность. Они будут изучаться, начиная с раздела 10.1.

Конструкция теоремы 8.9 кажется неуклюжей. Действительно, построенной одно­ленточной МТ может понадобится гораздо больше времени для работы, чем много­ленточной. Однако время работы этих двух машин соразмерно в том смысле, что вре­мя работы одноленточной МТ есть не более чем квадрат времени работы многолен­точной. Хотя «возведение в квадрат» не является хорошей соразмерностью, оно сохраняет свойство времени работы быть полиномиальным. В главе 10 будут пред­ставлены следующие факты.

• Разница между полиномиальным временем и более высокими степенями его возрас­тания — это в действительности граница между тем, что можно решить с помощью компьютера, и тем, что практически нерешаемо.
• Несмотря на обширные исследования, время, необходимое для решения многих проблем, не удается определить точнее, чем «некоторое полиномиальное». Таким образом, когда изучается время, необходимое для решения некоторой проблемы, ис­пользование многоленточной или одноленточной МТ не является критичным.

Докажем, что время работы многоленточной МТ является не более чем квадратом времени работы одноленточной МТ.

Теорема 8.10. Время, необходимое одноленточной МТ N для имитации п переходов ^-ленточной МТ М, есть 0{п).

Доказательство. После п переходов машины М головочные маркеры не могут быть разделены более, чем 2п клетками. Таким образом, если N стартует на крайнем слева маркере, ей нужно сдвинуться не более, чем на 2п клеток вправо, чтобы найти все головочные маркеры. Затем ей нужно совершить проход влево, изменяя содержи­мое лент М и сдвигая головочные маркеры вправо или влево, если необходимо. Вы­полнение этого требует не более 2п сдвигов влево, плюс не более 2к переходов для изменения направления движения и записи маркера X в клетку справа (когда головка М сдвигается вправо).

Таким образом, число переходов N, необходимых для имитации одного из первых п переходов, не более An + 2к. Поскольку к — константа, не зависящая от числа имитируе­мых переходов, это чипло переходов есть О(п). Имитация п переходов требует времени не более, чем в п р’аз больше, т.е. 0(п²).

8.4.4. Недетерминированные машины Тьюринга

Недетерминированная машина Тьюринга (НМТ) отличается от изученных нами де­терминированных тем, что ее S(q, X) для каждого состояния q и ленточного символа X представляет собой множество троек

{(q_h Yj, Dj), (q₂, Y₂, D₂), …, (q_k, Y_k, D_k)}, где к— натуральное число. НМТ может выбирать на каждом шаге любую из троек для следующего перехода. Она не может, однако, выбрать состояние из одной тройки, лен­точный символ из другой, а направление из какой-нибудь еще.

Язык, допускаемый НМТ М, определяется по аналогии с другими недетерминированными устройствами, вроде НКА или МП-автоматов. Таким образом, М допускает вход w, если су­ществует некоторая последовательность выборов переходов, ведущая из начального МО с w на входе в МО с допускающим состоянием. Существование других выборов, которые не ве­дут в допускающее состояние, не имеет значения, как и для НКА или МП-автоматов.

Недетерминированные МТ допускают те же языки, что и детерминированные (или ДМТ, если нам нужно подчеркнуть их детерминированность). Доказательство основано на том, что для любой НМТ M_N можно построить ДМТ M_D, которая исследует конфигурации, достигаемые M_N с помощью любой последовательности переходов. Если M_D находит хотя бы одно МО с допускающим состоянием, то сама переходит в допускающее состояние. M_D должна помещать новые МО в очередь, а не в магазин, чтобы после некоторого конечного времени были проимитированы все последовательности длиной до к (к = 1,2, …).

Теорема 8.11. Если M_N— недетерминированная машина Тьюринга, то существует детерминированная машина Тьюринга Мц, у которой L(M_D) = L(M_N).

Доказательство. Построим А/« в виде многоленточной МТ, общий вид которой представлен на рис. 8.18. Первая лента M_D хранит последовательность МО M_N, включая состояние M_N. Одно МО M_N отмечено как «текущее»; следующие за ним МО должны быть исследованы после него. На рис. 8.18 третье МО отмечено символом х вместе с разделителем МО — символом *. Все МО слева от текущего уже исследованы, и в даль­нейшем их можно игнорировать.

Для обработки текущего МО машина M_D совершает следующие действия.

• M_D проверяет состояние и обозреваемый символ текущего МО. Информация о том, какие выборы перехода есть у M_N для каждого состояния и символа, хранится в ко­нечном управлении Мд. Если состояние в текущем МО является допускающим, то M_D допускает и прекращает имитацию.
• Если состояние в текущем МО не допускающее, а пара состояние-символ имеет к переходов, тоM_D использует свою вторую ленту для копирования МО и создания к копий этого МО в конце очереди МО на ленте 1.
• M_D изменяет каждое из этих к МО в соответствии с к различными выборами перехо­дов, которые есть у M_N из текущего МО.

Рис. 8.18. Имитация НМТ с помощью ДМТ

Очевидно, что имитация точна в том смысле, что M_D допускает только тогда, когда находит, что М_ы может перейти в допускающее МО. Однако нужно обосновать, что если M_N попадает в допускающее МО после п переходов, то M_D в конце концов породит это МО в качестве текущего и допустит.

Предположим, что m есть максимальное число выборов у M_N в любой конфигурации. Тогда существует одно начальное МО M_N, не более m МО, достижимых за 1 шаг, не бо­лее m² МО, достижимых за 2 шага, и т.д. Таким образом, после п переходов M_N может достичь не более 1 + m + m² + …+ mⁿ МО, что не превышает пт».

Порядок, в котором M_D исследует МО Мы, называется «поиск в ширину» («breadth first»), т.е. она исследует все МО, достижимые за 0 переходов (начальное МО), затем все МО, достижимые за 1 переход, за 2 перехода, и т.д. В частности, M_D сделает текущими все МО, достижимые не более, чем за п переходов, и создаст все следующие за ними МО, перед тем, как делать текущими МО, достижимые более, чем за п переходов.

Как следствие, допускающее МО M_N рассматривается M_D в числе первых пт^п МО. Нам нужно знать лишь то, что Мо рассматривает это МО через некоторое конечное вре­мя, и этой границы достаточно, чтобы убедиться, что допускающее МО в конце концов действительно рассматривается. Таким образом, если M_N допускает, то M_D также допус­кает. Поскольку по построению Мд допускает только потому, что допускает M_N, можно заключить, что L(M_D) = L(M_N). □

4. MD возвращается к отмеченному (текущему) МО, удаляет отметку и перемещает ее на следующее МО справа. Цикл повторяется с шага 1.

Отметим, что построенная детерминированная МТ может потребовать времени, экс­поненциально большего, чем время работы недетерминированной МТ. Неизвестно, явля­ется ли это экспоненциальное соотношение необходимым. Этому вопросу и некоторым его производным, связанным с поисками лучшего способа детерминированной имитации НМТ, посвящена глава 10.

8.4.5. Упражнения к разделу 8.4

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

Недетерминированная МТ М= ({q0, qi, q2], {0, 1}, {0, 1, В}, 8, q0, В, {q2}) пред­ставлена следующей функций переходов. 8 0 Символ 1 В qo {(qo, 1.Л)} {(q,, 0, Я)} 0 qi {(gt, 0, R), (q0, 0,1)} {(q„ 1, R), (go, 1,1)} {(42, В, Л)} qi 0 0 0

Покажите, какие МО достижимы из начального МО, если входом является сле­дующая цепочка:

а) (*) 01;

б)   001.

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

а) (*) язык всех цепочек из символов 0 и 1, содержащих некоторую подцепочку длиной 100, которая повторяется, причем не обязательно подряд. Формаль­но, данный язык есть множество цепочек из 0 и 1 вида wxyxz, где |х| = 100, а w, у и z имеют произвольную длину;

б) язык всех цепочек вида w_l#w₂#…#w_n для произвольного п, где каждая из w, есть цепочка из символов 0 и 1, причем для некоторого j цепочка wj является двоичной записью числа j;

в) язык всех цепочек того же вида, что и в п. б, но хотя бы для двух значений j цепочки Wj представляют собой двоичную запись j.

(!) Рассмотрим недетерминированную машину Тьюринга

М= ({qo, д„ q₂, q/}, {0, 1}, {0, 1, В}, 8, q₀, В, {q_f}).

Неформально, но ясно опишите язык L(M), если 8 состоит из следующих мно­жеств правил: 8(q₀,0) = {(q₀,\,R), (q_h\,R)), 8(q,, 1) = {(q₂,0,L)}, S(q₂,\) = {(qo, 1,R)}, 5(g_hB)={(q_hB, R)}.

(*) Рассмотрим недетерминированную МТ, лента которой бесконечна в обоих направлениях. В некоторый момент времени вся лента пуста, за исключением одной клетки, в которой записан символ $. Головка находится в некоторой пус­той клетке, а состоянием является q:

а) напишите переходы, позволяющие НМТ перейти в состояние р, обозревая $;

б) (!) предположим, что МТ детерминирована. Как бы вы позволили ей найти $ и перейти в состояние р!

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

В данном упражнении с помощью специальной 3-ленточной МТ реализуется магазин.

Первая лента используется только для хранения и чтения входа. Входной алфавит состоит из символа Т, который интерпретируется, как «вытолкнуть из магазина», и символов а и 6, интерпретируемых как «поместить а (соответственно, b) в магазин».

Вторая лента используется для запоминания магазина.

Третья лента является выходной. Каждый раз, когда из магазина выталкивается сим­вол, он записывается на выходную ленту вслед за ранее записанными.

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

На рис. 8.17 была представлена имитация ^-ленточной МТ с помощью однолен­точной в общем случае.

а) (*) Предположим, что данная техника использована для имитации 5-ленточ- ной МТ, ленточный алфавит которой состоит из 7 символов. Сколько лен­точных символов будет у одноленточной машины?

б) (*) Альтернативный способ имитации к лент с помощью одной состоит в ис­пользовании (к+ 1)-й дорожки для хранения позиций головок всех к лент, причем первые к дорожек имитируют к лент очевидным образом. Заметим, что с (к + 1 )-й дорожкой нужно быть аккуратным, чтобы различать головки и

допускать возможность того, что две и более головок могут находиться в од­ной клетке. Сокращает ли данный метод число ленточных символов, необхо­димых для одноленточной МТ? в) Еще один способ имитации к лент с помощью одной вообще не требует за­поминания позиций головок. Вместо этого (к+ 1)-я дорожка используется для отметки только одной клетки ленты. Каждая имитируемая лента все вре­мя позиционируется на своей дорожке так, что головка находится на отме­ченной клетке. Если к-ленточная МТ перемещает головку на ленте /, то ими­тирующая одноленточная МТ смещает все непустое содержимое /-й дорожки на одну клетку в противоположном направлении, так что клетка, обозревае­мая головкой /-й клетки в ^-ленточной машине, остается в отмеченной клет­ке. Помогает ли данный метод сократить число ленточных символов одно­ленточной МТ? Есть ли у него недостатки по сравнению с другими описан­ными здесь методами?

(!) Машина Тьюринга, называемая к-головочной, имеет к головок, читающих клетки на одной ленте. Переход такой МТ зависит от состояния и символов, обозреваемых головками. За один переход эта МТ может изменить состояние, записать новый символ в клетку, обозреваемую каждой из головок, и сдвинуть каждую головку влево, вправо или оставить на месте. Поскольку несколько го­ловок могут одновременно обозревать одну и ту же клетку, предполагается, что головки пронумерованы от 1 до к, и символ, который в действительности запи­сывается в клетку, есть символ, записываемый головкой с наибольшим номе­ром. Докажите, что множества языков, допускаемых А>головочными и обычны­ми машинами Тьюринга, совпадают.

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

8.5. Машины Тьюринга с ограничениями

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

Затем исследуются определенные виды многоленточных МТ, которые обобщают МП-автоматы. Во-первых, ленты МТ ограничиваются и ведут себя, как магазины. Во- вторых, ленты ограничиваются еще больше, становясь «счетчиками», т.е. они могут представлять лишь одно целое число, а МТ имеет возможность только отличать 0 от лю­бого ненулевого числа. Значение этих ограничений в том, что существует несколько очень простых разновидностей автоматов, обладающих всеми возможностями компью­теров. Более того, неразрешимые проблемы, связанные с машинами Тьюринга и описан­ные в главе 9, в равной мере относятся и к этим простым машинам.

8.5.1. Машины Тьюринга с односторонними лентами

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

В основе этой конструкции лежит использование двух дорожек на односторонней ленте. Верхняя дорожка представляет клетки исходной МТ, находящиеся справа от на­чальной позиции, и ее саму. Нижняя дорожка представляет позиции слева от начальной, но в обратном порядке. Точное упорядочение показано на рис. 8.19. Верхняя дорожка представляет клетки Х₀, X,, …, где Х₀— начальная позиция головки, Х₂, … — клет­ки справа от нее. Клетки X,, X ₂, и последующие представляют клетки слева от началь­ной позиции. Обратите внимание на * в левой клетке на нижней дорожке. Этот символ служит концевым маркером и предохраняет головку односторонней ленты от случайного выхода за левый конец ленты.

Х„	Xj	Х2
*	X 1	х2

Рис. 8.19. Односторонняя лента может имитировать двустороннюю бесконечную ленту

Можно усилить ограничение нашей машины Тьюринга, чтобы она никогда не запи­сывала пробелов. Это простое ограничение, вместе с лентой, бесконечной только в одну сторону, означает, что лента всегда представляет собой префикс из непустых символов, за которым следует бесконечная последовательность пробелов. Кроме того, крайний слева непустой символ всегда находится в начальной позиции ленты. В теоремах 9.19 и 10.9 будет видно, насколько полезно предполагать, что МО имеют именно такой вид.

Теорема 8.12. Каждый язык, допускаемый МТ М₂, допускается также МТ Mi со сле­дующими ограничениями.

Головка Mi никогда не смещается влево от своей начальной позиции.

М1 никогда не записывает пробелы.

Доказательство. Условие 2 обосновать легко. Введем новый ленточный символ В\ выполняющий роль пробела, но отличный от него. Таким образом, если М₂ имеет прави­ло S₂(q,X) = (р, В, D), изменим его на 8₂{q,X) = (р, В», D). Положим 8₂(q, В0 для любого состояния q равным S₂(q, В).

Условие 1 требует больших усилий. Пусть

M₂={Q₂, 2, Г₂,S₂, q₂, B,F₂)~ МТ М₂, модифицированная, как описано выше, т.е. она никогда не записывает пробел В. Построим

Mi = (Q,, 2 х [В], Г,, <5„ q₀, [В, В], F,), компоненты которой определены следующим образом.

Qz— состояниями М/ являются {q₀, q_t} U (Q2^х {U, L}), ^{т е}— начальное q₀, еще одно qi и

все состояния М₂ со вторым компонентом U или L (upper или lower — верхний или нижний). Второй компонент указывает на дорожку, в которой находится клетка, обозреваемая М₂ (см. рис. 8.19), т.е. U означает, что головка М₂ находится в на­чальной позиции или справа от нее, a L — что слева. Г/ — ленточными символами являются все пары символов из Г^, т.е. Г^ х Г₂. Входными символами М/ являются пары вида [а, В], где а из 2. Пробел М_: имеет пробелы в обоих компонентах. Кроме того, для каждого символа X из Г? в Г₇ есть пара [X, *], где * — новый символ, который отсутствует в Г^ и отмечает левый конец ленты М/. 8/ — переходы Mj определены следующим образом.

1- S/(q,/, [а, В}) = (q_h [а, *], R) для каждого а из 2. Первый переход машины М, помещает маркер * на нижнюю дорожку левой клетки. Состоянием становится q,, а головка сдвигается вправо, поскольку не может двигаться влево или оставаться на месте.

8i(q,, [X, В]) = ([<7₂, U], [X, В], L) для каждого X из Mi в состоянии q, устанавлива­ет начальное состояние М₂, возвращая головку в начальную позицию и изменяя со­стояние на [q₂, U], т.е. начальное состояние М₂ с головкой Mj на первой дорожке.

Если 8₂{q, X) = (p,Y, D), то для каждого Z из Г₂

8i{[q, U}, [X, Z]) = {\р, U], [Y, Z], D) и 8j([q, L], [Z,X])={[p, L], [Z,Y], D), где D — направление, противоположное D, т.е. L, если D = R, и R, если D = L. Если Mi не находится в крайней слева клетке, то она имитирует М₂ на подходящей для

этого дорожке — верхней, если вторым компонентом состояния является U, и ниж­ней— если L. Заметим, что, работая с нижней дорожкой, М, сдвигает головку в на­правлении, противоположном сдвигу головки М₂. Такой выбор направления естест­венен, поскольку левая половина ленты М₂ хранится в нижней дорожке Mi в обрат­ном направлении.

Если S₂(q, X) = (p,Y, К), то

S,([q, L], IX., *]) = St([q, U\, [X, *]) =([р, U\, [Г, *], R). Это правило распространяется на один случай обработки левого концевого марке­ра *. Если М₂ из начальной позиции движется вправо, то, независимо от того, была ли она раньше слева или справа от этой позиции (второй компонент состояния M_t может быть как L, так и U), Mi должна двигаться вправо и обрабатывать верхнюю дорожку. Таким образом, на следующем шаге Mi окажется в позиции, представ­ленной^ на рис. 8.19.

Если S₂(q, X) = (р, У, L), то

$,([<7, L], [X, *]) = 8i([q, U], [X, *]) = ([р, L], [Y, *], R). Это правило подобно предыдущему, но связано со случаем, когда М₂ сдвигается влево от своей начальной позиции. Mi должна двигаться вправо от своего концевого марке­ра, но обрабатывать нижнюю дорожку, т.е. клетку, представленнуюX., на рис. 8.19.

F1— множеством допускающих состояний является F₂ X {U, L}, т.е. все состояния M_h первым компонентом которых является допускающее состояние М₂. В момент до- пускания Mi может обрабатывать как верхнюю, так и нижнюю дорожку.

Доказательство теоремы по существу завершено. С помощью индукции по числу пе­реходов, совершаемых М₂, можно заметить, что M_t имитирует МО М₂ на своей ленте, ес­ли взять нижнюю дорожку, развернуть и дописать к ней верхнюю.^[6] Заметим также, что Mi попадает в одно из допускающих состояний тогда и только тогда, когда это же делает М₂. Таким образом, L(Mi) = L(M₂). □

8.5.2. Мультистековые машины

Теперь рассмотрим несколько вычислительных моделей, основанных на обобщениях ма­газинных автоматов. Вначале рассмотрим, что происходит, если МП-автомат имеет несколь­ко магазинов. Из примера 8.7 уже известно, что МТ может допускать языки, не допускае­мые никаким МП-автоматом с одним магазином. Однако оказывается, что если снабдить МП-автомат двумя магазинами, то он может допустить любой язык, допускаемый МТ.

Рассмотрим также класс машин, называемых «счетчиковыми машинами». Они обла­дают возможностью запоминать конечное число целых чисел («счетчиков») и совершать
различные переходы в зависимости от того, какие из счетчиков равны 0 (если таковые вообще есть). Счетчиковая машина может только прибавить 1 к счетчику или вычесть 1 из него, но отличить значения двух различных ненулевых счетчиков она не способна. Следовательно, счетчик похож на магазин с двухсимвольным алфавитом, состоящим из маркера дна (он появляется только на дне) и еще одного символа, который можно зано­сить в магазин и выталкивать из него.

Допустить/отвергнуть

Конечное управление

Рис. 8.20. Машина с тремя магазинами

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

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

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

Итак, типичное правило перехода для А-магазинной машины имеет вид

Вход

S(q, а,Х,,Х₂, …,Х_к) = (р, у,, у₂, …, у_к). Его смысл состоит в том, что, находясь в состоянии q, с X, на вершине /-го магазина, /= 1, 2, …, к, машина может прочитать на входе а (либо символ алфавита, либо £), пе­рейти в состояние р и заменить X, на вершине /-го магазина цепочкой у_ь /= 1, 2, …, к. Мультистековая машина допускает, попав в заключительное состояние.

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

Теорема 8.13. Если язык L допускается машиной Тьюринга, то L допускается двух­машинной машиной.

Доказательство. Основная идея состоит в том, что два магазина могут имитировать одну ленту машины Тьюринга, причем один магазин хранит содержимое ленты слева от головки, а второй— то, что находится справа, за исключением бесконечных цепочек пробелов, окружающих значащие символы ленты. Более детально, пусть L есть L(M) для некоторой (одноленточной) МТ М Наша двухмагазинная машина S выполняет следую­щие действия.

S начинает с маркером дна в каждом из магазинов. Этот маркер может быть стартовым символом для магазинов и не должен появляться больше нигде в магазине. В дальней­шем будем говорить, что «магазин пуст», когда он содержит лишь маркер дна.

Пусть и<$ является входом S. S копирует w в первый магазин, прекращая копирова­ние, прочитав маркер конца входа.

S выталкивает каждый символ по очереди из первого магазина и помещает его во второй магазин. Теперь первый магазин пуст, а второй содержит w с ее левым кон­цом на вершине.

S переходит в начальное (имитируемое) состояние М. Первый магазин S пуст, свиде­тельствуя о том, что у Мелева от головки нет ничего, кроме пробелов. Второй мага­зин S содержит w, отражая тот факт, что справа от головки М находится w.

S имитирует переход М следующим образом:

а) S знает состояние М, скажем, q, поскольку S имитирует состояние М в своем собственном конечном управлении;

б) S знает символ X, обозреваемый головкой М; это символ на вершине второго магазина S. Как исключение, если второй магазин содержит только маркер дна, то М только что переместилась на пробел; S интерпретирует символ, обозреваемый М, как пробел;

в) итак, S знает следующий переход М;

г) следующее состояние М записывается в компоненте конечного управления S вместо предыдущего состояния;

д) если М меняет X на Y и сдвигается вправо, то S помещает Y в свой первый магазин, имитируя то, что Y теперь слева от головки М. X выталкивается из второго магазина S. Однако есть два исключения.

Если второй магазин содержит только маркер дна (следовательно, X— пробел), то второй магазин не изменяется; М сдвинулась еще на один пробел вправо.

Если Y— пробел, и первый магазин пуст, то этот магазин остается пус­тым. Причина в том, что слева от головки М находятся только пробелы;

е) если М меняет X на Y и сдвигается влево, то S выталкивает символ с вершины первого магазина, скажем, Z, затем меняет X на ZY во втором магазине. Это изменение отражает, что символ Z, ранее расположенный слева от головки М, теперь обозревается ею. Как исключение, если Z является маркером дна, то S должна поместить BY во второй магазин, не выталкивая ничего из первого.

6. Sдопускает, если новое состояние М является допускающим. В противном случаеS имитирует еще один переход Мтаким же способом.

8.5.3. Счетчиковые машины

Счетчиковую машину можно представить одним из двух способов.

Счетчиковая машина имеет такую же структуру, как и мультистековая (см. рис. 8.20), но вместо магазинов у нее счетчики. Счетчики содержат произвольные неотрицательные целые числа, но отличить можно только ненулевое от нулевого. Таким образом, переход счетчиковой машины зависит от ее состояния, входного символа и того, какие из счетчиков являются нулевыми. За один переход машина может изменить состояние и добавить или отнять 1 от любого из счетчиков. Однако счетчик не может быть отрицательным, поэтому отнимать 1 от счетчика со значени­ем 0 нельзя.

Счетчиковая машина также может рассматриваться, как мультистековая машина со следующими ограничениями:

а) есть только два магазинных символа, Z₀ {маркер дна) и X;

б) вначале Z₀ находится в каждом магазине;

в) Z₀ можно заменить только цепочкой видаXZ₀ для некоторого / > 0;

г) X можно заменить только цепочкой видаХ для некоторого i > 0. Таким обра­зом, Z₀ встречается только на дне каждого магазина, а все остальные симво­лы (если есть) — это символы X.

Для счетчиковых машин будем использовать определение 1, хотя оба они, очевидно, задают машины одинаковой мощности. Причина в том, что магазин XZ₀ может быть идентифицирован значением /. В определении 2 значение 0 можно отличить от осталь­ных, поскольку значению 0 соответствует Z₀ на вершине магазина, в противном случае там помещается X. Однако отличить два положительных числа невозможно, поскольку обоим соответствует X на вершине магазина.

8.5.4. Мощность счетчиковых машин

О языках счетчиковых машин стоит сделать несколько очевидных замечаний.

• Каждый язык, допускаемый счетчиковой машиной, рекурсивно перечислим. При­чина в том, что счетчиковые машины являются частным случаем магазинных, а магазинные — частным случаем многоленточных машин Тьюринга, которые по теореме 9 допускают только рекурсивно перечислимые языки.
• Каждый язык, допускаемый односчетчиковой машиной, является КС-языком. За­метим, что счетчик, с точки зрения определения 2, является магазином, поэтому односчетчиковая машина представляет собой частный случай одномагазинной, т.е. МП-автомата. Языки односчетчиковых машин допускаются детерминирован­ными МП-автоматами, хотя доказать это на удивление сложно. Трудность вызы­вает тот факт, что мультистековые и счетчиковые машины имеют маркер $ в конце входа. Недетерминированный МП-автомат может «догадаться», что он ви­дит последний входной символ, и следующим будет маркер. Таким образом, яс­но, что недетерминированный МП-автомат без концевого маркера может имити­ровать ДМП-автомат с маркером. Однако доказать, что ДМП-автомат без конце­вого маркера может имитировать ДМП-автомат с маркером, весьма трудно, и мы этого не делаем.

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

Теорема 8.14. Каждый рекурсивно перечислимый язык допускается трехсчетчиковой машиной.

Доказательство. Начнем с теоремы 8.13, утверждавшей, что каждый рекурсивно перечислимый язык допускается двухмагазинной машиной. С ее использованием нам достаточно показать, как магазин имитируется с помощью счетчиков. Предположим, магазинная машина использует г — 1 ленточных символов. Можно обозначить символы цифрами от 1 до г — 1 и рассматривать магазин XiX₂…X„ как целое число по основа­нию г, т.е. этот магазин (его вершина, как обычно, слева) представлен целым числом Х„г»‘¹ + Х_п_,г^а~² + … + X₂r + X,.

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

Операции над магазином можно разделить на три вида: вытолкнуть верхний символ из ма­газина, изменить магазинный символ и поместить символ в магазин. Переход двухмагазинной машины может вовлекать несколько таких операций; в частности, замену верхнего символа X цепочкой символов нужно разделить на замену X и затем помещение дополнительных симво­лов в магазин. Эти операции выполняются над магазином, который представлен числом /, следующим образом. Заметим, что для выполнения операций, требующих подсчета чисел от О до г-1, можно использовать конечное управление мультистековой машины.

• ‘ Для выталкивания из магазина нужно изменить / на /У/^—, отбрасывая остаток, которым является Х[. Начиная с нулевого значения третьего счетчика, число i несколько раз сокращается на г, а третий счетчик увеличивается на 1. Когда счетчик, первоначаль­но имевший значение /, достигает 0, происходит остановка. Затем исходный счетчик увеличивается на 1 и третий счетчик уменьшается на 1 до тех пор, пока третий счет­чик снова не станет нулевым. В этот момент счетчик, в котором вначале было /, со­держит иг.
• Для изменения Хна К на вершине магазина, представленного целым /, числоiувели­чивается или уменьшается на небольшую величину, заведомо не больше г. Если Yи X рассматриваются как цифры, иY>X,то / увеличивается наY-X;еслиY < X, то / уменьшается на Х-
• Для помещения X в магазин, содержащий /, нужно поменять / наir + X. Вначале ум­ножаем / на г. Для этого несколько раз уменьшаем значение / на 1 и увеличиваем третий счетчик (который, как всегда, начинается с 0) на г. Когда исходный счетчик достигнет 0, в третьем счетчике будетТретий счетчик копируется в исходный и вновь обнуляется, как в п. 1. Наконец, исходный счетчик увеличивается на А».

Для завершения конструкции нужно инициализировать счетчики, чтобы имитировать магазины из их начального состояния, в котором они содержат только начальный символ двухмагазинной машины. Этот шаг реализуется путем увеличения двух основных счет­чиков на некоторое число от 1 до г — 1, соответствующее начальному символу. □

Теорема 8.15. Каждый рекурсивно перечислимый язык допускается двухсчетчиковой машиной.

Доказательство. С учетом предыдущей теоремы нужно лишь показать, как имитиро­вать три счетчика с помощью двух. Идея состоит в том, чтобы представить три счетчика, скажем, i,j и к, одним целым числом. Этим числом будет т = 2’3^J5^k. Один счетчик будет хранить это число, а второй использоваться в качестве вспомогательного для умножения и деления т на одно из трех простых чисел 2, 3 или 5. Для имитации трехсчетчиковой машины нужно реализовать следующие операции.

1. Увеличить i,j и/иЛи к. Для того чтобы увеличить / на 1, нужно умножить т на 2. В тео­реме 8.14 уже показано, как умножить содержимое счетчика на константу г, используя второй счетчик. Аналогично j увеличивается путем умножения т на 3, а к — на 5.

• Различить, какие из чисел, /’,jили к, равны 0. Для того чтобы выяснить, что / = 0, нужно определить, делится ли т без остатка на 2. Число т копируется во второй счетчик с использованием состояния машины, чтобы запомнить, уменьшено т чет­ное или нечетное число раз. Если т уменьшено нечетное число раз к тому моменту, когда оно стало равно 0, тоi = В таком случае т копируется из второго счетчика в первый. Аналогично, равенство j = 0 проверяется путем определения, делится ли т на 3, а к = 0 — делится ли оно на 5.
• Уменьшитьi,jи/или к. Для этого т делится на 2, 3 или 5, соответственно. В доказа­тельстве теоремы 14 описано, как выполнить деление на любую константу с ис­пользованием дополнительного счетчика. Трехсчетчиковая машина не может уменьшить число 0 (это ошибка, ведущая к останову без допускания), поэтому если т не делится нацело на соответствующую константу, то имитирующая двухсчетчи-

ковая машина также останавливается без допускания. □

8.5.5. Упражнения к разделу 8.5

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

а) (*) {0ⁿl^m\п>т> 1};

б) {0ⁿl^m| 1 <п<т};

в) (*!) {d&c^k | / =у или / =

г) (!!)    (/=_/’ или / = к или j = к].

(!!) Цель этого упражнения — показать, что мощность односчетчиковых машин с маркером конца входа не превосходит мощности детерминированных МП- автоматов. L$ — это конкатенация языка L с языком, содержащим одну- единственную цепочку $, т.е. /.$ состоит из всех строк w$, где w принадлежит L. Покажите, что если язык L$ допускается ДМП-автоматом, где $ — концевой маркер, не встречающийся в цепочках из L, то L также допускается некоторым ДМП-автоматом. Указание. Этот вопрос совпадает с вопросом замкнутости языков, допускаемых ДМП-автоматами, относительно операции L/a, определен­ной в упражнении 4.2.2. Нужно модифицировать ДМП-автомат Р для L% путем замены каждого из его магазинных символов X всеми возможными парами (X, S), где S есть множество состояний. Если Р имеет магазин XiX₂…X„, то по­строенный для L ДМП-автомат имеет магазин (X,, S,)(X₇, S₂)…(X„, S„), где каж­дое Si есть множество состояний q, в которых Р. начав с МО (q, a,X,X_l4…X„), допускает.

8.6. Машины Тьюринга и компьютеры

Теперь сравним машины Тьюринга с обычным компьютером. Эти модели кажутся совершенно разными, но они допускают одни и те же языки — рекурсивно перечисли­мые. Поскольку понятие «обычный компьютер» математически не определено, аргумен­тация данного раздела не является формальной. Нам приходится обращаться к интуиции читателя по поводу того, что могут компьютеры, в частности, если рассматриваемые числа превосходят обычные пределы, обусловленные архитектурой компьютеров (например, 32-битовым представлением чисел). Утверждения данного раздела можно разделить на две части.

Компьютер может имитировать машину Тьюринга.

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

8.6.1. Имитация машины Тьюринга на компьютере

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

Серьезный вопрос возникает, когда мы решаем, как программа должна имитировать ленту машины Тьюринга. Эта лента может стать бесконечно длинной, но память компь­ютера — главная память, диск или другие устройства — конечна. Можно ли проимити- ровать бесконечную ленту с помощью фиксированного объема памяти?

Если у нас нет возможности заменять запоминающие устройства, то проимитировать действительно нельзя; в таком случае компьютер был бы конечным автоматом, и допус­кал бы только регулярные языки. Однако обычные компьютеры имеют заменяемые за­поминающие устройства, например, «Zip»-диски. В действительности обычный жесткий диск можно снять и заменить пустым, но идентичным диском.

Поскольку очевидного предела на количество используемых дисков нет, будем счи­тать, что доступны столько дисков, сколько может потребоваться компьютеру. Тогда эти диски можно разместить в двух магазинах (рис. 8.21). Один магазин содержит данные в удаленных клетках ленты машины Тьюринга, расположенных слева от ее головки, а дру­гой — в дальних клетках справа от головки. Чем дальше в магазине расположены дан­ные, тем дальше они от головки на ленте.

Лента слева от головки      Лента справа от головки Рис. 8.21. Имитация машины Тьюринга на обычном компьютере

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

Аналогично, если ленточная головка МТ достигает удаленных клеток, не представлен­ных на текущем смонтированном диске, то печатается сообщение «обмен справа». Человек перемещает текущий диск на вершину левого магазина и монтирует на компьютер диск с вершины правого магазина. Ситуация, когда какой-либо магазин пуст, а компьютер требу­ет, чтобы диск из него был смонтирован, означает, что МТ достигла области пробелов на ленте. В этом случае оператору придется купить новый диск и смонтировать его.

8.6.2. Имитация компьютера на машине Тьюринга

Нужно также провести обратное сравнение: существуют ли вещи, которые может сделать обычный компьютер, а машина Тьюринга— нет. Важным вторичным вопросом является вопрос, может ли компьютер делать определенные вещи существенно быстрее, чем машина Тьюринга. В этом разделе обосновывается, что МТ может имитировать компьютер, а в разделе 8.6.3 — что эта имитация может быть достаточно быстрой в том смысле, что «всего лишь» полиномиальная зависимость разделяет время работы компь­ютера и МТ для решения какой-либо проблемы. Напомним читателю еще раз, что суще­ствуют немаловажные причины считать подобными все времена работы, лежащие в пре­делах полиномиальной зависимости друг от друга, тогда как экспоненциальные отличия во времени работы «слишком велики». Теория, в которой проводится сравнение полино­миального и экспоненциального времени работы, будет рассмотрена в главе 10.

Проблема очень больших ленточных алфавитов

Доводы раздела 8.6.1 становятся сомнительными, если число ленточных символов на­столько велико, что код одного ленточного символа не решается на диске. Для этого нужно действительно очень много ленточных символо,в, поскольку 30-гигабайтный диск, например, может представить любой из 2^24000000000f⁾ символов. Аналогично, чис­ло состояний могло бы быть настолько большим, что состояние нельзя было предста­вить, используя целый диск.

Для одного из разрешений этой проблемы следует ограничить число ленточных сим­волов, используемых МТ. Любой ленточный алфавит можно закодировать в двоич­ном виде. Таким образом, любая МТ М может быть проимитирована с помощью дру­гой МТ М\ использующей только ленточные символы 0, 1 и б. Однако у М’ должно быть очень много состояний, поскольку для имитации перехода М МТ М’ должна сканировать ее ленточный символ и запомнить в своем конечном управлении все би­ты, показывающие, какой ленточный символ сканируется. Таким же образом мы сталкиваемся с огромными множествами состояний, и компьютер, который имитиру­ет М’, должен монтировать и демонтировать несколько дисков, решая, каким же яв­ляется и каким будет следующее состояние М’. Естественно, о компьютерах, решаю­щих задачи подобного рода, никто и не задумывается, поэтому обычные операцион­ные системы не имеют поддержки для таких задач. Однако при желании мы могли бы запрограммировать «голый», лишенный операционной системы компьютер, снабдив его соответствующими возможностями.

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

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

1. Предполагается,-что память компьютера состоит из неопределенно длинной после­довательности слов, каждое из которых имеет адрес. В реальном компьютере слова были бы длиной 32 или 64 бит, но мы длину слова ограничивать не будем. В качест­ве адресов используются целые 0, 1, 2 и т.д. В реальном компьютере последователь­ными целыми нумеровались бы отдельные байты, поэтому адреса слов были бы кратны 4 или 8, но это различие несущественно. В реальном компьютере количество слов «памяти» также было бы ограничено, но мы хотим учесть содержимое произ­вольного числа дисков или других запоминающих устройств, поэтому предполагаем, что количество слов ничем не ограничено.

Предполагается, что программа компьютера записывается в некоторые слова памя­ти. Каждое из этих слов представляет простую инструкцию, как в машинном или ас­семблерном языке обычного компьютера. Примерами служат инструкции переме­щения данных из одного слова в другое или прибавления одного слова к другому. Допускается «непрямая адресация», т.е. инструкция может ссылаться на другое сло­во и использовать его содержимое в качестве адреса слова, к которому применяется операция. Эта возможность, обычная для современных компьютеров, нужна для доступа к массивам, для следования по связям списков и вообще для выполнения операций с указателями.

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

Обычный компьютер имеет регистры — слова памяти с особо быстрым доступом. Часто такие операции, как сложение, применяются только к регистрам, но мы по­добные ограничения не вводим и считаем, что с любым словом можно произвести любую операцию. Относительная скорость операций на различных словах значения не имеет, поскольку вообще не нужна при сравнении возможностей компьютеров и машин Тьюринга по распознаванию языков. Даже если нас интересует полиноми­альная связь между временами работы, разница в скорости доступа к различным словам остается неважной, поскольку влияет «лишь» на константный сомножитель.

Возможная конструкция машины Тьюринга для имитации компьютера представлена на рис. 8.22. Эта МТ имеет несколько лент, но с помощью построений из раздела 8.4.1 ее можно преобразовать в одноленточную. Первая лента представляет всю память компью­тера. Мы использовали код, в котором адреса слов памяти в порядке их номеров пере­межаются со значениями (содержимым) этих слов. И адреса, и значения записаны в дво­ичном виде. Маркеры * и # используются для того, чтобы легко было найти конец адреса и значения слова и различить, является ли двоичная цепочка адресом или значением. Еще один маркер, $, отмечает начало последовательности адресов и значений.

Вторая лента представляет собой «счетчик инструкций». Эта лента содержит одно двоичное целое, представляющее одну из позиций в памяти на первой ленте. Оно интер­претируется как адрес инструкции, которая должна быть выполнена следующей.

Третья лента содержит «адрес памяти» или значение по нему после того, как этот адрес устанавливается на первой ленте. Для выполнения инструкции МТ должна найти
значение по одному или нескольким адресам памяти, где хранятся данные, участвую­щие в вычислении. Нужный адрес копируется на ленту 3 и сравнивается с адресами на ленте 1 до совпадения. Значение по этому адресу копируется на третью ленту и пере­мещается в нужное место, как правило, по одному из начальных адресов, представ­ляющих регистры компьютера.

Конечное управление

Счетчик инструкций

Входной файл компьютера

Память

Адрес памяти

Рабочая память

Рис. 8.22. Машина Тьюринга, имитирующая обычный компьютер

Наша МТ имитирует цикл инструкции (instruction cycle) компьютера следующим образом.

На первой ленте ищется адрес, совпадающий с номером инструкции на ленте 2. На­чиная с маркера $, движемся вправо, сравнивая каждый адрес с содержимым лен­ты 2. Сравнить адреса на двух лентах легко, поскольку нужно лишь синхронно сдви­гать ленточные головки вправо, проверяя совпадение обозреваемых символов.

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

Если в инструкции используется значение по некоторому адресу, то этот адрес явля­ется частью инструкции. Он копируется на третью ленту, а позиция инструкции от­мечается с помощью второй дорожки первой ленты (не показанной на рис. 8.22), по­этому при необходимости к инструкции легко вернуться. Ищем адрес на первой лен­те, и значение по нему копируем на ленту 3, хранящую адрес памяти.

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

а) скопировать значение по другому адресу. Второй адрес извлекается из инст­рукции, помещается на ленту 3 и находится на ленте 1, как описано выше. Когда второй адрес найден, значение по нему копируется в пространство, за­резервированное для него. Если для нового значения нужно больше или меньше памяти, чем для старого, доступное пространство изменяется путем сдвига (shifting over). Он осуществляется так.

На рабочую ленту копируется вся значащая (без пробелов) часть лен­ты 1 справа от того места, куда нужно поместить новое значение.

Новое значение записывается в пространство нужного объема.

Рабочая лента копируется обратно, на ленту 1, непосредственно справа от нового значения.

В особых случаях адрес может не встретиться на первой ленте, поскольку не использовался ранее. Тогда на первой ленте находится место, к которому от­носится данный адрес, при необходимости делается сдвиг, и в это место за­писывается адрес и новое значение;

б) прибавить найденное значение к значению по другому адресу. Для получе­ния второго адреса возвращаемся к инструкции. Ищем адрес на ленте 1. Вы­полняем двоичное сложение значения по этому адресу и значения, записан­ного на ленте 3. Сканируя два значения справа налево, МТ может выполнить сложение с переносом. Если для результата нужно больше места, на ленте 1 используется техника сдвига;

в) перейти к выполнению инструкции по адресу, заданному значением на лен­те 3. Для этого лента 3 просто копируется на ленту 2, и цикл инструкции на­чинается вновь.

Выполнив инструкцию и выяснив, что она не является переходом, к счетчику инст­рукций на ленте 2 прибавляем 1 и вновь начинаем цикл инструкции.

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

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

Наконец, можно предполагать, что компьютер порождает выход, говорящий о допус­тимости входных данных. Для перевода этого действия в термины МТ предположим, что у компьютера есть «допускающая» инструкция, которая, возможно, соответствует функ­ции, вызываемой компьютером для печати yes в выходном файле. Когда МТ имитирует выполнение этой инструкции компьютера, она переходит в собственное допускающее состояние и останавливается.

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

8.6.3. Сравнение времени работы компьютеров и машин Тьюринга

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

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

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

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

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

Перед тем как доказать, что машина Тьюринга, описанная выше, может имитировать п шагов компьютера за время 0(п’), нам нужно исследовать вопрос умножения как ма­шинной инструкции. Проблема в том, что предельное число битов в одном машинном слове не было установлено. Если, скажем, компьютер начал бы со слова, содержащего 2, и должен был бы п раз последовательно умножить это слово само на себя, то оно имело бы значение 2²» . Это число требует 2″ + 1 битов для представления, поэтому время, не­обходимое машине Тьюринга для имитации этих п инструкций, будет, как минимум, экспоненциальным.

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

Пример 8.16. При действии последнего ограничения сложение является допустимой операцией, поскольку длина результата может быть лишь на один бит больше, чем мак­симальная длина слагаемых. Умножение недопустимо, поскольку два т-битовых слова могут дать произведение длиной 2т. Однако умножение w-битовых целых можно ими­тировать с помощью т последовательных сложений, перемежаемых сдвигами сомножи­телей на один бит влево (что является еще одной операцией, увеличивающей длину сло­ва на 1). Таким образом, мы все еще можем умножать неограниченно длинные слова, но время, нужное компьютеру, пропорционально квадрату длины операндов. □

Предположив, что при выполнении компьютерной инструкции длина возрастает не более, чем на один бит, можно доказать полиномиальную взаимосвязь между двумя вре­менами работы. Идея доказательства— заметить, что после выполнения п инструкций количество слов, упоминаемых на ленте памяти МТ, есть 0(п), и каждое компьютерное слово требует О(п) клеток МТ для его представления. Таким образом, лента содержит 0(п²) клеток, и МТ может найти конечное число слов, необходимое для выполнения од­ной инструкции компьютера, за время 0(п²).

Существует, однако, одно дополнительное требование к инструкциям. Даже если ин­струкция не порождает длинное слово в качестве результата, она может занимать очень много времени для его вычисления. Поэтому делается дополнительное предположение, что сама по себе инструкция, применяемая к словам длиной не более к, может быть вы­полнена за O(l^) шагов на многоленточной машине Тьюринга. Несомненно, что обычные операции компьютера, такие как сложение, сдвиг или сравнение значений, могут быть выполнены за 0(к) шагов многоленточной МТ, поэтому мы даже слишком либеральны, допуская, что может делать компьютер в одной инструкции.

Теорема 8.17. Пусть компьютер обладает следующими свойствами.

У него есть только инструкции, увеличивающие максимальную длину слова не бо­лее, чем на 1.

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

Тогда машина Тьюринга, описанная в разделе 8.6.2, может имитировать п шагов компь­ютера за 0(п³) своих шагов.

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

Итак, после выполнения п шагов компьютер не может породить слово длиннее, чем с+ и, и не может создать или использовать адрес, занимающий больше с + п битов. Каж­дая инструкция порождает не более одного нового адреса, получающего значение, по­этому общее число адресов после выполнения п инструкций не превышает d+n. По­скольку любая комбинация «адрес-слово» требует не более 2(с + п) + 2 разрядов, вклю­чая адрес, содержимое и два маркера для их разделения, общее число клеток, занятых после имитации п инструкций, не больше 2(d + п)(с + п + 1). Поскольку с и d — констан­ты, это число клеток есть О(п’).

Нам известно, что каждый из фиксированного числа просмотров адресов, используе­мых в одной инструкции компьютера, может быть выполнен за время 0{п²). Поскольку слова имеют длину 0(п), допустим, что сами по себе инструкции могут быть выполнены на МТ за время 0(п~). Остается еще цена инструкции, которая составлена временем, не­обходимым машине Тьюринга для создания нового пространства, чтобы сохранить но­вое или расширенное слово. Однако сдвиг включает копирование данных объемом не более 0(п²) с ленты 1 на рабочую ленту и обратно. Таким образом, сдвиг также требует лишь ()(rf ) времени на одну инструкцию компьютера.

Заключаем, что МТ имитирует один шаг компьютера за 0(п²) своих шагов. Таким об­разом, как утверждается в теореме, п шагов компьютера можно проимитировать за 0(я³) шагов машины Тьюринга. □

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

Теорема 8.18. Выполнение п шагов работы компьютера типа, описанного в теоре­ме 8.17, можно проимитировать на одноленточной машине Тьюринга с использованием не более 0(п^б) шагов. □

Резюме

• Машина Тьюринга. МТ представляет собой абстрактную вычислительную маши­ну, мощность которой совпадает с мощностью как реальных компьютеров, так и других математических определений того, что может быть вычислено. МТ состо­ит из управления с конечным числом состояний и бесконечной ленты, разделен­ной на клетки. Каждая клетка хранит один из конечного числа ленточных симво­лов, и одна из клеток является текущей позицией ленточной головки. МТ совер­шает переходы на основе своего текущего состояния и ленточного символа в клетке, обозреваемой головкой. За один переход она изменяет состояние, перепи­сывает обозреваемый символ и сдвигает головку на одну клетку вправо или влево.
• Допускание машиной Тьюринга. МТ начинает работу над входом, цепочкой вход­ных символов конечной длины на ее ленте, причем остальные клетки на ленте за­полнены пробелами. Пробел является одним из ленточных символов, и вход обра­зуется из подмножества ленточных символов, не включающего пробел. Эти сим­волы называются входными. МТ допускает свой вход, попадая в допускающее состояние.
• Рекурсивно-перечислимые языки. Языки, допускаемые МТ, называются рекурсив­но-перечислимыми (РП-языками). Таким образом, РП-языки— это языки, кото­рые могут быть распознаны или допущены вычислительным устройством какого- либо вида.
• Мгновенные описания МТ. Текущую конфигурацию МТ можно описать цепочкой конечной длины, которая включает все клетки ленты между крайними слева и справа значащими символами (отличными от пробела). Состояние и позиция го­ловки указываются помещением состояния в последовательность ленточных сим­волов непосредственно слева от обозреваемой клетки.
• Запоминание в конечном управлении. Иногда построение МТ для некоторого язы­ка облегчается за счет того, что состояние представляется как имеющее несколько компонентов. Один из них является управляющим и функционирует, как состоя­ние. Другие компоненты содержат данные, которые нужно запомнить машине.
• Многодорожечные машины. Часто полезно рассматривать ленточные символы в виде кортежей с фиксированным числом компонентов. Каждый компонент можно изобразить как элемент отдельной дорожки на ленте.
• Многоленточные машины Тьюринга. Расширенная модель МТ имеет некоторое фиксированное число лент (более одной). Переход МТ основан на состоянии и кортеже символов, обозреваемых головками на каждой ленте. За один переход многоленточная МТ изменяет состояние, переписывает символы в клетках, обо­зреваемых каждой головкой, и сдвигает любую из головок на одну клетку в любом

направлении. Многоленточная МТ способна распознавать только рекурсивно пе­речислимые языки, хотя делает это быстрее, чем обычная одноленточная.

• Недетерминированные машины Тьюринга. НМТ имеет конечное число выборов следующего перехода (состояние, новый символ и сдвиг головки) для каждого со­стояния и обозреваемого символа. Она допускает свой вход, если хотя бы одна последовательность выборов ведет в МО с допускающим состоянием. Хотя НМТ и кажется более мощной, чем детерминированная МТ, она также распознает лишь рекурсивно перечислимые языки.
• Машины Тьюринга с односторонней лентой. МТ можно ограничить так, что­бы ее лента была бесконечной только справа и не имела клеток слева от на­чальной позиции головки. Такая МТ может допустить любой рекурсивно пе­речислимый язык.
• Многомагазинные (мультистековые) машины Тьюринга. Ленты многоленточ­ной МТ можно ограничить так, чтобы они вели себя, как магазины. Вход раз­мещен на отдельной ленте и читается один раз слева направо, как у конечных или МП-автоматов. Одномагазинная машина в действительности является ДМП-автоматом, хотя машина с двумя магазинами может допустить любой рекурсивно перечислимый язык.
• Счетчиковые машины. Магазины мультистековых машин можно ограничить во­обще одним символом, отличным от маркера дна магазина. Таким образом, каж­дый магазин функционирует, как счетчик, позволяющий хранить неотрицательное целое и проверять, совпадает ли хранимое целое с 0, но ничего более. Машины с двумя счетчиками достаточно для того, чтобы допустить любой рекурсивно пере­числимый язык.
• Имитация машины Тьюринга на реальном компьютере. Имитация МТ на компь­ютере в принципе возможна, если допустить, что для имитации значащей части ленты существует потенциально бесконечный запас сменных запоминающих уст­ройств вроде диска. Поскольку физические ресурсы, необходимые для создания дисков, конечны, данный довод сомнителен. Однако, поскольку пределы памяти Вселенной неизвестны или, без сомнения, обширны, предположение о бесконеч­ности ресурсов (как для ленты МТ) является практически реалистичным и в целом допустимо.
• Имитация компьютера на машине Тьюринга. МТ может имитировать память и управление реального компьютера путем использования одной ленты для записи всех элементов памяти и их содержимого — регистров, основной памяти, дисков и других запоминающих устройств. Таким образом, можно быть уверенным, что все, не выполнимое машиной Тьюринга, не может быть сделано и компьютером.

Литература

Понятие машины Тьюринга взято из [8]. Приблизительно в то же самое время для описания вычислимости было предложено несколько других, менее машиноподобных моделей (работы Черча [1], Клини [5] и Поста [7]). Всем им предшествовала работа Ге- деля [3], которая в конечном счете показывала, что с помощью компьютера ответить на все математические вопросы невозможно.

Изучение многоленточных МТ и, в частности, рассмотрение вопроса о том, как их время работы сравнивается с одноленточной моделью, началось в статье [4]. Исследова­ние многомагазинных и счетчиковых машин исходит из [6], хотя конструкции, приве­денные здесь, взяты из [2].

Метод использования «hello, world» как заменителя допускания с помощью машины Тьюринга или ее останова появился в неопубликованных записках Рудича (S. Rudich).

• Church, «Ап undecidable problem in elementary number theory», American J. Math. 58 (1936),pp. 345-363.
• C. Fischer, «Turing machines with restricted memory access», Information and Control 9:4 (1966),pp. 364-379.
• Goedel, «Uber formal unentscheidbare satze der Principia Mathematica und verwander systeme», Monatschefte fur Mathematic und Physik 38 (1931), pp. 173-198.
• Hartmanis and R. E. Stearns, «On the computational complexity of algorithms», Trans­actions oftheAMS 117 (1965),pp. 285-306.
• C. Kleene, «General recursive functions of natural numbers», Mathematische Annalen 112(1936),pp. 727-742.
• L. Minsky, «Recursive unsolvability of Post’s problem of ‘tag’ and other topics in the theory of Turing machines», Annals of Mathematics 74:3 (1961),pp. 437^455.
• Post, «Finite combinatory processes— formulation I», J. Symbolic Logic1 (1936), pp. 103-105. (Пост Э.Л. Финитные комбинаторные процессы— формулировка 1.// Успенский В.А. Машина Поста. — М.: Наука. — С. 89-95.)
• А. М. Turing, «On computable numbers with an application to the Entscheidungsprob- lem», London Math. Society2:42 (1936),pp. 230-265.ibid.2:43,pp. 544-546.

^[1] В. W. Kernighan and D. М. Ritchie, The С Programming Language, 1978, Prentice-Hall, Engle- wood Cliffs, NJ. (Керниган Б., Ритчи Д. Язык программирования Си. — М.: Финансы и статистика, 1992. См. также Керниган Б., Ритчи Д., Фьюэр А. Язык программирования Си. Задачи по языку Си. — М.: Финансы и статистика, 1985.)

^[2] Наиболее вероятно, что программа печатает по в одном вызове printf, но она может печа­тать «п» в одном вызове printf, а «о» — в следующем.

^[3] Функция malloc системы UNIX распределяет блок памяти, размер которого задается в ее вызове. Эта функция используется, когда нужный размер памяти невозможно определить до начала выполнения программы, как и при чтении входа произвольной длины. Обычно malloc вызывается несколько раз по мере того, как возрастают объем прочитанного входа и потребность в памяти.

^[4] Напомним, что’ проблема в действительности представляет собой язык. Говоря о проблеме разрешения, приводят ли данные программа и вход к печати hello, world, мы в действитель­ности говорим о цепочках, образованных С-программами и их входными данными. Это множество цепочек является языком над алфавитом из символов ASCII.

^[5] Точнее, удаляется все, что находится после крайней слева группы нулей, возможно, усечен­ной. — Прим. ред.

^[6] Не забудем и о *, которую нужно удалить. — Прим. перев.