Странная формула. Часть 5. Вездесущая единица

 АЛЕКСЕЙ ВТОРНИКОВ, ЗАО КБ «Ростовский Универсальный», ведущий программист, pdp8dec@gmail.com

Странная формула
Часть 5. Вездесущая единица

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

Единица – вздор, единица – ноль...

В.Маяковский

Необходимые пояснения

Чтобы не говорить всякий раз «число, на единицу большее» или «добавить единицу к числу», удобно ввести для этого краткое обозначение. На самом деле существует много способов обозначить операцию увеличения числа на единицу (например, хорошо известная операция инкремента i++ в C-подобных языках программирования), но мы рассмотрим те, что распространены в математике.

Напомним, что натуральный ряд N (а мы далее будем говорить только о числах из натурального ряда) – это последовательность целых неотрицательных чисел: 0, 1, 2, ..., n-1, n, n+1, ... У натурального ряда нет конца (это часто, хотя и некорректно, обозначается символом «∞»), но есть начало, а именно число 0. Таким образом, используя операцию прибавления единицы, мы, «стартовав» с 0, можем рано или поздно «добраться» до любого числа, каким бы большим оно ни было. Вот несколько примеров:

0 + 1 = 1

0 + 1 + 1 = 2

0 + 1 + 1 + ... + 1 = 10000

Эти очевидные арифметические равенства можно записать либо в форме:

0 + 1 = 0' = 1

0 + 1 + 1 = 0'' = 2

0 + 1 + 1 + ... + 1 = 0''... ' = 10000

это т.н. штрих-нотация, либо в форме:

S0 = 1

SS0 = 2

SS...S0 = 10000

