Существование явной формулы для рекурсивного алгоритма

[slavav]

Функция Аккермана в качестве контрпримера.

[mihaild]

maximkarimov в сообщении #1438103 писал(а):

рекурсивный алгоритм

Примитивно или обще рекурсивный алгоритм (разрешена ли минимизация)?

maximkarimov в сообщении #1438103 писал(а):

в том смысле, что (любой) n-член Y может быть вычислен подстановкой n в некоторое уравнение-тождество

Какие операции разрешены в этом уравнении?

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

[maximkarimov]

mihaild в сообщении #1438112 писал(а):

maximkarimov в сообщении #1438103 писал(а):

рекурсивный алгоритм

Примитивно или обще рекурсивный алгоритм (разрешена ли минимизация)?

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

maximkarimov в сообщении #1438103 писал(а):

в том смысле, что (любой) n-член Y может быть вычислен подстановкой n в некоторое уравнение-тождество

Какие операции разрешены в этом уравнении? Скажем $n\uparrow\uparrow n$ является примитивно рекурсивной функцией, но не выражается через стандартные элементарные (арифметику и степень), т.к. растет слишком быстро.[/quote]

Без ограничений.

[mihaild]

maximkarimov в сообщении #1438142 писал(а):

указание на свойство "рекурсивности" алгоритма X можно вообще опустить

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

maximkarimov в сообщении #1438142 писал(а):

Без ограничений

Ну тогда введем вспомогательную функцию $f(n, m)$, которая выдает результат $m$-го алгоритма на числе $n$. Тогда любая последовательность, задающаяся алгоритмом, задается и формулой $f(n, m_0)$ для некоторого $m_0$.