А теперь про нечто полностью вычислительное

К. Дж. Дейт
Перевод - Сергей Кузнецов

Оригинал: And Now for Something Completely Computational

В некотором роде эта статья является продолжением, уточнением и развитием первой статьи цикла «Обсуждение некоторых критических замечаний в адрес Третьего Манифеста» «Гедель, Рассел, Кодд: Рекурсивная золотая чехарда». Что такое вычислительная полнота языка? Как связаны вычислительная полнота и неразрешимость? Полезна или вредна вычислительная полнота языка баз данных? Знал ли обо всех этих проблемах родоначальник реляционных баз данных Кодд? Обо всем этом в присущей ему полемической манере, но, как всегда, четко и убедительно пишет Крис Дейт.

С.Д. Кузнецов

И я когда-то к магам и святым Ходил, познанья жаждою томим, Я им внимал; но уходил всегда Чрез ту же дверь, как и являлся к ним.

Эдвард Фитцджеральд. ХАЙЯМИАДА (поэма).
Перевод: О. Румер

Аннотация

В нашем с Хью Дарвеном Третьем Манифесте (для краткости, просто «Манифесте») устанавливается набор предписаний и запретов, которые касаются разработки языка программирования баз данных, называемого D (см. [9]). В частности, одно из предписаний – «ОО-предписание 3» – звучит следующим образом:

D должен быть вычислительно полным. Это значит, что в D может поддерживаться механизм вызовов из так называемых основных (host) программ, написанных на языках, отличных от D (но эта поддержка не является обязательной). Аналогично, в D может поддерживаться использование других языков для реализации операций, определяемых пользователями (но эта поддержка не является обязательной).

Однако в [1] утверждается, что из этого предписания следует серьезная ущербность Манифеста. В этом источнике говорится следующее^♦:

Придание вычислительной полноты языку Tutorial D является ошибочным решением, поскольку это приводит к созданию языка, логические выражения которого могут быть неразрешимыми, – хотя для любого логического выражения должен существовать алгоритм, позволяющий его вычислить.

Замечание: В этой цитате упоминается Tutorial D, а не D как таковой, и поэтому я должен пояснить, как соотносятся Tutorial D и D. Начнем с того, что имя D является родовым – оно используется в [9] для обозначения любого языка, соответствующего принципам, заложенным в Третьем Манифесте. Таким образом, может иметься любое число различных языков, квалифицируемых как допустимый D. Подразумевается, что Tutorial D является одним из таких языков; он более или менее формально определяется в [9] и используется во всей этой книге (и в других публикациях) как основа примеров. В настоящей статье для определенности я сосредотачиваюсь (большей частью) на Tutorial D (как и автор [1]), но обсуждение и используемые аргументы применимы к любому допустимому D.

• Разрешимость
• Вычислительная полнота
• Вычислительная полнота влечет неразрешимость
• «Избежал ли ловушки» Кодд?
• Почему мы стремимся в вычислительной полноте?
• Имеет ли все это значение?
• Литература
• Приложение

Разрешимость

Как я отмечал в аннотации, в [1] утверждается, что в Tutorial D допускается отсутствие разрешимости; более точно, утверждается, что в Tutorial D некоторые логические выражения являются неразрешимыми. Что это значит?

Во-первых, каждое выражение можно считать правилом вычисления значения; поэтому, в частности, логическое выражение можно считать правилом вычисления истинностного значения. Итак, логическое выражение – это выражение, сформулированное на некотором языке L, про которое подразумевается, что оно обозначает TRUE или FALSE.^♦♦ Пусть exp является таким выражением; тогда exp называется неразрешимым, если это выражение правильно построено – т.е. сконструировано в полном соответствии с синтаксическими правилами языка L, – но при этом не существует алгоритм, который за конечное время может определить, является ли результатом вычисления exp TRUE. В расширительном смысле, язык L называется неразрешимым в том и только в том случае, когда существует, по крайней мере, одно неразрешимое выражение, представляемое средствами L. Замечу, между прочим, что исчисление высказываний является разрешимым, а исчисление предикатов – нет.