а это, как нетрудно догадаться, S-нотация. Таким образом, количество штрихов («'») или символов («S») выражает количество операций прибавления единицы к нулю. Мы будем использовать второй способ (т.е. посредством символа «S»), так как он, на мой взгляд, удобнее для восприятия.

Замечание. Порой встречается еще один способ, при котором натуральное число n записывается последовательностью n+1 единиц; тогда 0 записывается просто как 1, а 5 как 111111, т.е. шестью единицами. Будьте внимательны, не спутайте эту нотацию с двоичной записью!

А теперь – приступим.

Хочется странного

Допустим, требуется описать процесс вычисления функции факториала, т.е. функцию:

n! = 1 * 2 * 3 * ... * n-1 * n

что понимается под «описанием процесса вычисления», вы вскоре увидите. Запрограммировать эту функцию просто (далее все примеры приведены на языке программирования Java).

Сначала – школярский и самый очевидный вариант:

int factorial (int n) {

int f = 1;

for (int i = 1; i <= n; i++) {

f = f * i;

}

return f;

}

Это, конечно, мило, но не более; другой вариант куда интереснее:

int factorial (int n) {

if (n <= 1) return 1;

return (n * factorial (n – 1));

}

В глаза бросается рекурсивный вызов функции внутри нее самой же, но уже с другим значением аргумента. О рекурсии мы поговорим позже, а пока копнем поглубже и спросим: какие операции лежат в основе вычисления факториала?

Очевидно, что вычисление факториала сводится к умножениям чисел от 1 до n. Итак, от факториала мы приходим к операции умножения: факториал → умножение, стрелка «→» означает операцию перехода; математики иногда используют термин «редукция», т.е. сведение одной операции к другой, обычно более простой.

Но что есть умножение? Или конкретнее: что значит умножить, скажем, 3 на 4? Элементарный ответ такой:

3 * 4 = 3 + 3 + 3 + 3

т.е. умножение сводится к сложению. Так, становится забавнее, и теперь цепочка вычисления факториала сводится к такому виду: факториал → умножение → сложение.

Совершенно логично спросить: а к чему сводится сложение, или что, собственно, означает, скажем, 2 + 3? Ответ – далее, а пока попробуйте ответить сами. Ответ таков:

2 + 3 = 2 + 1 + 1 + 1

т.е. операция сложения свелась к уже знакомой нам операции прибавления единицы. Это стоит записать: факториал → умножение → сложение → прибавление 1.

Мы, таким образом, опустились от высокоуровневой функции вычисления факториала к низкоуровневой функции прибавления 1, т.е. к операции, которую ранее мы условились записывать в виде SS...S0, где многоточия заменяют нужное количество операций прибавления единицы. Небольшой пример:

4! = SSSSSSSSSSSSSSSSSSSSSSSS0

Проверьте!. Дальше, похоже, упрощать некуда.

Какой вывод можно сделать из этого почти очевидного анализа? А вот какой: все в конечном счете свелось к прибавлению нужного количества единиц. Теперь автоматически возникает вопрос: а какие еще функции, помимо факториала, могут быть подобным образом сведены к прибавлению единицы? Раздел математики, в котором изучаются такие функции (конечно, функции в самом общем виде), называется теорией рекурсивных функций (часто используется другой термин – теория вычислимых функций).

Немного истории

Теория рекурсивных (вычислимых) функций (далее коротко «ТРФ») как самостоятельная дисциплина оформилась относительно недавно, в 1923 году, после публикации норвежским математиком Туральфом Скулемом (1887-1963) статьи с длинным названием «Основания элементарной арифметики, установленные посредством рекурсивного способа мышления...».

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

Скулем задался вопросом: можно ли дать такое описание арифметики, которое, по возможности, было бы свободно от использования принципов, положенных в основу теории бесконечных множеств (и избежать тем самым возможных парадоксов этой теории)?

Оказалось, что ответ на этот вопрос положительный. Через восемь лет идеи, высказанные Скулемом, что называется, «выстрелили»: австрийский математик Курт Гедель подхватил идеи Скулема, существенно их развил и использовал при доказательстве двух самых, вероятно, знаменитых и значимых теорем XX века – теорем о неполноте арифметики.

После этого развитие ТРФ приобрело стремительный характер. Один только краткий перечень имен тех математиков, кто принял участие в разработке ТРФ, внушает уважение: А. Черч, С. Клини, А. Тьюринг, Э. Пост, Р. Петер, М. Дэвис, Дж. Робинсон, наши соотечественники А.А. Марков, П.С. Новиков, А.И. Мальцев, Ю.В. Матиясевич. Что особенно должно заинтриговать читателей журнала, так это то, что ТРФ имеет непосредственный «выход» на проблематику программирования.

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

Опять о сложении

Итак, анализируя способ вычисления факториала, мы увидели, что все сводится к элементарной операции прибавления единицы. Значит, надо аккуратно проанализировать сложение.

Пусть даны два произвольных (натуральных) числа, которые мы обозначим через a и n. Нужно математически выразить операцию получения их суммы (обозначим для краткости эту операцию через «sum»).

Здесь нужно рассмотреть два случая:

• n = 0
• n ≠ 0

В первом случае sum (0, a) = a (на языке школьной алгебры это означает, что 0 не изменяет суммы; на языке современной алгебры говорят, что 0 – нейтральный элемент). Этот случай, конечно, неинтересен. А вот второй случай – другое дело. Внимание – сейчас вы увидите небольшой трюк, из числа тех, которые так любят математики. Сумму числа a и числа n при n ≠ 0 можно выразить так:

sum (n, a) = sum (n-1, a) + 1

Проверим:

sum (5, 2) = sum (4, 2) + 1

что, конечно, правильно.

Посмотрите внимательнее на правую часть: вот она – единица! Продолжим (начиная с этого места настоятельно рекомендуем выписывать все шаги):

sum (n-1, a) = sum (n-2, a) + 1

sum (n-2, a) = sum (n-3, a) + 1

...

sum (n-n, a) = sum (0, a) = a

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

Упражнение 1. Запрограммируйте рекурсивную функцию сложения двух натуральных чисел на любом известном вам языке программирования (ответ см. в конце статьи). Конечно, никто не станет программировать такую функцию при наличии встроенной операции сложения. Наша цель – продемонстрировать рекурсивный характер функции суммирования.

Многие, впервые видя такой способ обращения со знакомой, казалось бы, функцией, несколько теряются. Лучший способ разобраться: вычислить функцию на конкретных числовых данных – попробуйте.

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

Упражнение 2. Выведите рекурсивную функцию умножения двух чисел (ответ см. в конце статьи). В качестве простого дополнения – запрограммируйте ее. Для особенно пытливых – попытайтесь выразить умножение в рекурсивном вызове функции только путем прибавления единицы (т.е. полностью исключите операцию умножения).

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

Замечание. В обоснование этого приведем элементарный пример. Все, вероятно, знают, что такое арифметическая прогрессия. Примером такой прогрессии является последовательность: 1, 2, 3, ..., n, с разностью равной 1.

Необходимо найти сумму всех элементов прогрессии. Можно, конечно, просуммировать все члены прогрессии один за другим, но куда проще воспользоваться функцией n * (n+1)/2. Задача усложнится, если разность прогрессии будет уже не 1, а другое число (возможно, отрицательное). Гораздо удобнее вывести общую функцию, чем всякий раз уныло выполнять арифметические операции, пусть даже и простые.

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

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

Рассмотренная нами функция сложения довольно проста, и правильность наших рассуждений «на пальцах» не вызывает сомнений. Однако большинство полезных функций гораздо сложнее (попробуйте, например, вывести функцию нахождения разности двух натуральных чисел и не забудьте, что отрицательные числа во множестве N не допускаются!). Поскольку мы говорим о математических объектах, то разумно унифицировать обозначения, терминологию и способы рассуждений, применяемые в ТРФ. Это тем более важно, что в литературе по ТРФ принят формальный способ изложения, и без определенного навыка читать эти книги вам будет сложно. Так что ничего не поделаешь – придется привыкать.

Формализация

Помните, в разделе «Немного истории» мы упомянули о небольшом и элементарном наборе базовых функций, посредством которых могут быть построены остальные функции?

Этот набор, действительно, элементарен и включает в себя следующие функции:

Нуль-функция. Эта функция, будучи применена к любому аргументу (и даже к списку аргументов), имеет своим значением 0. Обозначим эту функцию через Z (x). Согласно определению: Z (x) = 0; Z (x₁, x₂, ..., x_n) = 0.

Функция «следующее число». Это наша старая знакомая – функция прибавления единицы S...0.

Функция проектирования. Эта функция позволяет выделить из набора аргументов определенное значение. Несколько примеров покажут эту функцию «в работе»:

I₀ (n₀, n₁, n₂, n₃, n₄) = n₀

I₁ (n₀, n₁, n₂, n₃, n₄) = n₁

I₃ (n₀, n₁, n₂, n₃, n₄) = n₃

Иначе говоря, функция проектирования вычленяет из переданных ей аргументов один – с заданным номером (нижний индекс возле имени функции). Вот, собственно, и все базовые функции! Но перед тем как демонстрировать их в работе, нужно сказать несколько слов о двух операциях, с помощью которых базовые функции могут комбинироваться (эти операции по назначению аналогичны правилам вывода в математической логике). Операции эти таковы:

• Операция композиции (подстановки)
• Операция примитивной рекурсии

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

Композиция (подстановка)

Операция композиции (подстановки) на самом деле должна быть вам хорошо знакома. Фактически это способ комбинирования простых функций для образования сложных функций (с произвольным количеством вложенности). Небольшой пример покажет, что мы имеем в виду:

ln (cos (x) – sin (x))

Здесь представлена функция натурального логарифма от функции, представляющей собой разность тригонометрических функций косинуса и синуса от аргумента (кстати, вспомните школу: для каких значений аргумента эта функция определена, т.е. имеет значение?). Конечно, вряд ли такая функция встретится в ином качестве, помимо упражнения по алгебре, но наша цель – показать сущность композиции функций.

Итак, композиция – это способ представления функции путем комбинирования нескольких составляющих.

Формально это выглядит так. Пусть имеется n функций, каждая из которых принимает m аргументов:

g₁ (x₁,...,x_m)

g₂ (x₁,...,x_m)

...

g_n (x₁,...,x_m)

Из этих функций можно образовать новую n-местную функцию вида

h(x₁,...,x_n) = f(g₁(x₁,...,x_m),g₂(x₁,...,x_m),..., g_n(x₁,...,x_m))

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

h = C_n [f, g₁,..., g_n]

и назовем это схемой композиции (или схемой подстановки).

Замечание. В литературе по ТРФ распространено еще одно обозначение:

h = S [f, g₁,..., g_n]

в котором символ «S» – это первая буква слова «substitution» (т.е. подстановка), но из-за сходства этого обозначения с символом базовой функции следования мы им пользоваться не будем.

Простой пример и несколько упражнений покажут эту весьма непривычную конструкцию в деле. Давайте проанализируем, что скрывается за следующей функцией:

C_n [S, S] 

Здесь первая (левая) операция S представляет собой функцию f из схемы подстановки. Вторая (правая) операция S – список подставляемых функций, которые мы обозначали как g₁, ..., g_n. В нашем примере этот список, очевидно, состоит только из одной функции (что вполне допустимо). Вначале нужно применить функции g₁, ..., g_n, а затем к полученному результату – функцию f (это непосредственно следует из схемы подстановки). В более привычной записи имеем:

h (x) = f (g (x))

Внутренняя функция (g) увеличивает значение аргумента x на 1 и передает новое значение внешней функции (f), которая, в свою очередь, увеличивает полученный от функции g аргумент еще на 1. Что на выходе? Да очень просто: x + 2. Таким образом, если до выполнения подстановки аргумент был равен 5, то после выполнения – 7. Формально:

C_n [S, S] (x) = x + 2

Обратите внимание, что мы использовали исключительно базовую функцию «следующее число» (а именно S (x). Понятно, это непривычный способ сложения, и, чтобы к нему привыкнуть, потребуются некоторое время и – главное – практика.

Упражнение 3. Пусть теперь нужно выразить x + 3. Как бы вы поступили? Не торопитесь заглядывать в ответ – все, что нужно, вы уже знаете.

Упражнение 4. Дана функция с пятью аргументами (от n₀ до n₄). Получить значение второго по порядку аргумента (n₁), присвоить ему значение, равное 1, и вернуть это значение как результат функции.

Итак, мы убедились, что операция композиции в совокупности с базовыми операциями – достаточно мощный и элегантный механизм. Главное, что нужно понять, – это то, что мы можем использовать не только одни лишь базовые функции, но и комбинации базовых функций с функциями, полученными применением базовых (вспомните о матрешках). Конечно, такой modus operandi на первых порах кажется необычным, но, если вдуматься, он вполне прозрачен и логичен. В следующей статье мы, как и обещали, рассмотрим вторую базовую операцию – операцию примитивной рекурсии. А пока предлагаем вам самостоятельно потренироваться в составлении функций с помощью операции композиции (подстановки).

Да, и напоследок: вы заметили определенное сходство базовых функций с командами абака, о котором мы говорили в предыдущей статье цикла? Признаемся – это не случайно.

Ответы к упражнениям

Упражнение 1. Реализация рекурсивной функции суммы двух натуральных чисел: 

public class Sum {

static int sum (int x, int n) {

int s = x;

if (n == 0) return s;

return (sum (n - 1, x) + 1);

}

public static void main (String [] args) {

System.out.println (sum (4, 7));

}

}

Упражнение 2. Рекурсивная функция умножения двух натуральных чисел: 

prod (0, a) = 0

prod (n, a) = prod (n-1, a) + n

Упражнение 3. Мы уже знаем, как вычислить x + 2. Чем отличается от этого вычисление x + 3? Да всего только еще одной операцией S; неформально

x + 3 = (x + 2) + 1 = S (x + 2)

Осталось только все собрать вместе. Очевидно, что функция h теперь будет композицией C_n [S, S] и S. Окончательно

h = C_n [S, C_n [S, S]]

Вот и все. Не правда ли, просто и изящно?

Упражнение 4. Для решения этого упражнения удобно идти «от обратного». Что нужно получить на выходе? Очевидно – единицу. Что именно должно получить это значение? Второй аргумент. Как выделить этот аргумент? С помощью базовой функции проектирования.

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

I₁ (n₀, n₁, n₂, n₃, n₄) = n₁

будьте внимательны с индексами: второй по порядку аргумент – это элемент списка аргументов с индексом 1.

Остается прибавить к полученному значению 1 (базовая функция S), и задача решена, но тут есть одна тонкость. Допустим, что список аргументов функции выглядит как (6, 41, 2, 0, 7). Второй аргумент, очевидно, равен 41 и после увеличения на единицу результат станет равен 42, а это вовсе не то, что требуется в условии! Что-то мы упускаем, но что? Подумайте немного.

Ответ очевиден: единица получается путем прибавления 1 к 0 (в наших обозначениях S0). Вот если бы второй аргумент был нулем... Но позвольте, а что нам мешает сделать его нулем? Да ничего – достаточно перед применением операции S сделать только что выделенный аргумент равным нулю, а для этого у нас имеется базовая же функция Z.

Осталось всего ничего – объединить все необходимые функции в одно целое:

h = C_n [S, C_n [Z, I₁ (n₀, n₁, n₂, n₃, n₄)]]

Получилась композиция (подстановка) в композиции (в подстановке). Неформально это читается так (движемся справа налево): выделить нужный аргумент функции, обнулить его (здесь мы «находимся» во внутренней композиции), увеличить результат на 1 (а теперь мы «находимся» во внешней композиции) и вернуть полученное значение (это окончательный результат). Изящно, не правда ли?

Если совсем формально, то результат следовало бы записать так:

C_n [S, C_n [Z, I₁ (n₀, n₁, n₂, n₃, n₄)]] (n₀, n₁, n₂, n₃, n₄) = 1

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

Библиография

1) Вторников А. Странная формула. Часть 4. Абак – простейший вычислитель. //«Системный администратор», №5, 2014 г. – С. 76-81.

Библиография по ТРФ весьма обширна. Ниже приводим ряд полезных книг в порядке возрастания сложности изложения:

2) Дж.Булос, Р.Джеффри. Вычислимость и логика. – М.: «Мир», 1993.

