dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 71
Текст из файла (страница 71)
— М.: ИЛ, 1962. — С. 279–311.)3.S. Ginsburg and G. Rose, “Operations which preserve definability in languages”, J. ACM10:2 (1963), pp. 175–195. (Гинзбург С., Роуз Дж. Об инвариантности классов языковотносительно некоторых преобразований. — Кибернетический сборник, Новая серия, вып. 5. — М.: Мир, 1968. — С. 138–166.)4.S. Greibach, “A new normal-form theorem for context-free phrase structure grammars”,J. ACM 12:1 (1965), pp.
42–52.5.W. Ogden, “A helpful result for proving inherent ambiguity”, Mathematical Systems Theory2:3 (1969), pp. 31–42. (Огден У. Результат, полезный для доказательства существеннойнеоднозначности. — сб. “Языки и автоматы”. — М.: Мир, 1975. — С. 109–113.)6.S. Scheinberg, “Note on the boolean properties of context-free languages”, Informationand Control 3:4 (1960), pp. 372–375.7.D.
H. Younger, “Recognition and parsing of context-free languages in time n3”, Information and Control 10:2 (1967), pp. 189–208. (Янгер Д. Распознавание и анализ контекстно-свободных языков за время n3. — Сб. “Проблемы математической логики”. —М.: Мир, 1970. — С. 344–362.)ËÈÒÅÐÀÒÓÐÀСтр. 317317318Стр. 318ÃËÀÂÀ 7. ÑÂÎÉÑÒÂÀ ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ßÇÛÊÎÂÃËÀÂÀ 8Ââåäåíèåâ òåîðèþ ìàøèíÒüþðèíãàВ этой главе направление наших усилий меняется.
До сих пор нас интересовали в основном простые классы языков и пути их использования для относительно ограниченныхзадач, вроде анализа протоколов, поиска в текстах или синтаксического анализа. Теперьначнется исследование языков, которые вообще можно определить с помощью вычислительных устройств.
Это равносильно изучению того, что может компьютер, посколькураспознавание цепочек языка является формальным способом выражения любой задачи,а решение задачи — это разумное представление того, что делает компьютер.Мы предполагаем, что читатель знаком с программированием на языке С. Вначале,используя это знание, с помощью неформальных доводов покажем, что существуютопределенные задачи (проблемы), которые с помощью компьютера решить невозможно.
Эти задачи называются “неразрешимыми”. Затем познакомимся с классическойформальной моделью компьютера, которая называется машиной Тьюринга (МТ). Ихотя машины Тьюринга совершенно не похожи на компьютеры, и было бы весьма неэффективно их производить и продавать, тем не менее машина Тьюринга получилапризнание как точная модель того, что способно делать любое физическое вычислительное устройство.В главе 9 машина Тьюринга используется для развития теории “неразрешимых” проблем, т.е. проблем, которые не может решить ни один компьютер. Мы покажем, чтомногие просто формулируемые задачи в действительности неразрешимы. Примером может служить распознавание, является ли данная грамматика неоднозначной, и ряд такихпримеров будет продолжен.8.1. Çàäà÷è, íå ðåøàåìûå êîìïüþòåðàìèЦель этого раздела — с помощью С-программирования неформально доказать, чтосуществуют задачи, которые невозможно решить, используя компьютер.
Мы рассмотримчастную задачу распознавания, является ли текст hello, world первым, что печатаетС-программа. Можно подумать, будто имитация любой программы всегда позволит сказать, что она делает, однако в реальности нам придется “бороться” с программами, которые работают невообразимо долго, прежде чем что-нибудь вывести на печать. Эта про-Стр. 319блема — незнание момента, в который что-то произойдет, если вообще произойдет, —является основной причиной нашей неспособности распознать, что делает программа.Однако доказательство того, что не существует алгоритма решения указанной задачираспознавания, весьма сложно и требует определенного формализма. В этом разделепредпочтение отдается формальным доказательствам, а не интуиции.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. Она получает на вход n и ищетположительные целые решения уравнения xn + yn = zn. Если находит, то печатает hello,world. Не обнаружив целых x, y и z, удовлетворяющих данному уравнению, она продолжает поиск до бесконечности и никогда не печатает hello, world.Для того чтобы понять, как работает эта программа, сначала заметим, что exp является встроенной функцией вычисления экспоненты. Основной программе нужно искатьтройки (x, y, z) в порядке, гарантирующем, что каждая тройка в конце концов достигается.
Для корректного поиска используется четвертая переменная, total, которая инициируется значением 3 и увеличивается в while-цикле каждый раз на 1, так что ее значение в конце концов достигает любого натурального числа. Внутри while-цикла totalразделяется на три положительных целых x, y и z, причем x изменяется в for-цикле от 1до total-2, y внутри этого for-цикла изменяется от 1 до total-x-1, а остаток значения total, между 1 и total-2, становится значением z.1B. W. Kernighan and D.
M. Ritchie, The C Programming Language, 1978, Prentice-Hall, Englewood Cliffs, NJ. (Керниган Б., Ритчи Д. Язык программирования Си. — М.: Финансы и статистика,1992. См. также Керниган Б., Ритчи Д., Фьюэр А. Язык программирования Си. Задачи по языкуСи. — М.: Финансы и статистика, 1985.)320Стр. 320ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀВо внутреннем цикле для тройки (x, y, z) проверяется равенство xn + yn = zn. Если оновыполняется, то печатается hello, world, а если нет — не печатается ничего.int exp(int i, n)/* вычисление i в степени n */{int ans, j;ans = 1;for (j=1; j<=n; j++) ans *= i;return(ans);}main(){int n, total, x, y, z;scanf("%d", n);total = 3;while (1) {for (x=1; x<=total-2; x++)for (y=1; x<=total-x-1; y++){z = total - x - y;if (exp(x,n) + exp(y,n) == exp(z,n))printf("hello, world\n");}total++;}}Рис. 8.2. Великая теорема Ферма, выраженная в программе приветствия мираЕсли прочитано значение 2, то программа находит набор значений total = 12, x = 3,y = 4 и z = 5, для которого xn + yn = zn.
Таким образом, если на входе 2, то программа действительно печатает hello, world.Однако для любого n > 2 программа никогда не найдет тройку положительных целых,удовлетворяющих xn + yn = zn, и hello, world напечатано не будет. Интересно, чтоеще несколько лет назад не было известно, печатает ли данная программа hello,world, т.е. имеет ли уравнение xn + yn = zn для некоторого большого n. Утверждение,что это уравнение не имеет решений, было сформулировано Ферма более 300 лет назад,но до недавних пор доказательство не было найдено.
Данное утверждение часто называется “великой теоремой Ферма” (“Fermat’s last theorem”).Определим проблему “hello, world” следующим образом. По данной С-программе иее входу определить, печатает ли она в качестве первых 12 символов hello, world. Вдальнейшем для краткости утверждение о том, что программа печатает hello, world,употребляется в смысле, что она печатает hello, world как первые 12 символов.8.1.
ÇÀÄÀ×È, ÍÅ ÐÅØÀÅÌÛÅ ÊÎÌÏÜÞÒÅÐÀÌÈСтр. 321321Поскольку математикам понадобилось более 300 лет для решения вопроса, выраженного простенькой 22-строчной программой, то представляется правдоподобным, что общая задача распознавания, печатает ли hello, world данная программа с даннымвходом, должна быть действительно сложной. Таким образом, любую задачу, не решенную математиками до сих пор, можно поставить как вопрос вида “печатает ли hello,world данная программа с данным входом?”.
Было бы замечательно, если бы нам удалось написать программу, которая проверяет любую программу P и ее вход I и определяет, печатается ли hello, world при выполнении P со входом I. Мы докажем, что такой программы не может быть.Ïî÷åìó äîëæíû ñóùåñòâîâàòü íåðàçðåøèìûå ïðîáëåìûНелегко доказать, что какая-то определенная проблема, например, обсуждаемая здесьпроблема “hello, world”, должна быть неразрешимой.
Однако легко понять, почемупочти все проблемы должны быть неразрешимыми в рамках любой системы, включающей программирование. Вспомним, что “проблема” — это в действительностивопрос о принадлежности цепочки языку. Множество различных языков над любымалфавитом, в котором более одного символа, несчетно.2 Таким образом, невозможнопронумеровать языки натуральными числами так, чтобы каждый язык получил номер, и каждое число было назначено одному языку.С другой стороны, программы, будучи конечными цепочками в конечном алфавите(обычно это подмножество алфавита ASCII), допускают такую нумерацию, т.е. образуют счетное множество. Их можно упорядочить по длине, а программы одной длины расположить в лексикографическом порядке. Таким образом, можно говорить опрограмме с номером 1, 2 и вообще с номером i.В результате можно утверждать, что проблем существует “бесконечно больше”, чемпрограмм.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
