Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 86
Текст из файла (страница 86)
л4нагадараэюечные машины. Часто полезно рассматривать ленточные символы в виде кортежей с фиксированным числом компонентов. Каждый компонент можно изобразить как элемент отдельной дорожки на ленте. Л4ногаленточные машины Тьюринга. Расширенная модель МТ имеет некоторое фиксированное число лент (более одной).
Переход МТ основан на состоянии и кортеже символов, обозреваемых головками на каждой ленте. За один переход многоленточная МТ изменяет состояние, переписывает символы в клетках, обозреваемых каждой головкой, н сдвигает любую из головок на одну клетку в любом ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА 374 направлении. Многоленточная МТ способна распознавать только рекурсивно пе- речислимые языки, хотя делает это быстрее, чем обычная одноленточная. Иедетериинироаанные машины Тьюринга. НМТ имеет конечное число выборов следующего перехода (состояние, новый символ и сдвиг головки) для каждого состояния и обозреваемого символа. Она допускает свой вход, если хотя бы одна последовательность выборов ведет в МО с допускающим состоянием.
Хотя НМТ и кажется более мощной, чем детерминированная МТ, она также распознает лишь рекурсивно перечислимые языки. Машины Тьюринга с односторонней лентой. МТ можно ограничить так, чтобы ее лента была бесконечной только справа и не имела клеток слева от начальной позиции головки. Такая МТ может допустить любой рекурсивно перечислимый язык. Многомагазинные (мультистекоеые) машины Тьюринга. Ленты многоленточной МТ можно ограничить так, чтобы они вели себя, как магазины. Вход размещен на отдельной ленте и читается один раз слева направо, как у конечных нли МП-автоматов.
Одномагазинная машина в действительности является ДМП-автоматом, хотя машина с двумя магазинами может допустить любой рекурсивно перечислимый язык. Счетчикоеые машины. Магазины мультистековых машин можно ограничить вообще одним символом, отличным от маркера дна магазина. Таким образом, каждый магазин функционирует, как счетчик, позволяющий хранить неотрицательное целое и проверять, совпадает ли хранимое целое с О, но ничего более, Машины с двумя счетчиками достаточно для того, чтобы допустить любой рекурсивно перечислимый язык.
Имитация машины Тьюринга на реальном компьютере. Имитация МТ на компьютере в принципе возможна, если допустить, что для имитации значащей части ленты существует потенциально бесконечный запас сменных запоминающих устройств вроде диска. Поскольку физические ресурсы, необходимые для создания дисков, конечны, данный довод сомнителен. Однако, поскольку пределы памяти Вселенной неизвестны или, без сомнения, обширны, предположение о бесконечности ресурсов (как для ленты МТ) является практически реалистичным и в целом допустимо. Имитация колтьютера на машине Тьюринга.
МТ может имитировать память и управление реального компьютера путем использования одной ленты для записи всех элементов памяти и их содержимого — регистров, основной памяти, дисков и других запоминающих устройств. Таким образом, можно быть уверенным, что все, не выполнимое машиной Тьюринга, не может быть сделано и компьютером. РЕЗЮМЕ 375 Литература Понятие машины Тьюринга взято из [8]. Приблизительно в то же самое время для описания вычислнмости было предложено несколько других, менее машиноподобных моделей [работы Черча [Ц, Клини [5] и Поста [7]).
Всем им предшествовала работа Геделя [3], которая в конечном счете показывала, что с помощью компьютера ответить на все математические вопросы невозможно. Изучение многоленточных МТ и, в частности, рассмотрение вопроса о том, как их время работы сравнивается с одноленточной моделью, началось в статье [4]. Исследование многомагазинных и счетчиковых машин исходит из [6], хотя конструкции, приведенные здесь, взяты из [2].
Метод использования "Лейо, зног16" как заменителя допускания с помощью машины Тьюринга или ее астапова появился в неопубликованных записках Рудича (Б. Кпсйсй). 1. А. СЛпгсЛ, "Ап понес!оаЫе ргоЫегп !п е!епзепгагу ппгпЬег гйеогу", Агиепсаи Х Ма11ь 58 [!936), рр. 345-363. 2. Р. С. ЕЕсЛег, "Топай |пасЫпез зн!1Л гез!псгег! те|ногу ассезз", 1н)оггнабон анг1 Сонгго1 9:4 (! 966), рр. 364-379.
3. К. Ооес[е[, "!)Ьег Гоггпа! ппепгзсЛен]Лаге за!ге г[ег Рг!пс!р!а Магйегпа!!са ппг! непнапг]ег зузгегпе', Моннгге1ийе7)гг Мигйетаггс ннИ РАЕЙ 38 [1931), рр, 173 — 198. 4. 1. Напгпапй апг[ К. Е. 8!еагпз, "Оп гЛе согпршагюпа! согпр!ехпу о1а!8опгйгоз", Тгаизаш1онз оу йе АМБ 117 [1965), рр. 285 — 306.
5. 8. С. К!еепе, "Оепега] гесогз!не Гипс!!опз оГ па!ига! пшпЬегз", МагЬешаг1зе1зе Анна!ел 112 (1936), рр. 727-742. б. М. 1.. М!пз]гу, "Кесогз!не ппзо!наЫ!1!у оГ Роьрз ргоЫегп оГ 'гай' апг! о!Лег гор!сз !п гйе гЛеогу о1Типп8 шасЛ!пез", Аниа[з о7'Маг1зегнапез 74:3 [1961), рр. 437 — 455. 7. Е. Розг, тр!п!ге согпЬ!пагогу ргосеазез — Гоппп!абоп Г', Х 5уггйо11с Ьоя[с 1 [1936), рр. !ОЗ вЂ” !05.
(Пост Э.Л. Финитные комбинаторные процессы — формулировка 1.11 Успенский В.А. Машина Поста. — Мз Наука. — С. 89 — 95.) 8, А. М. Тпппй, "Оп согпрогаЫе ппшЬегз зн!1Л ап аррйсацоп го гйе ЕпгзсЛе!г!ппдзргоЬ- 1ев", Ргос. 1 наг[оп Мань Яосгегу 2:42 [1936), рр. 230-265.
161г[. 2;43, рр. 544-546, 376 ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА ГЛАВА 9 Неразрешимость Эта глава начинается повторением рассуждений из раздела 8.1, которые неформально обосновывали существование проблем, не разрешимых с помощью компьютера. Недостатком тех "правдоподобных рассуждений" было вынужденное пренебрежение реальными ограничениями, возникающими при реализации языка С (или другого языка программирования) на любом реальном компьютере.
Однако эти ограничения, вроде конечности адресного пространства, не являются фундаментальными. Наоборот, с течением времени мы вправе ожидать от компьютеров неограниченного роста таких количествен- ных характеристик, как размеры адресного пространства, оперативной памяти и т.п. Сосредоточившись на машинах Тьюринга, для которых отграничения такого рода от- сутствуют, можно лучше понять главное — принципиальные возможности вычислительных устройств, если не сегодня, то в перспективе.
В этой главе дается формальное доказательство того, что никакая машина Тьюринга не может решить следующую задачу. ° Допускает ли данная машина Тьюринга сама себя (свой код) в качестве вхола? Из раздела 8.6 известно, что на машинах Тьюринга можно имитировать работу реальных компьютеров„даже не имеющих сегодняшних ограничений. Поэтому независимо от того, насколько ослаблены эти практические ограничения, у нас будет строгое доказатель- ство, что указанную задачу нельзя решить с помощью компьютера. Далее мы разделим проблемы, разрешимые с помощью машин Тьюринга, на два класса. В первый класс войдут те из них, которые имеют аагорильи решения (т.е.
машину Тьюринга, которая останавливается независимо от того, допускает она свой вход или нет). Во второй класс войдут проблемы, разрешимые лишь с помощью таких машин Тьюринга, которые с недопустимыми входами могут работать бесконечно. В последнем случае проверить допустимость входа весьма проблематично, поскольку независимо от того, сколь долго работает МТ, неизвестно, допускается вход или нет.
Поэтому мы сосредоточимся на методах доказательства "неразрешимости" проблем, т.е. что для них не существует алгоритма решения независимо от того, допускаются ли они машиной Тью- ринга, которая не останавливается на некоторых входах, или нет. Будет доказано, что неразрешима следующая проблема. ° Допускает ли ланная машина Тьюринга данный вход? Затем из неразрешимости этой проблемы будет выведена неразрешимость ряда других проблем.
Например, будет показано, что все нетривиальные задачи, связанные с языком машины Тьюринга, неразрешимы, как и многие проблемы, в которых речь вообще не идет о машинах Тьюринга, программах или компьютерах. 9.1. Неперечислиллый язык Напомним, что язык 1 является рекуреиапо-перечисэииым (РП-языком), если 1 = ЦМ) для некоторой МТ М. В разделе 9.2 будут введены так называемые "рекурсивные", или "разрешимые", языки, которые не только рекурсивно перечислимы, но и допускаются некоторой МТ, останавливающейся на всех своих входах независимо от их допустимости. Наша дальняя цель — доказать неразрешимость языка, состоящего из пар 1М н), ко- торые удовлетворяют следующим условиям.
1. М вЂ” машина Тьюринга (в виде соответствующего двоичного кода) с входным алфавитом 10, 1). 2. н — цепочка из символов О и 1. 3. М допускает вход ж. Если эта проблема неразрешима при условии, что алфавит — двоичный, то она, безусловно, будет неразрешимой и в более общем виде, прн произвольном входном алфавите. Прежде всего, необходимо сформулировать эту проблему как вопрос о принадлежности некоторому конкретному языку.
Поэтому нужно определить такое кодирование машин Тьюринга, в котором использовались бы только символы О и 1 независимо от числа состояний МТ. Имея такие коды, можно рассматривать любую двоичную цепочку как машину Тьюринга. Если цепочка не является правильным представлением какой-либо МТ, то ее можно считать представлением МТ без переходов. Для достижения промежуточной цели, представленной в данном разделе, используется "'язык диагонализацин" Рж Он состоит нз всех цепочек н, каждая из которых не допускается машиной Тьюринга, представленной этой цепочкой.
Мы покажем, что такой машины Тьюринга, которая бы допускала 1ж вообще не существует. Напомним; показать, что язык не допускается никакой машиной Тьюринга, значит доказать нечто большее, чем то, что данный язык неразрешим (т.е. что для него не существует алгоритма, или МТ, которая останавливается на всех своих входах). Роль языка 1а аналогична роли гипотетической программы О, из раздела 8.1.2, которая печатает )те11о, ьгог1сз, если ей на вход подается программа, не печатаюп1оя )зе11о, эеог1с1 при чтении собственного кода.
Точнее, как не существует О,, так и Та не может быть допущен никакой машиной Тьюринга. Реакция первой на саму себя как на вход приводит к противоречию. Аналогично, если бы 1а допускался некоторой машиной Тьюринга, то она противоречила бы самой себе при обработке своего собст- асино~о кода. 9.1.1. Перечисление двоичных цепочек В дальнейшем нам понадобится приписать всем двоичным цепочкам целые числа так, чтобы каждой цепочке соответствовало одно целое число и каждому числу — одна цепочка.
Если н — двоичная цепочка, то 1н рассматривается как двоичное представление ГЛАВА 9. НЕРАЗРЕШИМОСТЬ 378 ) а целого числа 0 Тогда и называется йй цепочкой. Таким образом, весть первая цепочка, 0 — вторая, 1 — третья, 00 — четвертая, 01 — пятая, и так далее. Это равносильно тому, что цепочки упорядочены по длине, а цепочки равной длины упорядочены лексикографически.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
