Непейвода Н.Н. Прикладная логика

Подождите немного. Документ загружается.

13.2. АКСИОМАТИЧЕСКОЕ ОПИСАНИЕ ВЫЧИСЛИМОСТИ

351

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

ровки Дж. Маккарти. Заметим, что простейшие композиции, в которых

последним применялся предикат, можно сами рассматривать как преди-

каты, поскольку любое их возможное значение может быть только ло-

гическим. Такие предикаты будем называть простейшими алгоритмиче-

скими. Определим условные термы следующим образом:

Определение 13.2.1.

Если

— простейшая композиция, то

— услов-

ный терм.

Если

— простейший алгоритмический предикат, а

— условные

термы сигнатуры

, то

if P then t else u ﬁ

условный терм той же сигнатуры. Его значения определяются следую-

щим образом:

if P then t else u ﬁ → b

(P & t → b) ∨ (

P & r → b).

⇔

Таким образом, если условие не определено, то условный терм тоже

не определен, а вот если одно из выражений не определено, то условный

терм может быть определен.

(Аксиома о рекурсивном определении)

Если все функ-

ции сигнатуры

проинтерпретированы как алгоритмы,

не

входит в

, а

t(ψ, x)

— условный терм со свободной пере-

менной

в сигнатуре

, пополненной

, то имеется алго-

ритм, такой, что

ψ(a) → b ⇔ t(ψ, a) → b.

Его определение записывается в форме

ψ(x) ← t(ψ, x).

Пример 13.2.1.

Рекурсивное определение функции, выделяющей из

кортежа первый элемент, может быть задано следующим образом:

FIRST(x) ←

if ATOM(x) then NULL else

if NIL(x) then NULL else

if SIMPLE(x) then TAIL(x) else

FIRST(BODY(x))

ﬁ ﬁ ﬁ

352

ГЛАВА 13. НЕПОЛНОТА И НЕФОРМАЛИЗУЕМОСТЬ

Заметим, что мы умалчивали, какое же значение принимают исходные