Если язык L является разрешимым, то по определению существует универсальный алгоритм («разрешающая процедура») для определения за конечное время того, является ли TRUE результатом вычисления произвольного выражения, представленного на языке L. Наоборот, если L является неразрешимым, то такой алгоритм не существует. Более того, если L является неразрешимым, отсутствует даже алгоритм для определения за конечное время того, является ли выражение L разрешимым (если бы такой алгоритм существовал, система могла бы (по крайней мере, частично) избежать проблемы, даже и не пытаясь вычислять неразрешимые выражения).

Из сказанного выше следует, что если, в частности, Tutorial D является неразрешимым, то будут иметься некоторые выражения, представленные с использованием этого языка, и, следовательно, некоторые запросы, представленные на Tutorial D (а именно, запросы, включающие такие выражения), с которыми система не сможет справляться удовлетворительным образом. В связи с этим тот факт, что Tutorial D является неразрешимым, выглядит как серьезный дефект.

Вычислительная полнота

В [1] утверждается, что именно вычислительная полнота Tutorial D делает этот язык неразрешимым:

Если некоторый язык включает логику предикатов и является вычислительно полным, то логическим следствием является неразрешимость некоторых выражений этого языка [курсив добавлен].

Так что же означает вычислительная полнота языка?

Как это не странно, я не смог найти определение термина вычислительная полнота ни в одном из большого числа просмотренных мной литературных источников из компьютерной области. Но во многих из них имеется определение вычислимой функции, и я думаю, что достаточно разумно считать язык вычислительно полным в том и только в том случае, если в нем поддерживается вычисление всех вычислимых функций. Так или иначе, я буду использовать это в качестве рабочего определения. Так что же такое вычислимая функция? Вот пара определений из литературных источников:

• Вычислимой функцией называется функция, которая может быть вычислена машиной Тьюринга за конечное число шагов [11].
• Вычислимая функция – это функция, которую можно закодировать с использованием циклов WHILE [12].

Вычислительная полнота влечет неразрешимость

Как я уже говорил, в [1] утверждается, что именно вычислительная полнота Tutorial D делает его неразрешимым. Вот расширенный вариант выдержки, которая приводилась в начале предыдущего раздела:

Проблема попросту состоит в следующем: Если некоторый язык включает логику предикатов и является вычислительно полным, то логическим следствием является то, что в набор синтаксически правильных выражений этого языка будут входить самоссылающиеся выражения, и некоторые из них будут неразрешимыми. Это именно то, что показал Гедель в процессе построения своей первой теоремы о неполноте… Значит, если Tutorial D является вычислительно полным, то набор синтаксически правильных выражений Tutorial D включает самоссылающиеся неразрешимые выражения. Я просто применяю теорему Геделя к Tutorial D.

Автор [1] аппелирует и ко второй теореме Геделя. Вот расширенный вариант выдержки, которая приводилась в аннотации к данной статье:

Придание вычислительной полноты языку Tutorial D является ошибочным решением, поскольку это приводит к созданию языка, логические выражения которого могут быть неразрешимыми, – хотя для любого логического выражения должен существовать алгоритм, позволяющий его вычислить (см. вторую теорему Геделя о неполноте). Имеется ли в Tutorial D пример, более убедительный, чем доказанная теорема? Кодд предусмотрительно избежал этой ловушки, а Третий Манифест – нет!

Я вернусь к вопросу о том, «избежал» ли Кодд «этой ловушки» в следующем разделе. Однако сначала позвольте мне сформулировать две теоремы Геделя. Замечание: В действительности эти теоремы могут формулироваться во многих разных видах; приводимые здесь варианты являются несколько упрощенными – на самом деле, чрезмерно упрощенными, – но в данной ситуации этого достаточно. Заметим также, что в целях данного обсуждения я считаю термины выражение и утверждение взаимозаменяемыми, хотя они обычно не считаются таковыми в контексте традиционных языков программирования.