Ясный и доступный учебник по математической логике и ТРФ. Много упражнений с подробным разбором решений.

3) Н.Катленд. Вычислимость. Введение в теорию рекурсивных функций. – М.: «Мир», 1983.

Вполне элементарное введение в ТРФ, но не обольщайтесь заранее – чтение книги потребует определенных усилий.

4) Р.Петер. Рекурсивные функции. – М.: «Издательство иностранной литературы», 1954.

Первая в мировой литературе монография по рекурсивным функциям. Уникальная книга с огромным количеством детально разобранных примеров и ясным стилем изложения. Лучшее, пожалуй, введение в ТРФ. Найти в бумажном варианте вряд ли удастся, но в электронном виде – легко.

5) А.И.Мальцев. Алгоритмы и рекурсивные функции. – М.: «Наука», 1986.

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

Этими книгами перечень литературы по ТРФ, конечно, не исчерпывается, но мы привели наиболее доступные и рассчитанные на начинающих изучать предмет.

В этой части мы только слегка коснулись идей и методов ТРФ. Надеемся, что вы заметили красоту и изящество предмета. А пока мы прощаемся (надеемся – ненадолго) и желаем вам успехов в путешествии по стране рекурсивных функций.

Комментарии могут оставлять только зарегистрированные пользователи