функции на неподходящих аргументах (скажем,

BODY

, если ей подать

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

просто определять новые алгоритмы так, чтобы сомнительные случаи

исключались заранее (оставались в другой альтернативе условного тер-

ма). Так что если нам зачем-то нужна всюду определенность элементар-

ных композиций, то эти функции можно доопределить произвольным

образом.

Пример 13.2.2.

Поскольку мы доказали, что не все алгоритмы опреде-

лены на всех значениях, естественно ожидать, что наша главная опера-

ция рекурсивного определения приводит к неопределенным функциям.

И в самом деле, рассмотрим

ERR(x) ← APPEND(ERR(APPEND(x, NULL)), NULL).

Вычисление данного алгоритма не может привести ни к какому резуль-

тату ни при каком значении

. В самом деле, результат должен быть

кортежом, поскольку последней применяется функция

APPEND

. Тогда

результат для

[x, NULL]

должен быть на один элемент короче, и так да-

лее. Получается бесконечный спуск в длинах значений.

Заметим, что при стандартной семантике рекурсивных процедур не

определен гораздо более простой алгоритм:

ERR1(x) ← ERR1(APPEND(x, NULL)).

Но здесь логически привести к противоречию предположение о суще-

ствовании значения не удается, и можно представить себе семантику

алгоритмического языка, раскрывающего такие определения в тожде-

ственную функцию (тоже подходящую в качестве решения такого ре-

курсивного уравнения).

Из неопределенности вычислимых функций (функций, определяе-

мых алгоритмами) следует, что не для всякого предиката множество его

истинности можно задать всюду определенным вычислимым предика-

том. Появляются следующие определения:

Определение 13.2.2.

Множество называется

разрешимым

, если имеет-

ся всюду определенный алгоритм, вычисляющий его характеристиче-

скую функцию (таким образом, данный алгоритм должен всегда давать

значение, логическое значение, и только одно из логических значений;

такой алгоритм называется

вычислимым предикатом

). Множество на-

зывается

перечислимым

, если имеется однозначный алгоритм, дающий

13.2. АКСИОМАТИЧЕСКОЕ ОПИСАНИЕ ВЫЧИСЛИМОСТИ

353

значение

ИСТИНА

тогда и только тогда, когда элемент принадлежит дан-

ному множеству

Например, множество троек hA, a, bi, где A — код алгоритма, таких,

что алгоритм с кодом A дает значение b на входных данных a, является

перечислимым, но не разрешимым.

Заметим, что дополнения некоторых перечислимых множеств мо-

гут быть неперечислимы. Чтобы легче показать это, рассмотрим еще

одну аксиому вычислимости, которая не столь обязательна, как преды-

дущие, отражая желательное и выполняющееся почти всегда в реализа-

циях свойство вычислений. А именно, мы выразим, что алгоритмы вы-

полняются шаг за шагом и выдают решение через конечное число ша-

гов. Соответственно, привлекая компьютерные аналогии, мы вспомина-

ем, что некоторые программы не переводятся машиной на свой язык, а

исполняются шаг за шагом при помощи специальной программы-интер-

претатора. Существование интерпретатора — более сильное свойство,

чем даже существование универсальной функции, и может быть запи-

сано следующим образом:

(Аксиома перечислимости)

Имеется такой разрешимый

предикат

, что для любого алгоритма

ϕ ϕ(a) → b

тогда и

только тогда, когда имеется кортеж

, первым членом ко-

торого является пара

[dϕe, a]

, все последующие члены име-

ют вид

[d$

e, a

]

, где

— некоторый алгоритм, а послед-

ний —

[NULL, b]

, на котором

Ψ(C) =

ИСТИНА

Ψ можно интерпретировать как предикат, проверяющий, является ли

данная конечная последовательность пар начальным отрезком вычисле-

ния некоторого алгоритма.

Если принять аксиому перечислимости, то, в частности, для нату-

ральных чисел любое множество, такое, что и оно само, и его дополне-

ние являются перечислимыми, разрешимо. Правда,для действительных

чисел и других сложных (не кодируемых достаточно просто натураль-

ными числами) объектов ситуация может быть несколько сложнее.

Порою нужна не разрешимость, а более слабое понятие: отдели-

мость.

Но, конечно же, этот алгоритм может не давать никакого значения, если элемент

множеству не принадлежит.

354

ГЛАВА 13. НЕПОЛНОТА И НЕФОРМАЛИЗУЕМОСТЬ

Определение 13.2.3.

Множество

Z отделяет

два непересекающихся мно-

жества

, если

X ⊂ Z

Y ⊂

Таким образом, отделимость — понятие относительное. Она зави-

сит от рассматриваемой системы множеств и универса.

Теорема 13.2. (Теорема о неотделимости)Имеются два перечислимых

множества

X и Y , таких, что нет разрешимого множества Z, отде-

ляющего их.

Идея доказательства.В качестве таких двух множеств можно взять

{[x, y] | Υ ([x, y]) → 0},

{[x, y] | Υ ([x, y]) → 1}.

Если предикат равенства вычислим, то любые два одноэлементных

множества отделимы.Но, скажем, для действительных чисел естествен-

но,в частности,рассматривать вычислимость на базисе некоторых стан-

дартных непрерывных аналитических функций (∙, +, −, \, exp, sin, cos,

ln...) и предиката <, определенного как частичный, чтобы сохранить

непрерывность: если x = y, то значение x < y не определено. Поэто-

му естественно появляется понятие отделимых элементов: два элемента

отделимы, если есть вычислимый предикат, истинный на одном из них

и ложный на другом.

Имеется просто формулируемая и общая теорема, показывающая,

что для свойств вычислимых функций нельзя почти никогда надеять-

ся на разрешимость. Детерминированный алгоритм

ϕ называется экс-

тенсиональным по первому аргументу, если для всех A и B, таких, что

функции, ими вычисляемые, одинаковы, имеем ϕ([A] ∗ X) → y ⇔

ϕ([B] ∗ X) → y. Таким образом, он на одинаковых функциях дает оди-

наковые результаты.

Теорема 13.3. (Теорема Успенского-Райса) Пусть предикат равен-

ства разрешим. Тогда, если экстенсиональный алгоритм всюду опре-

делен, то он не зависит от первого аргумента, т. е.

∀x, y (x, y — коды алгоритмов ⇒

∀z, u (ϕ([x] ∗ z) → u ⇔ ϕ([y] ∗ z) → u)).

Доказательство. Рассуждаем от противного. Пусть есть такое z, что

ψ = λx ϕ([x] ∗ z) не является тождественной функцией.

13.2. АКСИОМАТИЧЕСКОЕ ОПИСАНИЕ ВЫЧИСЛИМОСТИ

355

Пусть

ERROR

— нигде не определенная функция, а e — код одного

из алгоритмов, ее вычисляющих. Пусть ϕ([e] ∗ z) → a. Тогда, по экс-

тенсиональности ϕ, для любого кода e

нигде не определенной функ-

ции ϕ([e

] ∗ z) → a. Поскольку ψ не является тождественной, найдется

такой код

, соответствующий некоторой вычислимой функции

, что

ϕ([d] ∗ z) → b. Теперь построим следующее определение:

ξ(f, x, y) ← if ATOM(Υ(f, x) then χ(y) else χ(y) ﬁ. (13.6)

Эта функция нигде не определена, если

f(x)не определено, а в против-

ном случае, при фиксированных f, x дает χ. Таким образом, прове-

ряя, чему равно ϕ(λy ξ(f, x, y)), мы могли бы проверить, применима ли

функция к аргументу, что является неразрешимой проблемой.

И наконец, рассмотрим систему алгоритмов, которая обычно пред-

ставляется в книгах по теории вычислимости. Она может быть описана

следующим образом.

Имеется бесконечно много атомов — натуральные числа. Истину ото-

ждествляем с 1, ложь — с 0. Имеются две исходные функции и один

предикат, определенные на атомах:

S(n), дающая по n n + 1,

Pd(n), дающая по n > 0 n − 1, a для 0 —

NULL

;

Z(n), предикат, проверяющий, равен ли его аргумент 0.

Такие алгоритмы,конечно же,детерминированы,поскольку детермини-

рованы исходные функции,и называются рекурсивными функциями.Со-

ответственно, множества, разрешимые при помощи рекурсивных функ-

ций, называются рекурсивно разрешимыми, а перечислимые с их помо-

щью — рекурсивно перечислимыми.

Пример 13.2.3.

Построим алгоритм, осуществляющий сложение двух

натуральных чисел:

PLUS([m, n]) ← if Z(n) then m else PLUS([m, Pd(n)]) ﬁ.

Другой способ определения алгоритмов дан в определении оператора

, строящего минимальное значение

, при котором

φ([m, n]) = 0

Muk(φ, [m, k]) ← if Zφ(m, k) then k else Muk(φ, [m, S(k)]) ﬁ;

Mu(φ, m) ← Muk(φ, [m, 0]).

356

ГЛАВА 13. НЕПОЛНОТА И НЕФОРМАЛИЗУЕМОСТЬ

Здесь сначала вводится вспомогательный алгоритм, а сама рекурсия идет

в другом направлении, чем обычно. Такая операция часто обозначается

квантором минимизации

, введенным Д. Гильбертом:

μn P (n),

где

— алгоритмический предикат.

Есть экспериментальный факт, степень подтвержденности которого

в настоящий момент неизмеримо выше, чем у любого естественнонауч-

ного принципа: все изобретенные детерминированные алгоритмы вы-

ражаются как рекурсивные схемы над примененным базисом исходных

функций. Этот факт имеет и теоретическое подтверждение, но уже тре-

бующее перехода к неклассической логике. Если несколько ограничить

логические средства так, чтобы существование означало построение, то

из полученного доказательства можно извлечь рекурсивное определе-

ние способа построения искомого объекта через функции, осуществля-

ющие построение результатов примененных утверждений. Как и приня-

то в естественных науках, это экспериментальное наблюдение возведе-

но в ранг общего утверждения, но в отличие от, скажем, законов Ньюто-

на скромно называется тезис Черча (может быть, правильнее было бы

добавить сюда еще и фамилию Тьюринга

Алан Тьюринг — английский математик, в конце 30-х гг. создавший математиче-

скую модель простейшей вычислительной машины, пригодной для вычисления всего

того, что можно фактически сделать в математике. Эта машина имеет память в виде

ленты, в каждой ячейке которой стоит символ 0 либо 1, и программу, записанную в

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

состоит в анализе одной из ячеек ленты, записи туда нового значения, сдвиге на одну

ячейку влево или вправо и переходе к явно указанной следующей команде. Во время

второй мировой войны он внес немалый вклад в победу союзников, обеспечив нечита-

емость английских шифров для немцев и дешифровку немецких, а также улучшив ме-

тоды расшифровки сигналов радиолокаторов. После войны он опубликовал небольшую

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

вопрос «Может ли машина мыслить?» должен решаться не на эмоциональном уровне,

а при помощи точных критериев того, что такое мышление. Он предложил в качестве

одного из таких критериев тест Тьюринга:

Если машина может длительное время поддерживать телетайпный

диалог с человеком, сидящим в другом помещении и не знающим,

кто его партнер, и тот уверен, что разговаривал с человеком, то она

может считаться разумной.

Этот тест в его примитивном понимании был опровергнут Дж. Вейценбаумом, но в дан-

ном случае и сама формулировка такого теста, и его опровержение внесли блестящие

13.2. АКСИОМАТИЧЕСКОЕ ОПИСАНИЕ ВЫЧИСЛИМОСТИ

357

Любой содержательный алгоритм выражается в любой из

принятых в настоящее время в математике формализаций

понятия алгоритма (в частности, как рекурсивная схема).

Из этого тезиса следует строгое утверждение, которое доказано для всех

используемых в математике понятий алгоритма: все они эквивалентны в

том смысле, что алгоритмически определимые функции над минималь-

ным базисом понятий совпадают

. Но еще более важно то, что для всех

явно выделенных в математике способов построения алгоритмов найде-

но их представление, согласующееся с тезисом Черча

Упражнения к § 13.2

13.2.1. А почему мы не взяли в качестве множества структур более про-

стое множество

∞

13.2.2. В доказательстве предложения о невозможности всюду опреде-

ленного универсального алгоритма есть неточность. Попробуй-

страницы в историю околокомпьютерной методологии, в которой на самом деле мало

утверждений,не являющихся благоглупостями и требующих серьезного опровержения.

Почти сразу после публикации книги А. Тьюринг умер.

Тут есть две ловушки. Во-первых, совпадение определимости не означает сопоста-

вимости ресурсов, необходимых для вычисления данной конкретной функции различ-

ными понятиями алгоритма. Так что утверждение, что все можно вычислить на ма-

шине Тьюринга, является математической демагогией, когда применимость подменяют

определимостью. Во-вторых, если исходный базис брать не минимальным и общепри-

нятым, а произвольным (как делали мы), то даже определимость начинает различаться.

Рекурсивные схемы — один из мощнейших в смысле относительной определимости

аппаратов теории алгоритмов.

Есть одно исключение, найденное автором. Если имеются вращающиеся черные ды-

ры, то в принципе можно организовать вычислительный процесс таким образом, чтобы

получить ответ на неразрешимую задачу, но при этом нужно самому успешно совер-

шить путешествие сквозь такую черную дыру в другую вселенную. Таким образом, в

некотором смысле тезис Черча и общая теория относительности друг другу противоре-

чат. На самом деле именно логики порою выдвигали обоснованные возражения против

теории относительности, слишком часто подвергавшейся неквалифицированной кри-

тике. Так, Курт Гёдель построил пример вселенной, в которой время может идти по

кругу, и тем самым опроверг мнение Эйнштейна,что из общей теории относительности

должна следовать однонаправленность времени (после чего сам А. Эйнштейн выдвинул

эту работу на одну из самых престижных научных премий). Серьезная теория требует

глубоких возражений, а глубинные взаимосвязи научного знания гораздо сильнее, чем

можно вообразить, наблюдая современную науку, разделенную на почти невзаимодей-

ствующие отрасли.

358

ГЛАВА 13. НЕПОЛНОТА И НЕФОРМАЛИЗУЕМОСТЬ

те найти ее и исправить, чуть-чуть видоизменив построения и не

вводя в рассмотрение никаких новых случаев.

13.2.3. А почему это мы не потрудились ввести логические связки в ак-

сиоматику алгоритмов? Можно ли их там выразить?

13.2.4. Верно ли, что разрешимые множества образуют булеву алгебру?

13.2.5. Постройте алгоритм,выделяющий первый элемент кортежа. По-

трудитесь, чтобы он был всегда определенным.

13.2.6. Постройте алгоритм, вычисляющий соединение кортежей.

13.2.7. Пусть алгоритм

ADD([n, m]) определен тогда и только тогда, ко-

гда n, m — атомы,являющиеся целыми числами, и выдает их сум-

му. Постройте алгоритм

SUM

суммирования всех членов кортежа.

13.2.8. Постройте алгоритм умножения двух натуральных чисел.

13.2.9. Постройте предикат, проверяющий равенство двух натуральных

чисел.

13.2.10. В наших последних примерах была одна вольность речи: мы

определяли рекурсией не

φ(x), а φ([m, n]). Как ее устранить? На-

много ли удлинятся при этом определения?

13.2.11. Студент Лыцаренко дал следующее доказательство того, что

при выполнении аксиомы перечислимости любое перечислимое

множество с перечислимым дополнением разрешимо:

Пусть алгоритм

ϕ перечисляет само множество, а ψ — его допол-

нением. Рассмотрим алгоритм типа алгоритма британского му-

зея. Будем перебирать все кортежи из пар, первая пара в которых

[dϕe, a] либо [dψe, a], и проверять каждый из них универсальным

интерпретатором, не является ли он вычислением, и если являет-

ся,получилась ли в результате истина. Поскольку один из алгорит-

мов перечисляет множество, а другой — его дополнение, в конце

концов один из них выдаст истину.

Можете ли Вы найти слабое место в данном рассуждении, и когда

оно верно?

13.3. ПРЕДСТАВИМОСТЬ ЧЕРЕЗ ДОКАЗУЕМОСТЬ

359

13.2.12. Студент Классиков заявил, что не всюду определенные функ-

ции — это извращение конструктивистов и информатиков, без них

всегда можно обойтись. В самом деле,дополним наш универс эле-

ментом

ОШИБКА

. Положим, что любой кортеж, содержащий та-

кой элемент,равен ему,и что любой алгоритм на аргументе

ОШИБ-

КА

выдает значение

ОШИБКА

, и тогда все становится на свои ме-

ста. Неопределенный в данной точке алгоритм просто выдает в

ней значение

ОШИБКА

. Можете ли Вы что-нибудь возразить?

13.2.13. После того, как его предыдущее рассуждение вызвало непони-

мание отдельных коллег, Классиков заявил, что они вообще за-

нимаются плохой математикой и, в частности, нарушают прин-

цип бритвы Оккама. Ваши рекурсивные функции можно было бы

определить как алгоритмы, получающиеся в пустой исходной сиг-

натуре (т. е. лишь из тех операций, которые есть в аксиомах,и кон-

станты

NULL

). А что Вы ему на это скажете?

13.2.14. Обобщите по возможности теорему Райса на случай, когда экс-

тенсиональный алгоритм дает на различных функциях два отде-

лимых значения.

§ 13.3. ПРЕДСТАВИМОСТЬ ЧЕРЕЗ ДОКАЗУЕМОСТЬ

В данном параграфе и далее до конца главы теории, если

иное явно не оговорено, имеют разрешимое множество ак-

сиом

Выразимости понятий порою недостаточно для того, чтобы коррект-

но работать с ними формальными методами. Дело в том, что даже вы-

разимые понятия могут находиться в достаточно сложных отношениях

с понятием доказательства. Если нечто — истина, это не обязательно

можно доказать принятыми формальными средствами

. Поэтому на-

На практике неясно, как использовать теорию, если даже понятие ‘быть аксиомой’

нельзя проверить.

В качестве иллюстрации смотрите судебную практику, но она еще хуже, посколь-

ку там средства доказательства внутренне противоречивы и позволяют порою доказать

ложь.

360

ГЛАВА 13. НЕПОЛНОТА И НЕФОРМАЛИЗУЕМОСТЬ

до посмотреть, для каких же классов понятий доказуемость совпадает с

истинностью.

Очевидно, что надеяться на это можно лишь для разрешимых мно-

жеств. Но оказывается, что и, наоборот, любое разрешимое множество

выразимо таким способом.

Рассмотрим базовую формализацию арифметики. Ее аксиомы прак-

тически всегда выполнены в математических теориях, включающих как

минимум натуральные числа. Эта аксиоматика известна как арифмети-

ка Пеано.

Сигнатура содержит предикат равенства, константу 0 и три функци-

ональных символа:

одноместный

S, интерпретируемый как прибавление 1;

два двуместных — сложение и умножение, с обычной интерпретацией.

Сложение и умножение будем записывать как бинарные операции.

Теория имеет бесконечно много аксиом, но почти все они

выража-

ются единой формулой со свободной предикатной переменной: прин-

ципом математической индукции.

A(0) & ∀x(A(x) ⇒ A(S(x))) ⇒ ∀x A(x). (13.7)

Следующая аксиома утверждает, что 0 — начальный элемент натураль-

ного ряда:

∀x

S(x) = 0.

Далее идет свойство, утверждающее его линейность:

∀x ∀y(S(x) = S(y) ⇒ x = y).

Далее — свойства сложения, умножения и возведения в степень

, а на

самом деле их рекурсивные определения через S:

∀x(x + 0 = x) ∀x ∀y(x + S(y) = S(x + y))

∀x(x ∙ 0 = 0) ∀x ∀y(x ∙ S(y) = x ∙ y + x)

∀x(x ↑ 0 = 1) ∀x ∀y(x ↑ S(y) = x ↑ y ∙ x)

В математике слова ‘почти все’, как правило, имеют точный смысл. В частности,

для счетного множества это почти всегда (уже в обыденном смысле) означает ‘всегда,

за исключением конечного числа элементов’. Тем не менее на математическое ‘почти

всегда’тоже нужно полагаться с оглядкой:ведь конечное число исключений может быть

больше, скажем,

Со времен Геделя известно, что возведение в степень можно определить через сло-

жение и умножение внутри арифметики, но нам не нужно быть до такой степени пури-

стами: с возведением в степень конструкция становится прозрачнее, а во всех распро-

страненных математических теориях оно все равно необходимо.