• Первая теорема Геделя о неполноте: Пусть S – это непротиворечивая формальная система, являющаяся не менее мощной, чем элементарная арифметика; тогда система S является неполной в том смысле, что в S существуют утверждения, которые являются истинными, но это невозможно доказать, оставаясь внутри S.
• Вторая теорема Геделя о неполноте: Пусть – это непротиворечивая формальная система, являющаяся не менее мощной, чем элементарная арифметика; тогда непротиворечивость системы S невозможно доказать, оставаясь внутри S.

Признаюсь, что я не вижу непосредственной связи второй теоремы с аргументами, приводимыми в [1], но очевидно, что первая теорема поддерживает эти аргументы. Более того, поскольку доказательство Геделя своей первой теоремы (a) включает явное построение самоссылающегося утверждения – в сущности, арифметического аналога утверждения «Данное утверждение невозможно доказать в S», а затем доказывает, что это утверждение невозможно доказать в S (и, следовательно, данное утверждение является истинным!), из этого следует, что множество неразрешимых выражений в S включает некоторые самоссылающиеся выражения. И поэтому, если язык Tutorial D вычислительно полон, то он является неразрешимым в том смысле, что в число его выражений входят самоссылающиеся и неразрешимые выражения.

«Избежал ли ловушки» Кодд?

К настоящему моменту мы видим, что в [1] , видимо, корректно утверждается, что Tutorial D, будучи вычислительно полным, является неразрешимым. Более того, в этом источнике также утверждается (по крайней мере, неявно), что реляционная алгебра и реляционное исчисление Кодда являются разрешимыми; в действительности, они должны быть таковыми, поскольку исчисление Кодда, по существу, является прикладной формой пропозиционального исчисления, которое разрешимо, а алгебра Кодда логически эквивалентна его исчислению.

Два отступления от темы: Во-первых, реляционное исчисление обычно считают прикладной формой исчисления предикатов, а не исчисления высказываний; однако тот факт, что мы имеем дело с конечными системами, означает, что на самом деле оно является исчислением высказываний, по крайней мере, с логической точки зрения. Во-вторых, исходное исчисление Кодда в действительности было менее выразительным, чем его алгебра (т.е. имелись некоторые алгебраические выражения, для которых отсутствовали эквиваленты в исчислении), но этот недостаток впоследствии был устранен. Большие подробности в этой статье нам не требуются.

Как мы видим, в [1] также утверждается, что Кодд «избегает ловушки» требования вычислительной полноты и за счет этого не сталкивается с проблемой неразрешимости. В [1] ничего не говорится явно о том, как можно избежать этой ловушки, но приводятся намеки на то, что для этого нужно провести четкую границу между частями языка, которые имеют отношение к работе с базой данных и вычислениями:

Мое пожелание состоит в том, чтобы явно разделить в Tutorial D теоретико-множественную семантику и семантику вычислительного языка …^♦♦♦ Следует переформулировать ОО-предписание 3, чтобы сказать, что подъязык приложений языка D должен быть вычислительно полным и полностью процедурным, а подъязык баз данных языка D должен быть не вычислительно полным, должен быть полностью непроцедурным и должен быть разрешимым (хотя мне не очень понятно, как эти подъязыки могут взаимодействовать) … [Еще одна попытка, позже:] Разделите D на RD (реляционную, непроцедурную часть) и CD (вычислительную, процедурную часть). Тогда ОО-предписание 3 следует переформулировать так, чтобы сказать, что RD должен быть не вычислительно полным, и в нем не должна обеспечиваться возможность вызова какой-либо операции, которую невозможно реализовать средствами RD … Реляционный язык баз данных RD должен быть разрешимым. Следовательно, он не должен быть вычислительно полным, и в нем не должна поддерживаться возможность вызова какой-либо процедуры, которую в принципе невозможно реализовать средствами RD.

Но следуют ли этим ограничениями предложения языка самого Кодда? Нет! Рассмотрим следующие выдержки из собственных статей Кодда:

