dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 84
Текст из файла (страница 84)
Начнем с замечания, что первая лента (лента памяти) машины Тьюринга(см. рис. 8.22) вначале содержит только программу компьютера. Эта программа может бытьдлинной, но длина ее фиксирована и является константой, не зависящей от n — числа шаговвыполнения ее инструкций. Таким образом, существует некоторая константа c, представляющая собой наибольшее из компьютерных слов или адресов, встречающихся в программе. Существует также константа d — количество слов, занимаемых программой.Итак, после выполнения n шагов компьютер не может породить слово длиннее, чемc + n, и не может создать или использовать адрес, занимающий больше c + n битов.
Каждая инструкция порождает не более одного нового адреса, получающего значение, поэтому общее число адресов после выполнения n инструкций не превышает d + n. Поскольку любая комбинация “адрес-слово” требует не более 2(c + n) + 2 разрядов, включая адрес, содержимое и два маркера для их разделения, общее число клеток, занятыхпосле имитации n инструкций, не больше 2(d + n)(c + n + 1).
Поскольку c и d — константы, это число клеток есть O(n2).Нам известно, что каждый из фиксированного числа просмотров адресов, используемых в одной инструкции компьютера, может быть выполнен за время O(n2). Посколькуслова имеют длину O(n), допустим, что сами по себе инструкции могут быть выполненына МТ за время O(n2). Остается еще цена инструкции, которая составлена временем, необходимым машине Тьюринга для создания нового пространства, чтобы сохранить новое или расширенное слово. Однако сдвиг включает копирование данных объемом неболее O(n2) с ленты 1 на рабочую ленту и обратно. Таким образом, сдвиг также требуетлишь O(n2) времени на одну инструкцию компьютера.8.6.
ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀ È ÊÎÌÏÜÞÒÅÐÛСтр. 373373Заключаем, что МТ имитирует один шаг компьютера за O(n2) своих шагов. Таким образом, как утверждается в теореме, n шагов компьютера можно проимитировать за O(n3)шагов машины Тьюринга. В заключение отметим, что возведение в куб числа шагов позволяет многоленточнойМТ имитировать компьютер. Из материала раздела 8.4.3 известно, что одноленточнаяМТ может имитировать многоленточную не более, чем за квадрат числа шагов. Такимобразом, имеет место следующее утверждение.Теорема 8.18. Выполнение n шагов работы компьютера типа, описанного в теореме 8.17, можно проимитировать на одноленточной машине Тьюринга с использованиемне более O(n6) шагов.
Ðåçþìå♦ Машина Тьюринга. МТ представляет собой абстрактную вычислительную машину, мощность которой совпадает с мощностью как реальных компьютеров, так идругих математических определений того, что может быть вычислено. МТ состоит из управления с конечным числом состояний и бесконечной ленты, разделенной на клетки. Каждая клетка хранит один из конечного числа ленточных символов, и одна из клеток является текущей позицией ленточной головки. МТ совершает переходы на основе своего текущего состояния и ленточного символа вклетке, обозреваемой головкой. За один переход она изменяет состояние, переписывает обозреваемый символ и сдвигает головку на одну клетку вправо или влево.♦ Допускание машиной Тьюринга.
МТ начинает работу над входом, цепочкой входныхсимволов конечной длины на ее ленте, причем остальные клетки на ленте заполненыпробелами. Пробел является одним из ленточных символов, и вход образуется из подмножества ленточных символов, не включающего пробел. Эти символы называютсявходными. МТ допускает свой вход, попадая в допускающее состояние.♦ Рекурсивно-перечислимые языки.
Языки, допускаемые МТ, называются рекурсивноперечислимыми (РП-языками). Таким образом, РП-языки — это языки, которые могутбыть распознаны или допущены вычислительным устройством какого-либо вида.♦ Мгновенные описания МТ. Текущую конфигурацию МТ можно описать цепочкойконечной длины, которая включает все клетки ленты между крайними слева исправа значащими символами (отличными от пробела). Состояние и позиция головки указываются помещением состояния в последовательность ленточных символов непосредственно слева от обозреваемой клетки.♦ Запоминание в конечном управлении.
Иногда построение МТ для некоторого языка облегчается за счет того, что состояние представляется как имеющее несколько374Стр. 374ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀкомпонентов. Один из них является управляющим и функционирует, как состояние. Другие компоненты содержат данные, которые нужно запомнить машине.♦ Многодорожечные машины. Часто полезно рассматривать ленточные символы ввиде кортежей с фиксированным числом компонентов.
Каждый компонент можноизобразить как элемент отдельной дорожки на ленте.♦ Многоленточные машины Тьюринга. Расширенная модель МТ имеет некотороефиксированное число лент (более одной). Переход МТ основан на состоянии икортеже символов, обозреваемых головками на каждой ленте. За один переходмноголенточная МТ изменяет состояние, переписывает символы в клетках, обозреваемых каждой головкой, и сдвигает любую из головок на одну клетку в любомнаправлении. Многоленточная МТ способна распознавать только рекурсивно перечислимые языки, хотя делает это быстрее, чем обычная одноленточная.♦ Недетерминированные машины Тьюринга. НМТ имеет конечное число выборовследующего перехода (состояние, новый символ и сдвиг головки) для каждого состояния и обозреваемого символа.
Она допускает свой вход, если хотя бы однапоследовательность выборов ведет в МО с допускающим состоянием. Хотя НМТи кажется более мощной, чем детерминированная МТ, она также распознает лишьрекурсивно перечислимые языки.♦ Машины Тьюринга с односторонней лентой. МТ можно ограничить так, чтобы ее лента была бесконечной только справа и не имела клеток слева от начальной позиции головки.
Такая МТ может допустить любой рекурсивно перечислимый язык.♦ Многомагазинные (мультистековые) машины Тьюринга. Ленты многоленточной МТможно ограничить так, чтобы они вели себя, как магазины. Вход размещен на отдельной ленте и читается один раз слева направо, как у конечных или МП-автоматов. Одномагазинная машина в действительности является ДМП-автоматом, хотя машина сдвумя магазинами может допустить любой рекурсивно перечислимый язык.♦ Счетчиковые машины.
Магазины мультистековых машин можно ограничить вообщеодним символом, отличным от маркера дна магазина. Таким образом, каждый магазинфункционирует, как счетчик, позволяющий хранить неотрицательное целое и проверять, совпадает ли хранимое целое с 0, но ничего более. Машины с двумя счетчикамидостаточно для того, чтобы допустить любой рекурсивно перечислимый язык.♦ Имитация машины Тьюринга на реальном компьютере. Имитация МТ на компьютерев принципе возможна, если допустить, что для имитации значащей части ленты существует потенциально бесконечный запас сменных запоминающих устройств вродедиска. Поскольку физические ресурсы, необходимые для создания дисков, конечны,данный довод сомнителен.
Однако, поскольку пределы памяти Вселенной неизвестныили, без сомнения, обширны, предположение о бесконечности ресурсов (как для лентыМТ) является практически реалистичным и в целом допустимо.ÐÅÇÞÌÅСтр. 375375♦ Имитация компьютера на машине Тьюринга. МТ может имитировать память иуправление реального компьютера путем использования одной ленты для записивсех элементов памяти и их содержимого — регистров, основной памяти, дискови других запоминающих устройств. Таким образом, можно быть уверенным, чтовсе, не выполнимое машиной Тьюринга, не может быть сделано и компьютером.ËèòåðàòóðàПонятие машины Тьюринга взято из [8]. Приблизительно в то же самое время дляописания вычислимости было предложено несколько других, менее машиноподобныхмоделей (работы Черча [1], Клини [5] и Поста [7]).
Всем им предшествовала работа Геделя [3], которая в конечном счете показывала, что с помощью компьютера ответить навсе математические вопросы невозможно.Изучение многоленточных МТ и, в частности, рассмотрение вопроса о том, как ихвремя работы сравнивается с одноленточной моделью, началось в статье [4]. Исследование многомагазинных и счетчиковых машин исходит из [6], хотя конструкции, приведенные здесь, взяты из [2].Метод использования “hello, world” как заменителя допускания с помощью машиныТьюринга или ее останова появился в неопубликованных записках Рудича (S. Rudich).1.A. Church, “An undecidable problem in elementary number theory”, American J. Math.
58(1936), pp. 345–363.2.P. C. Fischer, “Turing machines with restricted memory access”, Information and Control9:4 (1966), pp. 364–379.3.K. Goedel, “Uber formal unentscheidbare satze der Principia Mathematica und verwandersysteme”, Monatschefte fur Mathematic und Physik 38 (1931), pp. 173–198.4.J. Hartmanis and R. E. Stearns, “On the computational complexity of algorithms”, Transactions of the AMS 117 (1965), pp.
285–306.5.S. C. Kleene, “General recursive functions of natural numbers”, Mathematische Annalen112 (1936), pp. 727–742.6.M. L. Minsky, “Recursive unsolvability of Post’s problem of ‘tag’ and other topics in thetheory of Turing machines”, Annals of Mathematics 74:3 (1961), pp. 437–455.7.E. Post, “Finite combinatory processes — formulation I”, J. Symbolic Logic 1 (1936),pp. 103–105. (Пост Э.Л. Финитные комбинаторные процессы — формулировка 1.//Успенский В.А.
Машина Поста. — М.: Наука. — С. 89–95.)8.A. M. Turing, “On computable numbers with an application to the Entscheidungsproblem”, Proc. London Math. Society 2:42 (1936), pp. 230-265. ibid. 2:43, pp. 544–546.376Стр. 376ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÃËÀÂÀ 9ÍåðàçðåøèìîñòüЭта глава начинается повторением рассуждений из раздела 8.1, которые неформальнообосновывали существование проблем, не разрешимых с помощью компьютера.
Недостатком тех “правдоподобных рассуждений” было вынужденное пренебрежение реальными ограничениями, возникающими при реализации языка C (или другого языка программирования) на любом реальном компьютере. Однако эти ограничения, вроде конечности адресного пространства, не являются фундаментальными. Наоборот, с течениемвремени мы вправе ожидать от компьютеров неограниченного роста таких количественных характеристик, как размеры адресного пространства, оперативной памяти и т.п.Сосредоточившись на машинах Тьюринга, для которых ограничения такого рода отсутствуют, можно лучше понять главное — принципиальные возможности вычислительных устройств, если не сегодня, то в перспективе.
В этой главе дается формальное доказательство того, что никакая машина Тьюринга не может решить следующую задачу.• Допускает ли данная машина Тьюринга сама себя (свой код) в качестве входа?Из раздела 8.6 известно, что на машинах Тьюринга можно имитировать работу реальныхкомпьютеров, даже не имеющих сегодняшних ограничений. Поэтому независимо от того, насколько ослаблены эти практические ограничения, у нас будет строгое доказательство, что указанную задачу нельзя решить с помощью компьютера.Далее мы разделим проблемы, разрешимые с помощью машин Тьюринга, на двакласса. В первый класс войдут те из них, которые имеют алгоритм решения (т.е. машинуТьюринга, которая останавливается независимо от того, допускает она свой вход илинет).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
