Задачки на рекурсию.

[PapaKarlo]

Профессор Снэйп в сообщении #258330 писал(а):

Я специально дал ссылку на определение функции Аккермана, которое надо использовать в задаче.

Подскажите темному, что такое $\mathrm{sgn}(z)$, которая используется в определении

$A(z+1,x,0)=\mathrm{sgn}(z)$

Правильно ли я понимаю, что

$z=-1,\;\;\;A(0,x,0)=x$
$z=\;\;0,\;\;\;\;A(1,x,0)=0$
$z=\;\;1,\;\;\;\;A(2,x,0)=1$
$z=\;\;2,\;\;\;\;A(3,x,0)=x$

Функция $\mathrm{sgn}(z)$ по формальным признакам зависит лишь от $z$, а равная ей функция $A(z+1,x,0)$ зависит еще и от $x$...

[Maslov]

Профессор Снэйп в сообщении #258330 писал(а):

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

Профессор Снэйп в сообщении #92740 писал(а):

Если воспринимать $A(z,x,y)$ как операцию над $x$ и $y$ уровня $z$, то операция каждого следующего уровня получается при помощи применения к иксу операции предыдущегно уровня $y$ раз. В частности, $x \cdot y$ --- это икс, сложенный сам с собою игрек раз, $x^y$ --- это икс, умноженный сам на себя игрек раз и т. д. Формально определение $A$ даётся следующей схемой:

$A(0,x,y) = x+y$
$A(z+1,x,0) = \mathrm{sgn}(z)$
$A(z+1,x,y+1) = A(z, x, A(z+1,x,y))$

Что-то я в Роджерсе несколько другое определение нашел:

Х.Роджерс в книге 'Теория рекурсивных функций и эффективная вычислимость' (М.: Мир, 1972) на стр. 25 писал(а):

Более формальное (и "рекурсивное") определение для этой функции задается так:
$f(0, 0, y) = y,$
$f(0, x+1, y) = f(0, x, y) + 1,$
$f(1,0,y) = 0,$
$f(z+2, 0, y) = 1,$
$f(z+1, x+1, y) = f(z, f(z+1, x, y), y).$

хотя это, вроде бы, то же самое

-- Чт ноя 05, 2009 01:28:48 --

PapaKarlo в сообщении #258413 писал(а):

Подскажите темному, что такое $\mathrm{sgn}(z)$, которая используется в определении

$A(z+1,x,0)=\mathrm{sgn}(z)$

это просто $\mathrm{sign}$

[Профессор Снэйп]

Maslov в сообщении #258462 писал(а):

Что-то я в Роджерсе несколько другое определение нашел

Ага, на стр. 25. По сути оно то же самое

Maslov в сообщении #258462 писал(а):

хотя это, вроде бы, то же самое

С точностью до перестановки аргументов $x$ и $y$

PapaKarlo в сообщении #258413 писал(а):

Подскажите темному, что такое $\mathrm{sgn}(z)$

$$ \mathrm{sgn}(z) = \begin{cases} 0, &z=0 \\ 1, &z>0 \end{cases} $$

[Maslov]

Профессор Снэйп в сообщении #258330 писал(а):

Речи об эффективности вообще не идёт. Вычисления могут быть значительно менее эффективными, чем с использованием рекурсии. Интересует лишь сама возхможность запрограммировать вычисления функции Аккермана без рекурсивного вызова.

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

[venco]

Maslov в сообщении #258466 писал(а):

Профессор Снэйп в сообщении #258330 писал(а):

Речи об эффективности вообще не идёт. Вычисления могут быть значительно менее эффективными, чем с использованием рекурсии. Интересует лишь сама возхможность запрограммировать вычисления функции Аккермана без рекурсивного вызова.

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

У машины Тюринга нет и запрета на эмуляцию стека.

[Maslov]

venco в сообщении #258468 писал(а):

У машины Тюринга нет и запрета на эмуляцию стека.

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

[Профессор Снэйп]

Maslov в сообщении #258466 писал(а):

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

Ну вот почему я, собственно, и снял задачу.

От себя могу предложить такое решение. Рассмотрим функцию

$$ c(z,x,y,v) = \begin{cases} 1, &A(z,x,y) = v \\ 0, &A(z,x,y) \neq v \end{cases} $$

Она примитивно рекурсивна и её можно запрограммировать только с циклами for. Затем напишем

Используется синтаксис Pascal

v := 0;
while c(z,x,y,v) = 0 do inc(v);
A := v - 1; 

