Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 74
Текст из файла (страница 74)
Нам нужен инструмент, позволяющий доказывать неразрешимость или труднорешаемость повседневных вопросов. Методика, представленная в разделе 8.1, полезна для вопросов, касающихся программ, но ее нелегко перенести на проблемы, не связанные с программами. Например, было бы нелегко свести проблему 'Ъе11о, иог1сГ' к проблеме неоднозначности грамматики. Таким образом, нужно перестроить нашу теорию неразрешимости, основанную не на программах в языке С нли других языках, а на очень простой модели компьютера, которая щзывается машиной Тьюринга.
Это устройство по существу представляет собой конечный автомат с бесконечной лентой, на которой он может как читать, так и записывать данные. Одно нз преимуществ машин Тьюринга по сравнению с программами как представлением вычислений состоит в том, что машина Тьюринга достаточно проста н ее конфигурацию кожно точно описать, используя нотацию, весьма похожую на МО МП-автоматов. Для сравнения, состояние С-программы включает все переменные, возникающие при выполнеявя любой цепочки вызовов функций, и нотация для описания этих состояний настолько сложна, что практически не позволяет проводить понятные формальные доказательства.
С использованием нотации машин Тьюринга будет доказана неразрешимость некоторых проблем, не связанных с программированием. Например, в разделе 9.4 будет покажво, что "проблема соответствий Поста", простой вопрос о двух списках цепочек, неразрешим, и что эта проблема облегчает доказательство неразрешимости вопросов о грамматиках, вроде неоднозначности. Аналогично, когда будут введены трудно разрешвмые проблемы, мы увидим, что к их числу принадлежат и определенные вопросы, казалось бы, не связанные с вычислениями, например, выполнимость булевских формул.
8.2,1. Поиски решения всех математических вопросов В начале ХХ столетия великий математик Д. Гильберт поставил вопрос о поисках алшрятма, который позволял бы определить истинность или ложность любого математического утверждения. В частности, он спрашивал, есть ли способ определить, истинна вла ложна произвольная формула в исчислении предикатов первого порядка с целыми числами. Исчисление предикатов первого порядка с целыми (арифметика) достаточно кашне, чтобы выразить утверждения типа "эта грамматика неоднозначна" или "эта программа печатает )эе11о, ног1с1*1 Поэтому, окажись предположение Гильберта празяльиын, данные проблемы были бы разрешимыми.
Однако в 1931 г. К. Гедель опубликовал свою знаменитую теорему о неполноте. Он лжазая, что существует истинная формула первого порядка с целыми, которую нельзя вв доказать, ни опровергнуть в исчислении предикатов первого порядка над целыми. Его техника доказательства похожа на конструкцию противоречивой программы О~ из раздела 8.1.2, но имеет дело с функциями целого аргумента, а не с С-программами.
Исчисление предикатов было не единственным понятием, применяемым для формализации "любого возможного вычисления". В действительности, исчисление предикатов, будучи декларативным, а не вычислительным, конкурировало с различными нотациями, вюаочая "частично рекурсивные функции". В 1936 г, А. М. Тьюринг в качестве модели 329 8.2. МАШИНА ТЬЮРИНГА "любого возможного вычисления" предложил машину Тьюринга.
Эта модель была не декларативной, а "машиноподобной", хотя настоящие электронные и даже электромеханические машины появились лишь несколько лет спустя ги сам Тьюринг занимался их разработкой во время второй мировой войны). Интересно, что все когда-либо предложенные серьезные вычислительные модели имеют одинаковую мощность, т.е. все они вычисляют одни и те же функции или распознают одни и те же множества. Недоказуемое предположение, что любой общий метод вычислений позволяет вычислять лишь частично рекурсивные функции (и их же способны вычислять машины Тьюринга или современные компьютеры), известно как гипотеза Черна (следуя логике А.
Черча), или тезис Черча-Тьюринга. 8.2.2. Описание машин Тьюринга Машина Тьюринга изображена иа рис. 8.8. Машина состоит из конечного управления, которое может находиться в любом из конечного множества состояний. Есть лента, разбитая на «летки; каждая клетка может хранить любой символ из конечного их множества. Риа 8.8. Машина Тьюринта Изначально на ленте записан вход, представляющий собой цепочку символов конечной длины. Символы выбраны из входного алфавита. Все остальные клетки, до бесконечности, слева и справа от входа содержат специальный символ, называемый пустым символом, или пробелом. Он является не входным, а ленточным символом. Кроме входных символов и пробела возможны другие ленточные символы.
Ленточная головка (далее просто головка) всегда устанавливается иа какую-то из клеток ленты, которая называется сканируемой, или обозреваемой. Вначале обозревается крайняя слева клетка входа. Переход машины Тьюринга — это функция, зависящая от состояния конечного управления и обозреваемого символа. За один переход машина Тьюринга должна выполнить следующие действия. Е Изменить состояние. Следующее состояние может совпадать с текущим.
2. Записать ленточный символ в обозреваемую клетку. Этот символ замещает любой символ в этой клетке, в частности, символы могут совпадать. 330 ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА 3. Сдвинуть головку влево или вправо. В нашей формализации не допускается, чтобы головка оставалась на месте. Это ограничение не изменяет того, что могут вычислить машины Тьюринга, поскольку любая последовательность переходов с остающейся на месте головкой и последующим сдвигом может быть сжата до одного перехода с из- менением состояния и ленточного символа и сдвигом головки влево илн вправо.
Формальная запись, используемая для машин Тьюринга (МТ), похожа на запись конечных автоматов или МП-автоматов. МТ описывается семеркой и= (д, Е, Г, б, дм В, Р), компоненты которой имеют следующий смысл. Д вЂ” конечное множество состояний конечного управления. Š— конечное множество входных символов. à — множество ленточных символов; Е всегда есть подмножество Г.
Б — функция переходов. Аргументами а(д, Х) являются состояние д и ленточный символ Х, а значением, если оно определено, — тройка (а, У, О). В этой тройке р есть следующее состояние из Д, У вЂ” символ из Г, который записывается вместо символа в обозреваемой клетке, а Р— направление сдвига головки "влево" или "вправо", обозначаемое, соответственно, как А или Я. дь — начальное состояние из Д, в котором управление находится в начале.
 — пусаой символ, или оробел. Этот символ принадлежит Г, но не Е, т.е. не является входным. Вначале он записан во всех клетках, кроме конечного их числа, где хранятся входные символы. Остальные символы называются значащими. Р— множество заключитечьных, или допускакнцих, состояний; является подмножеством Д. 8.2.3. Конфигурации машин Тьюринга Для формального описания работы машины Тьюринга нужно построить систему записи конфигураций, или мгновенных описаний (МО), подобную нотации, определенной для МП-автоматов.