Из самой первой (1969 г.) статьи про реляционную модель [2]: Пусть подъязык выборки называется R и основной язык – H … R обеспечивает возможность спецификации выборки любого поднабора данных из банка данных … Класс ограничительных выражений, которое могут использоваться в спецификации набора, находится в точно определенном … соответствии с классом правильно построенных формул исчисления предикатов … Любая требуемая арифметическая функция может определяться с использованием языка H и вызываться из конструкций языка R [курсив добавлен].

Из пересмотренного варианта статьи, опубликованного в 1970 г. в Communications of the ACM [3]: Пусть подъязык выборки называется R и основной язык – H … R обеспечивает возможность спецификации выборки любого поднабора данных из банка данных … Класс ограничительных выражений, которое могут использоваться в спецификации набора, должен обладать описательной мощностью класса правильно построенных формул прикладного исчисления предикатов … В условных или других частях операторов выборки могут потребоваться арифметические функции. Такие функции могут определяться на языке H и вызываться из конструкций языка R [курсив добавлен].

И в статье, посвященной подъязыку данных ALPHA [4], говорится следующее:

Все вычислительные функции определяются с помощью операторов основного языка; все операции выборки и сохранения – с помощью операторов подъязыка данных. Однако в операторе подъязыка данных может содержаться вызов функции, определенной с помощью операторов основного языка … Расширяемая библиотека функций, которые могут вызываться из запросов, обеспечивает средства расширения возможностей выборки DSL [Data SubLanguage] ALPHA.

В этой статье далее приводится несколько примеров использования таких функций как в разделе «целевого списка», так и в разделе «условия» запросов. Так что я бы сказал, что во всех трех статьях [2-4] Кодд не только «не избегал ловушки» – очевидно, что он даже и задумывался о наличии ловушки, которую нужно стараться избегать.

Замечание: Комментируя ранний вариант настоящей статьи, автор [1] утверждал, что разделение Коддом языков R и H было достаточным для того, чтобы «избежать ловушки». В частности, он утверждал, что (a) одним из эффектов такого разделения являлось то, что к вызову из языка R функции, определенной средствами языка H, можно было относиться с точки зрения языка R как к константе, и (b) что ловушки удалось избежать, потому что в функциях, определенных на языке H, отсутствовал доступ к переменным, определенным на языке R. После размышлений я пришел к выводу, что не понимаю эти утверждения. В частности, в функциях, используемых Коддом в примерах в [4], очень часто производится доступ к переменным, «определенным на языке R», – в число этих функций входят аналоги всем знакомых агрегатных операций COUNT, SUM, AVG, MAX и MIN, которые, конечно, явно определяются для работы с отношениями. (Если речь идет о том, что эти функции могут только читать свои операнды и не могут изменять их, то это верно и для Tutorial D, так что, по-видимому, имеется в виду не это.)

Отклоняясь от темы, я хотел бы добавить, что по причинам, которые мне не хотелось бы здесь объяснять, я никогда не относился к числу поклонников идеи подъязыка данных (частично по этой причине появилось ОО-предписание 3 Манифеста). Как я писал в [7],

Я никогда не был убежден в том, что выделение доступа к данным в отдельный «подъязык» является хорошей идеей, [хотя] она присутствует в нашей практике в течение довольно долгого времени в форме встраиваемого SQL. Кстати, в связи с этим интересно заметить, что после добавления в стандарт SQL в 1996 г. механизма PSM («Persistent Stored Modules») сам SQL стал теперь вычислительно полным языком – что означает отсутствие дальнейшей потребности в основном языке (при использовании SQL).

Почему мы стремимся к вычислительной полноте

Вот снова ОО-предписание 3 в своей исходной формулировке:

D должен быть вычислительно полным. Это значит, что в D может поддерживаться механизм вызовов из так называемых основных (host) программ, написанных на языках, отличных от D (но эта поддержка не является обязательной). Аналогично, в D может поддерживаться использование других языков для реализации операций, определяемых пользователями (но эта поддержка не является обязательной).

В [1] это предписание комментируется следующим образом:

Я не понимаю текст, начинающийся с «Это значит», – он не является определением того, что означает вычислительная полнота языка. Наличие программ, написанных на других языках, которые можно вызывать из конструкций данного языка или из которых можно вызвать программы, написанные на данном языке, не делает этот язык вычислительно полным.

Конечно, я согласен с тем, что текст, начинающийся с «Это значит», не является определением вычислительной полноты; он для этого и не предназначался, и может быть желательна некоторая переформулировка. Скорее, этот текст предназначался для разъяснения некоторых последствий вычислительной полноты языка D – другими словами, он предназначался для разъяснения того, почему мы считаем вычислительную полноту хорошей идеей. В своей части [1] Хью писал следующее:

Я надеюсь, что обоснование нашего включения требования вычислительной полноты является очевидным. Частично оно состоит в том, что тогда приложения могут писаться на языке D, что позволяет избежать проблем, связанных с потребностью писать их на другом языке, а частично в том, что обеспечивается возможность использования языка D для кодирования реализаций операций, определяемых пользователями.

В ходе дальнейшей переписки в ответ на уже обсуждавшиеся мной критические замечания Хью сказал следующее:

Возможно, нам следовало сказать что-нибудь, подобное следующему: Язык D должен включать полный набор возможностей для реализации приложений баз данных и операций, определяемых пользователями. Для достижения целей было бы достаточно наличия вычислительно полного языка, но от D не требуется вычислительная полнота; не требуется и наличие возможности написания на языке D приложений и операций, определяемых пользователями.

Но если мы соглашается отступить от вычислительной полноты, то как далеко мы можешь отойти? – т.е. где мы проведем границу? Насколько много вычислительных действий можем мы поддерживать безопасно? Если верно то, что вычислительная полнота означает всего лишь возможность вычислять все вычислимые функции, а вычислимая функция означает всего лишь функцию, которую можно закодировать с использованием циклов WHILE, то следует ли нам запретить циклы WHILE? Если да, то с чем мы останемся? Замечание: Конечно, эти вопросы являются теоретическими. Моя позиция достаточно очевидна: я не думаю, что мы можем отойти от вычислительной полноты. Более того, Хью согласен со мной; его намек на то, что от D может не требоваться вычислительная полнота, не был серьезным.

Но имеется еще одна проблема, которую я должен затронуть при обсуждении нашего стремления к вычислительной полноте языка D. Среди прочего, вычислительная полнота означает возможность включения в реляционные выражения вызовов определяемых пользователями операций только чтения, возвращающих значения-отношения, – операций, реализация которых может быть закодирована на самом языке D, возможно, с использованием циклов и других процедурных конструкций, – и некоторые критики могут счесть эту возможность противоречащей исходной цели Кодда относительно того, что все запросы и пр. должны представляться декларативно. Однако мы утверждаем, что вызовы операций только чтения являются в равной степени декларативными, независимо от того, где, как, кем и на каком языке эти операции реализованы (и независимо от того, являются ли они возвращающими значения-отношения). Для иллюстрации рассмотрим следующий пример:

OPERATOR TABLE_NUM ( K INTEGER )

RETURNS RELATION { N INTEGER } ;

... implementation code ...

END OPERATOR ;

При вызове эта операция возвращает отношение, представляющее предикат «N является целым числом в диапазоне от 1 до K» (полезность такой операции демонстрируется в [6]). Тогда, конечно, вызов, например, TABLE_NUM (3149) является в равной степени «декларативным» вне зависимости от того, (a) написан ли код реализации на языке D тем же пользователем, который производит вызов, или (b) он написан некоторым другим пользователем на некотором другом языке, или (c) он предоставляется в составе СУБД.

Имеет ли все это значение?

Еще одна выдержка из [1]:

Если язык Tutorial D является неразрешимым, то рано или поздно пользователь или система попытаются вычислить неразрешимый оператор, и это приведет к отказу реализации. Вы может возразить, указав, что этого не происходит в вычислительно полных языках, таких как Ada, Pascal, Fortran или Java. Но вы будет не правы. В действительности, нетрудно закодировать бесконечный процедурный цикл, который не распознает никакой компилятор.

Более точно, как мы видим, в [1] утверждается, что с реляционным языком должна быть ассоциирована процедура разрешения («должна существовать процедура разрешения для вычисления любого логического выражения»). Но корректно ли это утверждение? В исчислении предикатов отсутствует процедура разрешения, но, по крайней мере, можно придумать некоторую процедуру, являющуюся полной и совершенной (sound and complete). В моем пересказе в [10] говорится следующее:

Для заданной правильно построенной формулы исчисления предикатов такая процедура будет корректно возвращать TRUE в том и только в том случае, когда формула вычисляется в TRUE; однако, если формула вычисляется в FALSE, то процедура либо выдаст FALSE, либо будет выполняться бесконечно. (Другими словами, если формула истинна, то она является доказательно истинной; однако если она ложна, то не является доказательно ложной.)

Поэтому на практике мы можем включить такую процедуру в реализацию системы. Более того, мы можем включить в процедуру механизм тайм-аутов, так что, если вычисление некоторого заданного выражения не завершается в течение некоторого предопределенного периода времени, систем прекращает вычисление и возвращает пользователю сообщение типа Слишком сложное выражение. (Конечно, она не должна возвращать TRUE или FALSE! Иначе мы вернулись бы к тому, что Кодд – совсем в другом контексте – называл «строго некорректным» результатом [5].)

Следовательно, резюмирую:

• Очевидно, нам хотелось бы иметь систему, в которой все возможные выражения могли бы вычисляться за конечное время.
• Этой цели невозможно достичь, если мы настаиваем на вычислительной полноте.
• Однако мы хотя бы знаем об этом, и можем к этому подготовиться.
• В частности, мы можем встроить в систему код, который позволит выдавать в ответ на некоторые запросы сообщения типа «Я не могут ответить на этот запрос, потому что он слишком сложен».

В заключение я хотел бы отметить следующее:

• При общении на естественном языке часто бывает невозможно точно ответить на некоторые вопросы. С такими ситуациями мы сталкиваемся постоянно. Поэтому система, которая иногда выдает сообщение Слишком сложное выражение, не является полностью бесполезной.
• В любом случает, даже при отсутствии вычислительной полноты, вполне вероятно существование запросов, на которые в принципе можно ответить за конечное время, но это время является настолько большим, что ответа дождаться практически невозможно. Другими словами, проблема неразрешимости существует и при отсутствии вычислительной полноты. И поэтому наше прагматическое решение этой проблемы (реализация механизма тайм-аутов), по-видимому, требуется в любом случае.
• Наконец, если вычислительная полнота ведет к отсутствию разрешимости, то, следовательно, неразрешимы традиционные языки программирования. Но мы благополучно уживаемся с этой проблемой на протяжении многих лет, и я не думаю, что она вызывает непреодолимые трудности. Чем в этом отношении отличаются языки баз данных?

Литература