Пока вроде рекурсии не наблюдается. Но... когда будем вычислять $c$, будет for и внутри него будет меняться параметр, причём меняться достаточно сложным образом, так, чтобы каждое текущее значение можно было развернуть и путём некоторых вычислений вытащить из него все предыдущие (типа если $p_0, p_1, \ldots$ --- все простые числа, перечисленные в порядке возрастания и $\phi(t) = p_0^{a_0} \cdot p_1^{a_1} \cdot \ldots \cdot p_t^{a_t}$, то $\phi(t+1) = \phi(t) \cdot p_{t+1}^{\psi(a_0,\ldots,a_t)}$). А это, наверное, всё же рекурсия

Я теперь уже сам не понимаю, за каким чёртом в Аккермана полез. Ведь если разобраться, то и $f(n) = n!$ без рекурсии не вычислить! Да и возведение в степень тоже. Сложение/умножение можно, в столбик там складываем/умножаем, а возведение в степень уже всё

-- Чт ноя 05, 2009 08:19:24 --

Проблема с формализацией в том, что непонятно, какие вещи следует считать рекурсией, а какие нет. Для примера рассмотрим два варианта кода, вычисляющего функцию $F(n) = n!$

Используется синтаксис Pascal

function F(n: integer): integer;
begin
  if n = 0 then F := 1 else F := F(n-1)*n
end;

Используется синтаксис Pascal

function F(n: integer): integer;
var i,m: integer;
begin
  m := 1;
  for i := 1 to n do m := m*i;
  F := m
end;

Первый вариант однозначно "рекурсивный". А второй? С одной стороны нет, а с другой --- алгоритм тот же самый, просто мы "заранее" вычисляем значения, которые нам впоследствии понадобятся для рекурсивного вызова. Ведь мы по сути просто вычисляем последовательность $F(0),F(1), \ldots,F(n)$, причём каждый следующий член последовательности выражаем через предыдущий! Тот же хрен, только в профиль. Можно ещё третий вариант предложить:

Используется синтаксис Pascal

function F(n: integer): integer;
var i,m: integer;
begin
  m := 1;
  for i := n downto 1 do m := m*i;
  F := m
end;

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

[venco]

Профессор Снэйп в сообщении #258473 писал(а):

Рассмотрим функцию

$$ c(z,x,y,v) = \begin{cases} 1, &A(z,x,y) = v \\ 0, &A(z,x,y) \neq v \end{cases} $$

Она примитивно рекурсивна и её можно запрограммировать только с циклами for.

Я не знаю термина "примитивно рекурсивная", но объясните, каким образом такая функция может оказаться "менее рекурсивная", чем исходная?

[Профессор Снэйп]

venco в сообщении #258480 писал(а):

Я не знаю термина "примитивно рекурсивная"

См. здесь, стр. 51 -- 60 и 112 -- 118.

venco в сообщении #258480 писал(а):

...объясните, каким образом такая функция может оказаться "менее рекурсивная", чем исходная?

Количество рекурсивных вызовов меньше, требуется стек меньшей высоты. "Меньше" в том смысле, что его можно "заранее" ограничить, до того, как мы начнём к нему обращаться.

Чем отличается цикл for от цикла while? Тем, что в случае с for количество итераций в цикле известно до начала его выполнения (если мы, конечно, придерживаемся правил структурного программирования, то есть не используем конструкции типа if ... then goto, не меняем значение переменной, обозначающей границу цикла, внутри самого цикла и не занимаемся прочими столь же гадкими вещами). Так вот: примитивно рекурсивные функции --- это, в точности, функции, которые можно запрограммировать с использованием только цикла for, без циклов while и repeat ... until.

[venco]

Профессор Снэйп в сообщении #258481 писал(а):

venco в сообщении #258480 писал(а):

Я не знаю термина "примитивно рекурсивная"

См. здесь, стр. 51 -- 60 и 112 -- 118.

Мда... смог скачать 17Кб из 1Мб.

Профессор Снэйп в сообщении #258481 писал(а):

venco в сообщении #258480 писал(а):

...объясните, каким образом такая функция может оказаться "менее рекурсивная", чем исходная?

Количество рекурсивных вызовов меньше, требуется стек меньшей высоты. "Меньше" в том смысле, что его можно "заранее" ограничить, до того, как мы начнём к нему обращаться.

Не, что это означает я догадываюсь.
Мне непонятно каким образом ваша функция $c()$ обходится меньшей рекурсией чем $A()$, если она её вызывает.

[Профессор Снэйп]

venco в сообщении #258482 писал(а):

Мне непонятно каким образом ваша функция $c()$ обходится меньшей рекурсией чем $A()$, если она её вызывает.

??? Пока что наоборот, $A$ "вызывает" $c$

Тут есть ещё такой момент. Естественно измерять зависимость привлекаемых для вычисления ресурсов от входных данных. Чем длиннее вход, тем больше памяти/времени и т. д. нужно на его обработку. Это естественно.

