Вы всё пляшете вокруг понятий "рекурсивности", которые считаете уже введёнными
А как по-Вашему вводятся теоретические понятия?
Аксиомами. Это не значит, что они "считаются уже введёнными". Например, как определяется сложение в арифметике? Рекурсивно двумя аксиомами:
и
Думаю, нужно резюмировать сказанное выше в разных местах относительно того, как определяется вычислимость (рекурсивность). Не прибегая к излишней формализации, т.е. на словах,
в классическом смысле понятие "рекурсивной функции" можно ввести двумя аксиомами:
1) Любая функция, отображающая конечное множество в конечное множество, рекурсивна.
2) Любая программа, состоящая из конечного количества любых операторов, реализующих рекурсивные функции, реализует рекурсивную функцию.
Здесь следует отметить ещё раз (ибо раньше это говорилось), что:
- Обе части формулировки существенны, т.е. (2) без (1)
не приводит ни к какому содержательному понятию "алгоритма". Точно так же, как без
мы не получим никакого содержательного понятия сложения в арифметике.
- Из этого определения никоим образом не следует конечность алфавита, к которому применимы произвольные рекурсивные функции. (
Someone ранее именовал его "областью определения" алгоритма).
- Равно как из него никоим образом не следует и конечность алфавита, в котором должны записываться коды программ. Объединение двух последних алфавитов я предлагаю именовать "универсом". Т.е. универс - это множество символов, которыми могут именоваться рекурсивные функции (включая базовые операторы), а также которые могут составлять их области определения.
Однако, посмотрев конструктивным взглядом на это определение, я вижу его недостаточность. Об этом свидетельствует пример
Someone, приведённый им в
сообщении #604038, где он пытался ограничить класс базовых операций машины Тьюринга функциями с конечной областью определения. Под аксиому (1) подходит? Да. Но если алфавит, на конечных подмножествах которого определены базовые операции МТ, не является рекурсивным множеством, то базовые операции могут получиться алгоритмически неразрешимыми!
Поясняю на примере (если будут вопросы, то потом уточню): Возьмём в качестве алфавита множество действительных чисел (в стандартном смысле: как множества всех подмножеств стандартных натуральных чисел). Для определённости считаем, что если на вход любой базовой операции попадает символ, не входящий в её область определения, то выходом является
. Рассмотрим базовую операцию
, областью определения которой является множество из одного элемента:
. Таблица значений функции состоит из одного элемента:
. Известно, что равенство действительных чисел - алгоритмически неразрешимо. Мало того, существуют примеры определений таких
, для которых истинность утверждения
неизвестна (и не очевидно, что когда-либо станет известной). Это означает, что базовая операция
над данным алфавитом - нерекурсивна. Т.е. принимая аксиому (1) по отношению к ней, мы поступаем неадекватно.
Как же быть? А очень просто. Надо всего лишь не забыть принять аксиому номер ноль:
0) Универс является рекурсивным множеством.
Как свидетельствует вышеприведённый пример, эта аксиома - тоже существенна для содержательного определения алгоритма (рекурсивной функции).