Поскольку МТ имеет неограниченно длинную ленту, можно подумать, что конечное описание конфигураций МТ невозможно. Однако после любого конечного числа шагов МТ может обозреть лишь конечное число клеток, хотя н ничем не ограниченное. Таким образом, в любом МО есть бесконечный префикс и бесконечный суффикс из клеток, которые еще не обозревались. Все эти клетки должны содержать или пробелы, или входные символы из конечного нх множества. Таким образом, в МО включаются только клетки между крайними слева и справа значащими символами. В отдельных случаях, когда головка обозревает один из пробелов перед нли за участком значащих символов, конечное число пробелов также включается в МО. Кроме ленты, нужно представить конечное управление и позицию головки.
Для этого состояние помещается непосредственно слева от обозреваемой клетки. Во избежание неоднозначности получаемой цепочки, состояния обозначаются символами, отличными от 8.2. МАШИНА ТЬЮРИНГА 331 ленточных. Таким образом, для представления МО используется цепочка ХХи..Х, >гуХХ.>...Х„. Здесь >у — состояние МТ, головка обозревает >-ю слева клетку, а Х>Хя...Х„ представляет собой часть ленты между крайними слева и справа значащими символами. Как исключение, если головка находится слева или справа от значащих символов, некоторое начало или окончание Х>Х,...Х„пусто, а > имеет значение, соответственно, 1 или и. Переходы МТ М = Щ Е, Г, 4 >уж В, Р) описываются с помощью отношения )-, ис- пользованного для МП-автоматов.
Подразумевая МТ М, для отображения переходов используем (-. Как обычно, для указания нуля или нескольких переходов МТ М использу- ется отношение )- или !-. Пусть >>(>у, Х) = (Р, У, У), т,е. головка сдвигается влево. Тогда Х>Х>...Х >>уХХ->...Х„( Х>Хи..Х, >РХ, >УХ,,>...Хп. Заметим, как этот переход отображает изменение состояния на Р и сдвиг головки на клетку > — 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