Функция $A$ очень быстро растёт, то есть при малых $z,x,y$ число $A(z,x,y)$ может быть очень велико. В этом смысле вычислять $A$ крайне трудоёмко. Что же касается $c$, то её вычисление менее трудоёмко по той причине, что приходится считать значения $c(z,x,y,v)$ при очень больших $v$, так что количество вычислительных ресурсов растёт в зависимости от длины входа гораздо слабее. Просто потому, что при тех же самых вычислениях вход длиннее

Мы не можем оценить количество итераций, необходимых для вычисления $A(z,x,y)$, имея в своём распоряжении лишь $z$, $x$ и $y$. Однако имея $v$, мы можем по нему оценивать количество итераций, необходимых для проверки равенства $A(z,x,y)=v$.

-- Чт ноя 05, 2009 16:30:21 --

venco в сообщении #258482 писал(а):

Мда... смог скачать 17Кб из 1Мб.

Ага, тупит оно иногда знатно. Просто подождите, время от времени оно всё же начинает работать с приемлемой скоростью

-- Чт ноя 05, 2009 16:34:24 --

Кстати, у меня только что скачалось нормально. Попробуйте сейчас, может, получится.

[Maslov]

Профессор Снэйп в сообщении #258473 писал(а):

Первый вариант однозначно "рекурсивный". А второй? С одной стороны нет, а с другой --- алгоритм тот же самый, просто мы "заранее" вычисляем значения, которые нам впоследствии понадобятся для рекурсивного вызова. Ведь мы по сути просто вычисляем последовательность $F(0),F(1), \ldots,F(n)$, причём каждый следующий член последовательности выражаем через предыдущий! Тот же хрен, только в профиль.

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

Разница такая же, как между рекуррентным определением

$$ \mathrm{F}(n) = \begin{cases} 0, &n=0 \\ 2 \mathrm{F}(n-1)+1, &n>0 \end{cases} $$

и итеративным вариантом вычисления той же функции

$$ \mathrm{F}(n) = 2^n - 1, &n\ge 0 $$

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

-- Чт ноя 05, 2009 14:20:13 --

Профессор Снэйп в сообщении #258481 писал(а):

Количество рекурсивных вызовов меньше, требуется стек меньшей высоты. "Меньше" в том смысле, что его можно "заранее" ограничить, до того, как мы начнём к нему обращаться.

Всё-таки не могли бы Вы пояснить, почему мы можем заранее ограничить количество итераций при проверке условия

$$A(x,y,z) = v$$

и не можем этого сделать при вычислении

$$A(x, y, z)$$

[Профессор Снэйп]

Maslov в сообщении #258549 писал(а):

Всё-таки не могли бы Вы пояснить, почему мы можем заранее ограничить количество итераций при проверке условия

$$A(x,y,z) = v$$

и не можем этого сделать при вычислении

$$A(x, y, z)$$

Да, ну что тут непонятного? Вот есть некий класс $\mathcal{F}$ достаточно медленно растущих функций. Существует $f \in \mathcal{F}$, такая что условие $A(z,x,y)=v$ проверяется не более чем за $f(z,x,y,v)$ шагов вычислений. Но не существует $g \in \mathcal{F}$, такой что $A(z,x,y)$ вычисляется за $\leqslant g(z,x,y)$ шагов. В первом случае число $v$ допускается в качестве аргумента функции, во втором --- нет.

Когда Вы спрашиваете "заранее ограничить", уточняйте: ограничить, исходя из чего. Зная $v$, мы можем из него исходить и найти ограничение в виде некоторой "простой" функции от $v$. А если $v$ нам не известно, то это уже невозможно.

[Nik_Svan]

Профессор Снэйп писал(а):

Да, ну что тут непонятного?

Зря вы так. Если Маслов вас затянет на свою территорию, то вы не сможете ответить и на совсем элементарные вопросы.

[venco]

Профессор Снэйп в сообщении #258656 писал(а):

Maslov в сообщении #258549 писал(а):

Всё-таки не могли бы Вы пояснить, почему мы можем заранее ограничить количество итераций при проверке условия

$$A(x,y,z) = v$$

и не можем этого сделать при вычислении

$$A(x, y, z)$$

Да, ну что тут непонятного? Вот есть некий класс $\mathcal{F}$ достаточно медленно растущих функций. Существует $f \in \mathcal{F}$, такая что условие $A(z,x,y)=v$ проверяется не более чем за $f(z,x,y,v)$ шагов вычислений. Но не существует $g \in \mathcal{F}$, такой что $A(z,x,y)$ вычисляется за $\leqslant g(z,x,y)$ шагов. В первом случае число $v$ допускается в качестве аргумента функции, во втором --- нет.

Когда Вы спрашиваете "заранее ограничить", уточняйте: ограничить, исходя из чего. Зная $v$, мы можем из него исходить и найти ограничение в виде некоторой "простой" функции от $v$. А если $v$ нам не известно, то это уже невозможно.

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