1. Anon.: Private correspondence with Hugh Darwen (December 2005 - January 2006).
2. E. F. Codd: "Derivability, Redundancy, and Consistency of Relations Stored in Large Data Banks," IBM Research Report RJ599 (August 19th, 1969).
3. E. F. Codd: "A Relational Model of Data for Large Shared Data Banks," CACM 13, No. 6 (June 1970). Republished in Milestones of Research—Selected Papers 1958-1982 (CACM 25th Anniversary Issue), CACM 26, No. 1 (January 1983). Есть русский перевод М.Р. Когаловского: Е.Ф. Кодд. Реляционная модель данных для больших совместно используемых банков данных, СУБД, N 1, 1995, http://old.osp.ru/dbms/1995/01/01.htm
4. E. F. Codd: "A Data Base Sublanguage Founded on the Relational Calculus," Proc. 1971 ACM SIGFIDET Workshop on Data Description, Access and Control, San Diego, Calif. (November 1971). (По поводу языка ALPHA можно также прочитать пересказ С.Д. Кузнецова двух статей Дейта: http://www.citforum.ru/database/digest/data_sub_alpha.shtml и http://www.citforum.ru/database/digest/ie990903.shtml.)
5. E. F. Codd and C. J. Date: "Much Ado About Nothing," in C. J. Date, Relational Database Writings 1991-1994 (Addison-Wesley, 1995).
6. Hugh Darwen (writing as Andrew Warden): "A Constant Friend," in C. J. Date, Relational Database Writings 1985-1989 (Addison-Wesley, 1990).
7. C. J. Date: The Database Relational Model: A Retrospective Review and Analysis. Reading, Mass.: Addison-Wesley (2000).
8. C. J. Date: "To Be Is to Be a Value of a Variable," www.thethirdmanifesto.com (July 2006). Имеется перевод на русский язык С.Д. Кузнецова: К. Дж. Дейт. Быть или не быть значению переменной
9. C. J. Date and Hugh Darwen: Databases, Types, and the Relational Model: The Third Manifesto (3rd edition). Reading, Mass.: Addison-Wesley (2006). (Второе издание книги опубликовано в переводе на русский язык: К. Дж. Дейт, Хью Дарвен. Основы будущих систем баз данных: третий манифест. Перевод под ред. С.Д.Кузнецова, Янус-К, 2004.)
10. Zohar Manna and Richard Waldinger: The Logical Basis for Computer Programming, Volume 2: Deductive Systems. Reading, Mass.: Addison-Wesley (1990).
11. Sybil P. Parker (ed.): The McGraw-Hill Dictionary of Mathematics. New York, N.Y.: McGraw-Hill (1994).
12. Eric W. Weisstein: CRC Concise Encyclopedia of Mathematics. Boca Raton, Fla.: Chapman & Hall / CRC (1999).

Приложение

В основной части этой статьи я цитировал [12] в связи с определением вычислимой функции как функции, которую можно закодировать с использованием циклов WHILE. Вслед за этим определением в [12] говорится следующее:

Циклы FOR (для которых имеется фиксированное ограничение на число итераций) являются частным случаем циклов WHILE, так что вычислимые функции можно также закодировать с использованием некоторой комбинации циклов FOR и WHILE. Простейшим примером функции, являющейся вычислимой, но не примитивно-рекурсивной, является функция Акермана (Ackermann).

Позвольте мне кратко развить эти замечания. Во-первых, функция называется рекурсивной в том и только в том случае, когда она «может быть получена [sic] путем использования конечного числа операций, вычислений или алгоритмов» [11]. (Заметим, что здесь термин рекурсивный используется не в обычном смысле языков программирования; в действительности, как кажется, он используется ровно в том же смысле, что и термин вычислимый, как он определялся ранее.) Во-вторых, функция называется примитивно-рекурсивной в том и только в том случае, когда ее можно закодировать с использованием только циклов FOR [12].

Далее, я не знаю, в каком смысле функция Акермана называется выше «простейшим примером» функции, являющейся рекурсивной (или, во всяком случае, вычислимой), но не примитивно-вычислимой. Однако для интереса я привожу здесь определение этой функции (замечу, что это определение является рекурсивным в обычном смысле языков программирования). Вот оно: пусть x и y обозначают неотрицательные целые числа. Тогда функция Акермана A(x,y) может быть определена следующим образом:

OPERATOR A ( X NONNEG_INT, Y NONNEG_INT ) RETURNS NONNEG_INT ;

RETURN ( CASE

WHEN X = 0 THEN Y + 1

WHEN Y = 0 THEN A ( X - 1, 1 )

ELSE A ( X - 1, A ( X, Y - 1 ) )

END CASE ) ;

END OPERATOR ;

Предостережение: Пожалуйста, не пытайтесь выполнить этот алгоритм на реальной машине даже для не очень больших значений x и y.