Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гросс М. -> "Теория формальных грамматик " -> 33

Теория формальных грамматик - Гросс М.

Гросс М., Лантен А. Теория формальных грамматик — М.: Мир, 1971. — 296 c.
Скачать (прямая ссылка): teoriyaformalnihgrammatik1971.djvu
Предыдущая << 1 .. 27 28 29 30 31 32 < 33 > 34 35 36 37 38 39 .. 101 >> Следующая


93

Если теперь положить X =» Л, то

Я, O Wx ФИ ^Wx.

Полученное противоречие доказывает, что множество О не является рекурсивным.

5.4.6. Проблема остановки для произвольной машины Тьюринга

Когда некоторой машине Тьюринга предлагается исходное задание, возможны ровно два взаимоисключающих случая:

— машина когда-нибудь останавливается, выдавая определенный результат;

— машина работает вечно.

Можно сформулировать следующую проблему: существует ли машина Тьюринга Г, для которой входными заданиями являются пары и которая, получив на вход пару

[z = ng(Z); X],

отвечает

— либо «Да; машина Z, имеющая гёделевский номер г, начав вычисления с X, выдаст некоторый результат»;

— либо «Нет; предлагать машине Z задание X не следует—¦ она никогда не остановится»?

Предположим, что такая машина T существует. Пусть E — рекурсивно перечислимое, но не рекурсивное множество; мы знаем, что такие множества существуют!

Множество E есть область определения некоторой частично вычислимой функции U вычисляемой машиной Za Машина T для любого натурального числа х давала бы один из двух ответов: «Да, х^Е и Za остановится»; «Нет, X ф E и Za не остановится».

Это означало бы, что E — рекурсивное множество, а такой вывод противоречит исходному предположению. Следовательно, имеет место

Теорема. Общая проблема остановки для произвольных машин Тьюринга неразрешима.

§ 5.5. ЗАМЕЧАНИЯ И ДОПОЛНЕНИЯ

5.5.1. Реальные вычислительные машины

Мы называем машину U универсальной, если она вычисляет функцию Qz (X). Когда этой машине в качестве исходного задания предложена пара (z, X), она выдаст тот результат, который получила бы, исходя из X, машина Z, гёделевский номер которой ng (Z) = z.

Это замечание делает очевидной аналогию между универсальной машиной Тьюринга U и электронными вычислительными 94

Часть /. Предварительные сведения из логики и алгебры

машинами (ЭВМ). Машина U соответствует ЭВМ, a z — конкретной программе, которую вводят в ЭВМ вместе с исходным заданием и которая осуществляет над этим заданием вычислительные операции.

Тем самым проблема остановки (иначе, проблема применимости) обретает следующий конкретный смысл. Пусть имеется программа P и входные данные б; спрашивается, существует ли такая общая программа G, которая позволяет заранее выяснить, остановится ли машина, начав вычисления по программе P с входными данными 6. Ответ является отрицательным: подобной программы G не существует. В частности, это означает, что никогда не будет написана программа, с помощью которой можно было бы обнаруживать в любых программах ошибки, приводящие к бесконечным вычислениям.

5.5.2. «Философское» отступление

Результаты, относящиеся к неразрешимости тех или иных проблем, отнюдь не дают повода для каких-либо философских рассуждений на тему о сравнении возможностей человека и машины Дело обстоит просто: в рамках некоторой математической теории удается доказать несуществование определенных объектов, точно так же как в арифметике доказывается несуществование рационального числа, квадрат которого был бы равен 2.

Открытие иррациональных чисел поставило перед древнимн греками целый ряд метафизических проблем; это объясняется тем, что подобное открытие опрокидывало «наивное» представление о мире, основанное на отношениях между целыми числами. Что же касается понятия неразрешимости, то оно ничего не опрокидывает. Неразрешимость той или иной проблемы означает всего лишь, что эта проблема плохо поставлена. Дальнейшее поведение исследователя определяется конкретной природой проблемы. Иногда целесообразно перейти к рассмотрению частных случаев, для которых данная проблема разрешима и может быть подвергнута математи ческому изучению. Бывает, однако, и так, что необходимо все же иметь дело с общим случаем (ибо именно он представляет прагматический интерес); тогда приходится «выкручиваться кто как может»— или, выражаясь более изящно, использовать эвристические методы1). Конкретный пример такой ситуации — поиск правил, позволяющих обнаружить ошибки программирования, ведущие к за цикливанию, весьма практичным, хотя и не на 100% надежным способом. Другой пример — поиск методов вычислений, для которых существовала бы общая процедура обнаружения ошибок.

') Возможна также ситуация, когда решающий проблему алгоритм существует, но практически не может быть реализован ввиду своей чрезвычайной сложности. При этом нередко удается доказать, что для той или иной проблемы простых алгоритмов нет.—Прим. ред. Гл. V. Вычислимость и разрешимость

95

5 5.3. Замечание о рекурсивных функциях

Для рекурсивных функций, играющих столь важную роль в математической логике, существует много различных (эквивалентных) определений. Следуя М. Дэвису, мы приведем здесь определение Джулии Робинсон. (Читатель сразу же поймет, как интерпретировать это определение с точки зрения теории машин Тьюринга.)

Определение. Функция называется частично рекурсивной, если ее можно построить путем конечного числа применений операций композиции и минимизации из следующих основных функций:
Предыдущая << 1 .. 27 28 29 30 31 32 < 33 > 34 35 36 37 38 39 .. 101 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed