Классика баз данных - статьи

       

В основной части этой статьи


В основной части этой статьи я цитировал [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.
В целях придания большей ясности я отредактировал (иногда радикально) большую часть цитат, используемых в этой статье.
Естественно, здесь я ограничиваюсь двузначной логикой.
Относительно «теоретико-множественной семантики и семантики вычислительного языка» см [8].

Содержание раздела