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

[maximkarimov]

Имеется рекурсивный алгоритм X с единственным входным (натуральным) аргументом n и единственным выходным (тоже натуральным) аргументом (или значением) m. Каково необходимое и достаточное условие для существования/несуществования замкнутого выражения для целочисленной последовательности, которая задана алгоритмом Х? Иными словами, в каком случае можно утверждать существование/несуществование явной формулы для целочисленной последовательности, которая задана рекурсивным алгоритмом?

[arseniiv]

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

-- Вс фев 02, 2020 22:55:59 --

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

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

Наконец, как алгоритм соотносится с последовательностью? $n$-й элемент последовательности равен результату выполнения алгоритма с параметром $n$ или например результату $n$-кратного применения алгоритма к некоторому начальному значению? (и может быть тогда именно это имелось в виду под рекурсивностью?..)

[maximkarimov]

arseniiv в сообщении #1437979 писал(а):

как алгоритм соотносится с последовательностью? $n$-й элемент последовательности равен результату выполнения алгоритма с параметром $n$

Именно так.

[worm2]

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

[mihaild]

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

[пианист]

maximkarimov
А как Вы различаете "алгоритм", "замкнутое выражение" и "явную формулу"?

[maximkarimov]

пианист в сообщении #1437993 писал(а):

maximkarimov
А как Вы различаете "алгоритм", "замкнутое выражение" и "явную формулу"?

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

[mihaild]

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

упорядоченный набор арифметических операций над совокупностью чисел

Какие операции считаются арифметическими?

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

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

Это не определение. Точнее в таком виде под него подходит вообще любое преобразование (и достаточно всего одной операции "получить ответ по входу").
Зато не видно где в вашем определении могли бы быть циклы или рекурсия, а они очень существенны в стандартном понятии алгоритма.

Вы пытаетесь придумать своё определение алгоритма потому что не знаете стандартного, или потому что оно вам не нравится? В первом случае - вы можете познакомиться с ним в учебниках (например Верещагин, Шень "Вычислимые функции"). Во втором - вам нужно сформулировать своё определение на том же уровне строгости, что и стандартное.

[maximkarimov]

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

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

Вы пытаетесь придумать своё определение алгоритма потому что не знаете стандартного, или потому что оно вам не нравится?

Ни то не другое - я строго ответил на заданный мне вопрос (как я различаю понятия "формула" и "алгоритм").
ЗЫ. Что касается претензий к моему чрезмерно широкому, по Вашему мнению, определению понятия "алгоритм" - да, соглашусь. Однако в контексте ответа на заданный мне вопрос (отличие формулы и алгоритма), не считаю это существенным.

-- 03.02.2020, 15:17 --

https://ru.wikipedia.org/wiki/Операция_(математика)#Арифметические

[пианист]

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

Ни то не другое - я строго ответил на заданный мне вопрос (как я различаю понятия "формула" и "алгоритм").

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

[maximkarimov]

Моя формулировка понятия "формула" не строга - согласен. Однако в контексте ответа на заданный мне вопрос (отличие формулы и алгоритма) не считаю это существенным.

У меня нет никакой формулы, а есть рекурсивный алгоритм, который задает целочисленную последовательность. И прежде, чем пытаться найти явную формулу для (любого) члена такой последовательности (в стандартном определении понятия "численная формула" - см. Вики), логично ответить на вопрос о том, существует она вообще или нет, не так ли?

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

[Aritaborian]

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

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

Это похоже разве что на попытку выдать определение элементарной функции, да и то хиловатую.

[пианист]

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

(Оффтоп)

Сомневаюсь, что стоит тратить время на подобные поиски. Лучше методом тыка попробовать подобрать формулу (если я правильно понял, про что речь).

[mihaild]

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

логично ответить на вопрос о том, существует она вообще или нет, не так ли?

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

Понятно, что вас интересует, как по некоторому одному способу задания последовательности, понять, можно ли задать эту последовательность некоторым другим способом. Непонятно, какие в точности способы вы рассматриваете, а ответ от этого зависит существенно.

[maximkarimov]

пианист в сообщении #1438095 писал(а):

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

(Оффтоп)

Сомневаюсь, что стоит тратить время на подобные поиски. Лучше методом тыка попробовать подобрать формулу (если я провильно понял, про что речь).

Да, именно так. Я тоже не слышал - потому и спрашиваю!)
Хорошо, а если так:

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

Справедливо ли данное утверждение? Если нет - почему, контрпример.