Александр Соловьев - ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ

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

Известный хорошо еще со школы ОПЕРАТОР СУПЕРПОЗИЦИИ позволяет вместо аргумента подставлять функцию… «Игла в яйце, а яйцо в ларце»…

Дольше словами описывать ОПЕРАТОР ПРИМИТИВНОЙ РЕКУРСИИ . Но если поднатужиться, то можно понять. Этот оператор позволяет построить новую функцию из двух функций, одна из которых имеет на один аргумент меньше, а другая на один аргумент больше.

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

(ненулевых) значений выбранного аргумента приравнивается другой функции, зависящей (напрягитесь!) от тех же аргументов, кроме выбранного; от ПРЕДЫДУЩЕГО значения выбранного аргумента и от создаваемой функции от предыдущего значения выбранного аргумента.

Ну как тут не пожалеть о формулах.

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

Функцию умножения икс на ноль можно выразить через нуль-функцию от икс, которая обеспечит нам желанное значение – ноль.

Функцию умножения икс на игрек (отличный от нуля) можно выразить через функцию сложения икса со значением функции умножения икса на предыдущее значение игрека… То есть мы выразили умножение через сложение.

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

Последний оператор – ОПЕРАТОР НАИМЕНЬШЕГО КОРНЯ . Его необходимость просто об'яснить хотя бы тем, что рекурсивные функции, призванные решать любые алгоритмически разрешимые задачи, сами используют лишь целые положительные числа. А это не позволяет решить даже детскую задачку: 5 – 8 =? (Нет для рекурсивных функций отрицательных чисел). На самом-то деле эти детские задачки можно решить по-детски. Договориться, что 1000 это (сдвинутый) ноль, а вычитание – есть сложение с «отрицательным» числом! Тогда

1005 + 992 = 1997 (приведение к шкале: 1997 – 1000 = 997)

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

Именно оператор наименьшего корня и следит, при каком значении выбранного аргумента наблюдаемая им функция впервые опустится до нуля. Это значение выбранного аргумента и будет значением оператора наименьшего корня. Например, для функции икс минус игрек при иксе равном 5, значение оператора наименьшего корня также будет равно 5, поскольку двигаясь в значениях игрека от нуля получим нулевое значение функции именно при игрек равном 5.

Базовые функции и функции, которые могут быть построены из них с помощью операторов суперпозиции, примитивной рекурсии и наименьшего корня, образуют множество ЧАСТИЧНО-РЕКУРСИВНЫХ ФУНКЦИЙ . А множество частично-рекурсивных функций совпадает с множеством всех алгоритмически разрешимых задач (множеством всех вычислимых функций). Кстати, за слово «частичные» надо благодарить оператор наименьшего корня, из-за которого в множество построенных функций входят и не всюду определенные (частичные) функции.

Тьюринг не был автостроителем. Машина Тьюринга не предполагает двигателя внутреннего сгорания, поскольку все там перемещается исключительно силой мысли. Это математическая модель. Она чем-то может и напоминающая автомашину, но не более чем машину напоминает магнитофон, в котором лента (разделенная на ячейки) неподвижна, а считывающе-записывающая головка вдоль нее ездит. Хуже того, ездит головка рывками, от ячейки к ячейке. А в ячейках записаны символы. (Чтобы не было пустых ячеек, в пустые ячейки записывают специальный пустой символ).