Имеет ли все это значение?
Еще одна выдержка из [1]:
Если язык Tutorial D является неразрешимым, то рано или поздно пользователь или система попытаются вычислить неразрешимый оператор, и это приведет к отказу реализации. Вы может возразить, указав, что этого не происходит в вычислительно полных языках, таких как Ada, Pascal, Fortran или Java. Но вы будет не правы. В действительности, нетрудно закодировать бесконечный процедурный цикл, который не распознает никакой компилятор.
Более точно, как мы видим, в [1] утверждается, что с реляционным языком должна быть ассоциирована процедура разрешения («должна существовать процедура разрешения для вычисления любого логического выражения»). Но корректно ли это утверждение? В исчислении предикатов отсутствует процедура разрешения, но, по крайней мере, можно придумать некоторую процедуру, являющуюся полной и совершенной (sound and complete). В моем пересказе в [10] говорится следующее:
Для заданной правильно построенной формулы исчисления предикатов такая процедура будет корректно возвращать TRUE в том и только в том случае, когда формула вычисляется в TRUE; однако, если формула вычисляется в FALSE, то процедура либо выдаст FALSE, либо будет выполняться бесконечно. (Другими словами, если формула истинна, то она является доказательно истинной; однако если она ложна, то не является доказательно ложной.)
Поэтому на практике мы можем включить такую процедуру в реализацию системы. Более того, мы можем включить в процедуру механизм тайм-аутов, так что, если вычисление некоторого заданного выражения не завершается в течение некоторого предопределенного периода времени, систем прекращает вычисление и возвращает пользователю сообщение типа Слишком сложное выражение. (Конечно, она не должна возвращать TRUE или FALSE! Иначе мы вернулись бы к тому, что Кодд – совсем в другом контексте – называл «строго некорректным» результатом [5].)
Следовательно, резюмирую:
- Очевидно, нам хотелось бы иметь систему, в которой все возможные выражения могли бы вычисляться за конечное время.
- Этой цели невозможно достичь, если мы настаиваем на вычислительной полноте.
- Однако мы хотя бы знаем об этом, и можем к этому подготовиться.
- В частности, мы можем встроить в систему код, который позволит выдавать в ответ на некоторые запросы сообщения типа «Я не могут ответить на этот запрос, потому что он слишком сложен».
В заключение я хотел бы отметить следующее:
- При общении на естественном языке часто бывает невозможно точно ответить на некоторые вопросы. С такими ситуациями мы сталкиваемся постоянно. Поэтому система, которая иногда выдает сообщение Слишком сложное выражение, не является полностью бесполезной.
- В любом случает, даже при отсутствии вычислительной полноты, вполне вероятно существование запросов, на которые в принципе можно ответить за конечное время, но это время является настолько большим, что ответа дождаться практически невозможно. Другими словами, проблема неразрешимости существует и при отсутствии вычислительной полноты. И поэтому наше прагматическое решение этой проблемы (реализация механизма тайм-аутов), по-видимому, требуется в любом случае.
- Наконец, если вычислительная полнота ведет к отсутствию разрешимости, то, следовательно, неразрешимы традиционные языки программирования. Но мы благополучно уживаемся с этой проблемой на протяжении многих лет, и я не думаю, что она вызывает непреодолимые трудности. Чем в этом отношении отличаются языки баз данных?
