Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 42
Текст из файла (страница 42)
Можно использовать для формирования циклон и безусловные переходы посс. То есть по внутренней логике машина Тьюринга аналогична конечному автомату, который был рассмотрен ранее. 2. Положение управляющей головки может быть изменено таким образом, чтобы она указывала на ячейку рабочей ленты, расположенную слева или справа от текущей. В каждый момент времени рабочая лента состоит из конечного числа заполненных ячеек, но при сдвиге управляющей головки на позицию вне этих ячеек к ним автоматически справа или слева добавляется новая ячейка с записанным в нее пустым символом.
В начальный момент времени в ячейках рабочей лепты машины Тьюринга содержатся входные данные, а управляющая голонка позиционирована на самую левую ячейку. Машина Тьюринга выполняет последовательность описанных выше простых операций, модифицируя содержимое ячеек рабочей ленты (при необходимости добавляя новые). Если в итоге она останавливается, то в ячейках рабочей ленты содержатся вычисленные результаты.
Машина Тьюринга — это чрезвычайно простая абстрактная машина. Обратите внимание на то, что она даже не способна производить арифметические действия. 150 Глава 4. Моделирование свойств языка Если вы захотите с ее помощью сложить два числа, то вам придется для этого создать программу, используя только указанные выше элементарные операции. Не допускаются никакие другие переменные или структуры данных.
Для хранения пан ных используется одна только рабочая лента (но при этом важно учесть, что ее возможности хранения ланных не ограничены). Может ли машина Тьюринга делать что-нибудь полезное? Можно привести несколько примеров программ, которые убедят вас, что машину Тьюринга можно использовать по крайней мере для выполнения таких простых действий, как сложение и вычитание. Но на самом деле можно доказать гораздо более сильное утверждение: машина Тьюринга может производить любые полезные действия в области вычислений! Таким образом, мы попытаемсядоказать, что любое вычисление может быть выражено в виде программы для машины Тьюринга и, следовательно, язык машины Тьюринга является универсальным языком, хотя в нем предусмотрена только одна структура данных (вектор) и нс определены никакие арифметические операции, отсутствуют определения подпрограмм и прочие структуры, стандартные лля обычных языков программирования.
Формальное выражение этой идеи известно как тезис Черча (Спцгсп) (того же Черча, которого мы упомянем в развело 4.2). Любая вычислимая фуггхг(ия может быть вычислена при помощи мишины Тьюринга. Этот тезис не является теоремой, которую можно доказать. Тезис Чсрча — это некоторая гипотеза, которую, в принципе, можно опровергнуть. Но лля этого потребуется предьявить какую-нибудь функцию, которая может быть вычислена посредством другого языка программирования и нс может быть вычислена на машине Тьюринга.
Тем не менее исследованием тезиса Черча в течение многих лет занимались многие математики; были предложены многочисленные абстрактные н реальные вычислительные машины и языки программирования. Но каждый раз удавалось доказать, что очередной метод, предложенный для создания универсального языка или универсальной вычислительной машины, на самом деле является не более мощным, чем машина Тьюринга. То есть любая функция, которую можно было вычислить при помощи нового языка нли новой машины, могла быть вычислена и с помо|цью машины Тьюринга.
При рассмотрении языков программирования следует иметь в вплу, что машина Тьюринга эквивалента грамматике типа О, которую мы обсуждали в предыдущем разделе этой главы. Достаточно легко показать, что любое состояние машины Тьюринга можно смоделировать прн помощи некоторого вывода грамматики типа О. Аналогично любая грамматика типа О распознается при помощи (недетерминированной) машины Тьюршп а. Тот факт, что (в отличие от контекстно-своболных грамматик) недетерминированные и летерминированные машины Тьюринга эквиваленты, может вызвать некоторое удивление. То есть любое вычисление, проволимое прн помощи недетерминированной машины Тьюринга, можно произвести, используя эквивалентную детерминированную машину Тьюринга.
Машина Тьюринга является примером того, что для достижения универсалыюсти ие требуется почти никаких аппаратных средств, за исключением неограниченной памяти. Даже чрезвычайно простой набор структур данных и операций оказывается достаточным для выражения любой вычислнмой функции. 4д. Формальные свойства языков 151 Проблема останова Изучение машин Тьюринга и языков привело к некоторым другим важным результатам, в том числе к тому, что некоторые задачи являкпся нераэрешимььви. Это означает, что для их решения ие сугцествует никакого общего алгоритма, даже в контексте описанных простых абстрактных машин. Рассмотрим подробнее уже упоминавшийся ранее в этой главе вопрос о программе, определяющей, завершится ли когда-нибудь выполнение другой программы, написанной иа языке С. Мы знаем, конечно, некоторые примеры программ иа С, выполнение которых обязательио завершится.
Например, программа авъч(( Пст к ) безусловно будет завершеиа. Фактически завершается выполиеиие любой программы иа С, которая состоит только из объявлений и операторов присваивания. Для того чтобы тестирующая программа могла определить такой тип программ, иеобходимо сделать следукицее; 1) взять какой-либо компилятор С; 2) исключить из НФБ-грамматики, определяющей язык С, все правила, которые включают какое-либо ветвление, вызов процедур или операторы цикла; 3) запустить компилятор, используя только получившийся урезанный набор правил грамматики языка С, Любая программа, откомпилированная при помогци такого модифицированного компилятора, может состоять только из операторов присваивания и неизбежно завершится после выполнения. Интерес представляют те программьц которые ие компилируются при помощи такого компилятора. Некоторые, очевидно, являются корректными, их выполнение будет завершено (иапример, те программы, в которых содержатся корректно работающие циклы); ио программы, в которых циклы работают неправильно, могут зациклиться и выполняться бесконечно.
Проблема заключается в том, что ие существует каких-либо общих критериев, позволяюших определить различия между этими типами программ. Предположим, что у вас имеется такая универсальная тестирующая программа и вы хотите с ее помощью проверить некоторую очень длинную программу (обозначим ес А). Допустим, вы задали предельно допустимое время проверки как 3 года; если в течение этого времени тестирующая программа ие сможет прийти к выводу, что программа А завершится, то будет считаться, что данная программа А никогда ие завершится.
По прошествии трех лет вы останавливаете работу тестируюшей программы и делаете вывод, что программа А никогда ие завершится. Но, возможно, если бы вы подождали еще (О минут, ответ был бы найден. Суть проблемы в том, что если речь идет о вещах, ие принадлежащих вычислимому множеству, мы просто ие зиаем, когда следует остановить выполнение программы и получить ответ. Наши ицтуитивиые рассуждения связаны отак называемой проблемой остаяовш существует ли какой-либо общий алгоритм, позволяющий определить, остаио- 152 Глава4. Моделированиесвойств языка вится ли через какое-нибудь время маи~ина Тьюринга, если в качестве входных данных ей была передана какая-либо конкретная строка символов? Исследования самого Тьюринга, проведенные в 1936 г., показали, что проблема останова неразрешима: не существует алгоритма решении задачи останона, общего для всех машин Тьюринга и для всех входных строк.
Для подтверждения неразрешимости какой-либо задачи мы показываем, что она эквивалентна задаче останова. Действительно, если бы рассматриваемая нами задача была разрешима, то была бы разрешима и залача останова. Но мы знаем, что это не так. Следовательно, исходная задача также неразрешима. Исследование атих простых универсальных языков и машин приводит нас к выводу, что любой язык программирования, который можно было бы использовать на практике, является универсальным, если проигнорировать ограничения, связанные со временем выполнения и объемом требуемой памяти.
Например, если какой-нибудь программист непоколебим в своем решении использовать только один язык программирования, например Б1БР, и утверждает. что «все можно сделать на 1.1Б Р», то он, строго говоря, прав. Можно сделать все, хотя какието вещи, возможно, будет сделать нелегко. Различия между языками программирования не являются качесглвеннььии — то есть они заключаются не в том, что решение каких-то задач возможно только при использовании определенных языков; этп различия носят количесглоенный характер и сводятся к тому, насколько легко, красиво и эффективно могут быть решены задачи на различных языках, Неоднозначность Иерархия типов грамматик Хомского является примером обычного для теоретических исследований явления: для описания какой-либо встречающейся на практике ситуации можно построить множество теоретических моделей, описывающих се различными способами. Некоторые из этих моделей оказываются менее полезными, чем другие, и легко забываются после непродолжительного их изучения.
Другие модели, в которых отражены какие-то важнгяе лля практики стороны изучаемой проблемы, становятся обшепринятыми. Контекстно-зависимые грамматики и грамматики с фразовой структурой в иерархии Хомского оказались неудачными моделями языков программирования. Хотя языки, определяемые грамматиками этих типов, являются более мощными, в то же время они сложнее для понимания, анализа и практического использования.
Впоследствии (при разработке новых грамматик) были сделаны попытки преодолеть ограничения, характерные для этих моделей. У НФБ-| рамматик имеется ряд достоинств. Их довольно просто использовать на практике, и они являются достаточно мощными, чтобы выразить большинство (но не все) синтаксических конструкций, которые необходимы в языках программирования (лингвисты считают, что для естественных языков такие грамматики менее полезны). К преимуществам НФБ-грамматик относится и то, что с помощью математического анализа такой грамматики легко обнаружить неявные свойства определяемого ею языка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
