Неразрешимость логики первого порядка (стр. 3 из 7)
Если обработка слова б переводит машину Тьюринга в заключительное состояние, то говорят, что она применима к б, в противном случае – не применима к б (машина работает бесконечно)
Рассмотрим пример:
Дана машина Тьюринга с внешним алфавитом А = {0, 1} (здесь 0 – символ пустой ячейки), алфавитом внутренних состояний Q = {q0, q1, q2} и со следующей функциональной схемой (программой):
q1 0 → 1 Л q2;
q1 1 → 0 Сq2;
q2 0 → 0 П q0;
q2 1 → 1 Сq1;
Данную программу можно записать с помощью таблицы
| 0 | 1 | |
| q1 | 1 Л q2 | 0 С q2 |
| q2 | 0 П q0 | 1 С q1 |
Посмотрим, в какое слово переработает эта машина слово 110, исходя из начального положения:
q1
| … | 1 | 1 | 0 | … |
На первом шаге действует команда: q1 0 → 1 Л q2 (управляющее устройство находится в состоянии q1, а в обозреваемой ячейке записана буква 0, в ячейку вместо 0 записывается 1, головка сдвигается влево, управляющее устройство переходит в состояние q2), в результате на машине создается следующая конфигурация:
q2
| … | 1 | 1 | 1 | … |
На втором шаге действует команда: q2 1 → 1Сq1 и на машине создается конфигурация:
q1
| … | 1 | 1 | 1 | … |
Третий шаг обусловлен командой: q1 1 → 0 Сq2. В результате нее создается конфигурация:
q2
| … | 1 | 0 | 1 | … |
Наконец, после выполнения команды q2 0 → 0 П q0 создается конфигурация
q0
| … | 1 | 0 | 1 | … |
Эта конфигурация является заключительной, потому что машина оказалась в состоянии остановки q0.
Таким образом, исходное слово 110 переработано машиной в слово 101.
Полученную последовательность конфигураций можно записать более коротким способом (содержимое обозреваемой ячейки записано справа от состояния, в котором находится в данный момент машина):
11q10 => 1q211 => 1q111 => 1q201 => 10q01
Машина Тьюринга – не что иное, как некоторое правило (алгоритм) для преобразования слов алфавита A
Q, т.е. конфигураций. Таким образом, для определения машины Тьюринга нужно задать ее внешний и внутренний алфавиты, программу и указать, какие из символов обозначают пустую ячейку и заключительное состояние.4. Доказательство неразрешимости проблемы остановки
Проблема остановки машины Тьюринга – это проблема построения такого алгоритма, который мог бы определить закончится или нет вычисление по некоторой задаче. Оказывается, что в общем случае такой алгоритм нельзя построить в принципе, то есть невозможно найти алгоритм, позволяющий по произвольной машине Тьюринга Т и произвольной ее начальной конфигурации qiajопределить придет ли машина Т в заключительное состояние q0, если начнет работу в этой конфигурации.
Если машина Т, запущенная в начальной конфигурации qiaj, останавливается (т.е. попадает в заключительное состояние) через конечное число шагов, то она называется самоприменимой, в противном случае – несамоприменимой.
Теорема.
Не существует машины Тьюринга М, решающей проблему самоприменимости, то есть проблема самоприменимости алгоритмически неразрешима.
Доказательство.
Предположим противное, то есть. пусть существует машина Тьюринга Т, решающая проблему самоприместимости в указанном выше смысле. Построим новую машину Т0, добавив новое состояние q0* и объявив его заключительным, а также добавив новые команды для состояния q0, которое было заключительным в Т:
q0 a1→ a1С q0 (1)
q0 a2→ a2С q0 (2)
…q0an→an С q0* (n)
Рассмотрим теперь работу машины T0.
Пусть M– произвольная машина. Если M– самоприменима, то начальная конфигурация q1ai перейдет с помощью команд машины T через конечное число шагов в конфигурацию q0a1, далее применяется команда (1), и машина T0 никогда не остановится. Если M– несамоприменима, то начальная конфигурация q1aiперейдет с помощью команд машины T через конечное число шагов в конфигурацию q0an, далее применяется команда (n), и машина T0 остановится.
Таким образом, машина T0 применима к кодам несамоприменимых машин Т и неприменима к кодам самоприменимых машин Т.
Теперь применим машину T0 к начальной конфигурации q1ai. Сама машина T0 является либо самоприменимой, либо несамоприменимой. Если T0 самоприменима, то по доказанному она никогда не остановится, начав с q1ai, и потому она несамоприменима. Если T0 несамоприменима, то по доказанному, она останавливается через конечное число шагов, начав с q1aj, и потому она самоприменима. Получили противоречие, следовательно проблема самоприменимости алгоритмически неразрешима, что и требовалось доказать.
Проблема остановки алгоритмически неразрешима, т. к. если бы она была разрешимой, то мы получили бы разрешимость проблемы самоприменимости.
5. Неразрешимости логики первого порядка
В математической логике и теории алгоритмов под разрешимостью подразумевают свойство формальной теории обладать алгоритмом, определяющим по данной формуле, выводима она из множества аксиом данной теории или нет. Теория называется разрешимой, если такой алгоритм существует, и неразрешимой, в противном случае.
Вывод неразрешимости логики первого порядка из неразрешимости проблемы остановки
Вообще, говорят, что проблема распознавания какого-либо свойства разрешима, если существует допускающий механическое вычисление тест (вычислимая, или эффективная, процедура), который, будучи применен к произвольному объекту соответствующего типа, по прошествии некоторого времени правильно классифицирует этот объект с точки зрения наличия или отсутствия у него некоторого свойства. (Слова «по прошествии некоторого времени» означают здесь «после некоторого конечного числа шагов».) Позитивным тестом называется эффективная процедура, устанавливающая по прошествии некоторого времени все случаи наличия соответствующего свойства и только их. Негативный тест – это эффективная процедура, обнаруживающая все случаи отсутствия свойства и только их. Проблема распознавания произвольного свойства разрешима тогда и только тогда, когда для него существует и позитивный, и негативный тесты; дело в том, что всякий объект может или обладать рассматриваемым свойством, или нет, и потому, обладая обоими тестами, можно применить их оба к интересующему объекту, выполняя поочередно шаги одного и другого, и после некоторого их количества обнаружить, обладает он этим свойством или нет. (Верно и обратное: всякий тест, устанавливающий через некоторое конечное число шагов, обладает данный объект рассматриваемым свойством или нет, реализует и позитивный, и негативный тесты для этого свойства) Нас будут интересовать сейчас свойства общезначимости и выполнимости, а в роли объектов «соответствующего типа» выступают формулы языка логики первого порядка.
Докажем, что для этих тестов не существует дополнительных – позитивного для выполнимости и негативного для общезначимости – и потому в логике первого порядка проблемы распознавания как общезначимости, так и выполнимости неразрешимы.
Докажем неразрешимость логики первого порядка от противного: покажем, что если бы соответствующий тест существовал, то проблема остановки оказалась бы разрешимой. Мы убедились, что проблема остановки неразрешима.
Наше доказательство от противного будет строиться так: мы покажем, как, располагая программой машины Тьюринга, а также натуральным числом n, можно эффективно построить такие конечное множество предложений Д и еще одно предложение Н, что Д ├ Н тогда и только тогда, когда рассматриваемая машина, будучи запущенной в состоянии n(т.е. когда она начинает работу в состоянии q1, считывая при этом самую левую единицу в сплошном массиве из n единиц на ленте с пустыми символами в остальных клетках), в конце концов останавливается. Таким образом, мы определяем некоторую интерпретацию машины Тьюринга I. Формула Н в интерпретации I говорит, что машина в конце концов остановится, а формула из множества Д описывают работу машины. Введем функцию следования ' (где i' = i + 1 для всякого i). Таким образом, если бы мы могли решить проблему распознавания общезначимости предложений, мы смогли бы эффективно решать, остановится в конце концов или нет данная машина Тьюринга, поскольку логическое следование Д ├ Н имеет место тогда и только тогда, когда общезначима импликация F1
F2 … Fk→H, где Fi 
Д (i = 1,2,… k).Будем считать, что клетки ленты машины Тьюринга занумерованы так: