Вычисления с бесконечным алфавитом

[arseniiv]

Вот тут (с. 45) множество символов, возможных в ячейках, сразу определяется конечным. Кроме того, лента ограничена с одной стороны, и в самой левой ячейке символ фиксирован. Даже такая машина «подходит».

[Munin]

Ну, что полубесконечная МТ не хуже бесконечнолентной - это тоже теорема такая есть. Меня удивляет, зачем включать в определения следствия таких теорем, если их всё равно доказывать позже введения понятия.

[arseniiv]

С полубесконечной, мне кажется, проще доказать всё основное. Хотя сравнивать не доводилось.

-- Вс авг 05, 2012 23:03:41 --

Да и выглядит она реализуемее.

[Munin]

По-моему, без разницы.

[epros]

Munin в сообщении #603246 писал(а):

Вы не знаете, что такое отрезок? Или кривляетесь? Я надеялся у вас чему-то научиться, а не подыгрывать вашей клоунаде.

Munin, я спросил у Вас, как Вы определяете действительное число. Это потому, что я знаю разные определения и ответ на Ваш вопрос от этого зависит. А Вы мне начинаете вместо этого отрезки чертить.

(Оффтоп)

Арсеньев Дерсу Узале:
— Как ты думаешь, что такое Солнце?
Дерсу Узала (удивлённо):
— Вон оно, смотри.

Значит у вас есть шанс научиться корректно определять действительные числа. Если не будете бравировать невежеством (за что кому-то другому уже надавали бы по ушам в не очень вежливых выражениях). Я, знаете ли, обратил внимание на Ваши рассуждения где-то в другой теме несколько дней назад про то, что в реальности якобы «нет действительных чисел»…

На остальное не отвечаю, ибо новых содержательных вопросов не вижу, а обучать Вас пониманию рекурсивных множеств я не нанимался - на конкретные вопросы ответил, и ладно.

[epros]

Ладно, буду исходить из маловероятной гипотезы "добросовестного непонимания" и отвечу на один вопрос:

Munin в сообщении #603246 писал(а):

Там только одна "базовая операция": переход из состояния $q_1$ в состояние $q_2,$ в зависимости от считанного символа, и одновременно с записью символа, а потом сдвигом. Она рекурсивная или нерекурсивная?

Если алфавит - не есть рекурсивное множество, то - не рекурсивная.

[Munin]

epros в сообщении #603292 писал(а):

Это потому, что я знаю разные определения и ответ на Ваш вопрос от этого зависит.

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

epros в сообщении #603292 писал(а):

обучать Вас пониманию рекурсивных множеств я не нанимался

Ну что ж, жаль. Я думал, мы все здесь друг друга чему-то учим. Нет, так нет.

epros в сообщении #603292 писал(а):

Я, знаете ли, обратил внимание на Ваши рассуждения где-то в другой теме несколько дней назад про то, что в реальности якобы «нет действительных чисел»…

А что, не так? Ну и высказались бы там. Вообще, это довольно общеизвестный факт...

-- 06.08.2012 13:33:09 --

epros в сообщении #603332 писал(а):

Если алфавит - не есть рекурсивное множество, то - не рекурсивная.

О как. Ну, тоже кое-что проясняет.

[Mathusic]

(Оффтоп)

Munin в сообщении #603357 писал(а):

epros в сообщении #603292 писал(а):

Я, знаете ли, обратил внимание на Ваши рассуждения где-то в другой теме несколько дней назад про то, что в реальности якобы «нет действительных чисел»…

А что, не так? Ну и высказались бы там. Вообще, это довольно общеизвестный факт...

Ссылочку можно на тему?
Заинтриговали вы меня, господа

[epros]

Munin в сообщении #603357 писал(а):

те, которые я знаю, все эквивалентны: бесконечные дроби, дедекиндовы сечения

Эквивалентность разных определений - это на самом деле вопрос выбранной аксиоматики. Т.е., скажем, если в ZFC их эквивалентность доказуема, то в какой-то другой аксиоматике может оказаться опровержимой.

Возьмём для примера бесконечную двоичную дробь: С точки зрения ZFC это то же самое, что двузначная функция натурального аргумента. Или то же самое, что подмножество стандартных натуральных чисел. Вы знаете способ "за один ход" напечатать бесконечную двоичную дробь? Я нет. Отлично, тогда можно подкорректировать аксиоматику, чтобы было можно. Например, "вычислимое число" определяется как алгоритм, который по заданному ему на вход натуральному числу генерирует нуль или единицу. Код такого алгоритма в принципе можно напечатать "за один ход" (правда нельзя за один ход определить, что это правильный код). Но дело в том, вычислимое число - уже совсем другой объект. В частности, множество вычислимых чисел оказывается не замкнутым относительно разности.

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

Или, скажем, мы посмотрели на два последние определения и они нас не удовлетворили: А как же "невычислимые числа", о существовании которых нам твердили большевики говорит ZFC? Хочется такое определение, чтобы число и "можно было напечатать", и в то же время чтобы туда входили те самые невычислимые числа. А пожалуйста: Берем формулу ZFC $\varphi(x)$, для которой доказуемо существование и единственность объекта $x$, а также доказуем тот факт, что объект $x$ является подмножеством минимального индуктивного множества. В переводе на нормальный язык это означает, что формула определяет конкретное стандартное действительное число. Разумеется, формулу в языке теории множеств напечатать можно. Осталось только соответствующую формулу найти и доказать. Один из примеров нам уже известен - это формула, определяющая число:

$x = \sum\limits_{n=1}^{\infty} \frac{1}{\Sigma(n)}$.

(Разумеется, это не полная запись формулы. Полная формула включает определение функции $\Sigma(n)$ - busy beaver.) Существование и единственность такого числа доказуемы в ZFC. И что ещё более интересно - доказуема его невычислимость.

Вот ещё один интересный вариант определения: Определяем "действительное число" как элемент real closed field. Чисто формально. Чем замечательно такое определение? Во-первых, любое утверждение о свойствах таких объектов, формализуемое в языке логики первого порядка, эквивалентно такому же утверждению о свойствах действительных чисел. Т.е., грубо говоря, "свойства ничем не отличаются от свойств действительных чисел" (правда только с точки зрения логики первого порядка). А во-вторых, внимание: теория первого порядка для таких объектов алгоритмически разрешима. Т.е. она не просто полна и непротиворечива, а ещё и существует алгоритм, который доказывает или опровергает любое предложение.

Munin в сообщении #603357 писал(а):

epros в сообщении #603292 писал(а):

Я, знаете ли, обратил внимание на Ваши рассуждения где-то в другой теме несколько дней назад про то, что в реальности якобы «нет действительных чисел»…

А что, не так? Ну и высказались бы там. Вообще, это довольно общеизвестный факт...

Не, ну в каком-то смысле можно говорить, что в реальности "вообще ничего нет", кроме непосредственных ощущений: Даже "яблока", которое мы берём и пробуем, нет, а есть только вкус, цвет, запах и т.п. Но Вы-то там что-то говорили относительно диагонали единичного квадрата - что, мол, как только начинаем разбираться в деталях, оказывается, что это был не квадрат, и т.п. А зачем нам тогда вообще было определять понятие квадрата, если их "вообще не бывает"? Наверное, всё же для описания чего-то реального. Наплевать, что описание может быть не идеально. Но вопрос о длине диагонали квадрата ведь законен? И как же Вы на него отвечаете, если полагаете, что действительных чисел "не бывает"?

По моим представлениям, понятие действительного числа ничуть не хуже понятия натурального. Да, и то, и другое - абстракции, но всё же применимые на практике.

[Munin]

epros в сообщении #603449 писал(а):

Эквивалентность разных определений - это на самом деле вопрос выбранной аксиоматики. Т.е., скажем, если в ZFC их эквивалентность доказуема, то в какой-то другой аксиоматике может оказаться опровержимой.

Хорошо. Значит, ZFC. Хотя нам на первом курсе ещё не говорили, что это ZFC :-)

epros в сообщении #603449 писал(а):

Вы знаете способ "за один ход" напечатать бесконечную двоичную дробь? Я нет.

Я не знаю, что такое в математике "напечатать".

Я могу себе представить некую абстракцию от реального действия печати, типа "поставить штамп", или "последовательность штампов". И не вижу проблемы (если только это не оговорено отдельно), чтобы на "штампе" было написано бесконечно длинное число, и его можно было "напечатать" одним приложением штампа. Это же абстракция, всё равно. И по сути, мы делаем очень близкое к этому действие, когда говорим "число $\pi$". Да даже "$0{,}(3)$".

epros в сообщении #603449 писал(а):

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

Всё острее недефинированность того, что вы называете "за один ход". Я могу представить себе "одно прикладывание штампа при печати". Я могу представить себе "один шаг работы машины Тьюринга". Но это явно не то.

epros в сообщении #603449 писал(а):

В частности, множество вычислимых чисел оказывается не замкнутым относительно разности.

Кажется, начинаю смутно улавливать какие-то параллели с рядами и с ординальными числами...

epros в сообщении #603449 писал(а):

Не, ну в каком-то смысле можно говорить, что в реальности "вообще ничего нет", кроме непосредственных ощущений

Я говорил в другом смысле, в котором яблоки и атомы всё-таки есть.

epros в сообщении #603449 писал(а):

А зачем нам тогда вообще было определять понятие квадрата, если их "вообще не бывает"?

Стоп, "вообще не бывает" я не произносил. В мыслях - конечно бывает. "Не бывает" в реальности, как физических тел, точно соответствующих математическим абстракциям. Ну, пока речь шла о том, чтобы поделить сторону пополам, или провести биссектрису, большая точность не требовалась, но как только математик потребовал длину диагонали с бесконечным числом значащих цифр, реальность забарахлила: несколько цифр, ну даже пару десятков, она вам ещё выдаст, а дальше - увы. Вот и получается, что в реальности длина диагонали квадрата - это где-то между 1,414 и 1,415, а представление о том, что оно выражается как $\sqrt{2},$ и что $\sqrt{2}$ несоизмерима с $1$ - это всё конструкции уже мысленные.

epros в сообщении #603449 писал(а):

А зачем нам тогда вообще было определять понятие квадрата, если их "вообще не бывает"? Наверное, всё же для описания чего-то реального.

Да, разумеется, только описание описуемому не тождественно.

epros в сообщении #603449 писал(а):

А зачем нам тогда вообще было определять понятие квадрата, если их "вообще не бывает"? Наверное, всё же для описания чего-то реального. Наплевать, что описание может быть не идеально.

Ровно наоборот: описание получилось гораздо более идеально, чем то, для чего оно предназначалось. И в смысле "утончённо, безупречно", и в смысле "нематериально, мысленно, абстрагировано, призрачно".

epros в сообщении #603449 писал(а):

Но вопрос о длине диагонали квадрата ведь законен? И как же Вы на него отвечаете, если полагаете, что действительных чисел "не бывает"?

На всякий случай ещё раз: я не говорил, что их "не бывает", я говорил, что их "не бывает в реальности". А в человеческих мыслях и идеях - пожалуйста.

[epros]

Munin в сообщении #603488 писал(а):

Я могу себе представить некую абстракцию от реального действия печати, типа "поставить штамп", или "последовательность штампов". И не вижу проблемы (если только это не оговорено отдельно), чтобы на "штампе" было написано бесконечно длинное число, и его можно было "напечатать" одним приложением штампа. Это же абстракция, всё равно. И по сути, мы делаем очень близкое к этому действие, когда говорим "число $\pi$". Да даже "$0{,}(3)$".

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

Кстати, когда мы говорим про "число $\pi$", то вовсе не абстрагируемся от его бесконечной длины. Мы имеем в виду определение числа, из которого можно вытащить любое количество знаков.

Munin в сообщении #603488 писал(а):

Всё острее недефинированность того, что вы называете "за один ход". Я могу представить себе "одно прикладывание штампа при печати". Я могу представить себе "один шаг работы машины Тьюринга". Но это явно не то.

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

Munin в сообщении #603488 писал(а):

Я говорил в другом смысле, в котором яблоки и атомы всё-таки есть.

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

Munin в сообщении #603488 писал(а):

epros в сообщении #603449 писал(а):

А зачем нам тогда вообще было определять понятие квадрата, если их "вообще не бывает"?

Стоп, "вообще не бывает" я не произносил. В мыслях - конечно бывает. "Не бывает" в реальности, как физических тел, точно соответствующих математическим абстракциям. Ну, пока речь шла о том, чтобы поделить сторону пополам, или провести биссектрису, большая точность не требовалась, но как только математик потребовал длину диагонали с бесконечным числом значащих цифр, реальность забарахлила: несколько цифр, ну даже пару десятков, она вам ещё выдаст, а дальше - увы. Вот и получается, что в реальности длина диагонали квадрата - это где-то между 1,414 и 1,415, а представление о том, что оно выражается как $\sqrt{2},$ и что $\sqrt{2}$ несоизмерима с $1$ - это всё конструкции уже мысленные.

Вы здесь смешиваете две вещи:
1) Философствования на тему того, что такое "реальность", и
2) Вопросы практического использования понятия (в данном случае - понятия действительного числа).
О первом я сейчас ничего не говорю. Проблема во втором. Насколько я понял, там Вы с энтузиазмом доказывали, что в физике действительные числа "не нужны", "не используются" или что-то в этом роде. Сейчас Вы фактически повторяете те же аргументы.

Что ж, я отвечу: В реальности (включая физические приложения) используется не бесконечная десятичная дробь, а формула, определяющая число $\sqrt{2}$. И эта формула конечна (и довольно проста). Что касается количества знаков десятичного представления, то сколько Вам нужно в конкретном случае, столько и посчитаете. Это не изменит используемого на практике понятия числа $\sqrt{2}$, изменится только понятие о точности его представления, которая Вам нужна.

Munin в сообщении #603488 писал(а):

epros в сообщении #603449 писал(а):

Наверное, всё же для описания чего-то реального. Наплевать, что описание может быть не идеально.

Ровно наоборот: описание получилось гораздо более идеально, чем то, для чего оно предназначалось. И в смысле "утончённо, безупречно", и в смысле "нематериально, мысленно, абстрагировано, призрачно".

Вы меня неправильно поняли. "Описание не идеально" - значит что оно не описывает то, что нам нужно, идеально точным и правильным образом.

[Munin]

epros в сообщении #603526 писал(а):

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

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

Это действительно часть определения? Вы можете показать её в учебниках?

epros в сообщении #603526 писал(а):

Только это всего лишь означает, что мы вернёмся к классическому понятию функции.

Это я тоже ни от кого, кроме вас, не слышал. Это теорема? Вы её можете показать в учебниках? Можете доказать сами?

epros в сообщении #603526 писал(а):

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

А какое вообще отношение математика имеет к практике??? На практике и множества $\mathbb{N}$ нет, и таблицы умножения на этом множестве. Понятно, что математические понятия для практического применения приходится "конечнизировать", огрублять и приземлять, но от этого сами понятия нисколько не страдают.

epros в сообщении #603526 писал(а):

Кстати, когда мы говорим про "число $\pi$", то вовсе не абстрагируемся от его бесконечной длины. Мы имеем в виду определение числа, из которого можно вытащить любое количество знаков.

На самом деле, нет. На самом деле, запись в виде бесконечной десятичной дроби, запись в виде дроби $1/3,$ запись в виде значка $\pi$ - это просто разные способы записи, ссылки на точку на числовой оси. Ни один из них не истиннее и не фундаментальнее другого, и процедура перевода из одного в другой вторична по отношению к ссылке на число - должна быть вторична, просто для того, чтобы поиск способа перевода из одного в другое представление был осмысленным решением осмысленной задачи, а не просто постулированием чего в голову взбредёт. $\pi$ в этом смысле не бесконечней и не конечней $1/3,$ оно равноправно с ней, а отличия между ними могут быть сформулированы в терминах иррациональных или трансцендентных чисел - то есть в другой плоскости, по отношению к процедурам и т. п.

epros в сообщении #603526 писал(а):

Любое конечное количество шагов алгоритма можно рассматривать как один шаг.

Это ещё одна теорема имени вас?

epros в сообщении #603526 писал(а):

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

А мне и не надо.

epros в сообщении #603526 писал(а):

Вы здесь смешиваете две вещи:
1) Философствования на тему того, что такое "реальность", и
2) Вопросы практического использования понятия (в данном случае - понятия действительного числа).

Я ни в коем случае не философствую. Я просто пользуюсь тем, что есть. Определения я беру из физического лексикона, а не из философского.

epros в сообщении #603526 писал(а):

Насколько я понял, там Вы с энтузиазмом доказывали, что в физике действительные числа "не нужны", "не используются" или что-то в этом роде.

Я не знаю, как задом наперёд надо меня "понимать", чтобы в результате так "понять".
Разумеется, действительные числа в физике нужны и используются. Без них физика бы развалилась как карточный домик.
Их в природе нет. А в физике (в науке) они есть. Как чрезвычайно удобное приближение к тому, что есть в природе. В 20 веке были попытки поиска других приближений, но не дали результатов, даже на том же уровне, не говоря уже о лучшем. Хотя, знакомиться с ними уже приходится ($p$-адические числа, некоммутативная геометрия).

epros в сообщении #603526 писал(а):

Что ж, я отвечу: В реальности (включая физические приложения) используется не бесконечная десятичная дробь, а формула, определяющая число $\sqrt{2}$.

В реальности ничего не используется, в реальности просто что-то есть. Например, атомы, яблоки и квадратные табуретки, состоящие из целого числа атомов.
В практической деятельности человека, включая физические приложения, которые к реальности относятся всё-таки косвенно, используется очень много чего - и формула, и дробь (конечная), и намного чаще - просто символ $\sqrt{2}.$

epros в сообщении #603526 писал(а):

Вы меня неправильно поняли. "Описание не идеально" - значит что оно не описывает то, что нам нужно, идеально точным и правильным образом.

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

[epros]

(Оффтоп)

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

Munin в сообщении #603535 писал(а):

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

Как минимум рекурсивность. Элементарность автоматически подразумевает рекурсивность. А поскольку её (элементарности) и достаточно для исчерпывающего определения алгоритма, то нет смысла (но не запрещено!) рассматривать бесконечные (но рекурсивные) алфавиты и проч.

Ёлы-палы, это ведь не я заговорил про несчётные алфавиты и т.п. Прямо театр абсурда какой-то...

Munin в сообщении #603535 писал(а):

Это я тоже ни от кого, кроме вас, не слышал. Это теорема? Вы её можете показать в учебниках? Можете доказать сами?

Что тут доказывать? Вы рассматриваете алгоритм как отображение аргумента на некое множество значений (без ограничений на рекурсивность). См. классическое определение функции и сравнивайте.

Munin в сообщении #603535 писал(а):

Это ещё одна теорема имени вас?

Это ещё одна банальность, сомневаться в которой может, уж извините за резкость, либо идиот, либо злобный тролль.

Munin в сообщении #603535 писал(а):

Разумеется, действительные числа в физике нужны и используются. Без них физика бы развалилась как карточный домик.
Их в природе нет. А в физике (в науке) они есть.

Вы только что де-факто доказывали обратное, ибо 1,414 и 1,415 - это рациональные числа, использование которых не требует понятия о действительных числах.

Munin в сообщении #603535 писал(а):

Как чрезвычайно удобное приближение к тому, что есть в природе

Действительное число - это не "приближение". Приближение - это конечная десятичная дробь. Причём приближение не к "природе", а как раз к действительному числу. Число $\sqrt{2}$ выражает длину диагонали единичного квадрата. Здесь и "число" и "квадрат" - абстрактные понятия. И отношение "выражает" между ними является точным (в рамках геометрии), а никаким не "приближением". Причём оба понятия (и "числа", и "квадрата") применимы на практике - не смотря на то, что точность измерения длины диагонали и достоверность установления самого факта, что рассматриваемый объект является квадратом, ограничены.

(Оффтоп)

Как можно рассуждать о каких-то действительно-значных алфавитах, имея такие "детские" представления о том, что такое действительное число?

-- Вт авг 07, 2012 11:13:19 --

Munin в сообщении #603535 писал(а):

А какое вообще отношение математика имеет к практике???

У меня нет слов... Вы никогда не использовали на практике таблицу умножения? Это - не математика? Такой риторический вопрос, предполагаемый ответ на который на самом деле неверен, это тот ещё приёмчик...

[epros]

Munin в сообщении #603535 писал(а):

На самом деле, запись в виде бесконечной десятичной дроби, запись в виде дроби $1/3$ запись в виде значка $\pi$ - это просто разные способы записи, ссылки на точку на числовой оси.

В надежде на "добросовестное непонимание" поясню ещё раз:
1) Запись числа $\pi$ "в виде бесконечной дроби" на практике до сих пор не встречалась.
2) Запись в виде значка "$\pi$" не является определением числа. Это просто обозначение, присвоение собственного имени.

Теперь контрольный вопрос:
Как объяснить человеку, никогда не слышавшему про число $\pi$, что это за число?

[Someone]

epros, Вы чего-то чудите.
О базовых операциях алгоритма всегда предполагается только одно: исполнитель алгоритма умеет их выполнять. Не вдаваясь в детали того, как он это делает.
То же самое касается алфавита. Единственное предположение об алфавите состоит в том, что исполнитель алгоритма умеет распознавать и писать символы алфавита. Без уточнения того, как он это делает.

Надо также иметь в виду, что описание алгоритма по определению является конечным и потому может явно ссылаться только на конечное число символов алфавита.

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