Например, можно ли на первом шаге по заданным аргументам сформировать программу на Паскале, вычисляющую значение функции Аккермана для этих аргументов, а на втором шаге - эту программу выполнить?
Ведь для машины Тьюринга все пути открыты, в том числе, и такой.
Ну вот почему я, собственно, и снял задачу.
От себя могу предложить такое решение. Рассмотрим функцию
![$$
c(z,x,y,v) =
\begin{cases}
1, &A(z,x,y) = v \\
0, &A(z,x,y) \neq v
\end{cases}
$$ $$
c(z,x,y,v) =
\begin{cases}
1, &A(z,x,y) = v \\
0, &A(z,x,y) \neq v
\end{cases}
$$](https://dxdy-04.korotkov.co.uk/f/f/8/4/f84fa71ce630e17b79879c175c9dcbd782.png)
Она примитивно рекурсивна и её можно запрограммировать только с циклами for. Затем напишем
v := 0;
while c(z,x,y,v) = 0 do inc(v);
A := v - 1;
Пока вроде рекурсии не наблюдается. Но... когда будем вычислять
![$c$ $c$](https://dxdy-04.korotkov.co.uk/f/3/e/1/3e18a4a28fdee1744e5e3f79d13b9ff682.png)
, будет for и внутри него будет меняться параметр, причём меняться достаточно сложным образом, так, чтобы каждое текущее значение можно было развернуть и путём некоторых вычислений вытащить из него все предыдущие (типа если
![$p_0, p_1, \ldots$ $p_0, p_1, \ldots$](https://dxdy-04.korotkov.co.uk/f/b/9/9/b9938fd9b7d5972bd12cce77c093f21882.png)
--- все простые числа, перечисленные в порядке возрастания и
![$\phi(t) = p_0^{a_0} \cdot p_1^{a_1} \cdot \ldots \cdot p_t^{a_t}$ $\phi(t) = p_0^{a_0} \cdot p_1^{a_1} \cdot \ldots \cdot p_t^{a_t}$](https://dxdy-01.korotkov.co.uk/f/4/a/3/4a3a9f8b6217817326410a34e90772bd82.png)
, то
![$\phi(t+1) = \phi(t) \cdot p_{t+1}^{\psi(a_0,\ldots,a_t)}$ $\phi(t+1) = \phi(t) \cdot p_{t+1}^{\psi(a_0,\ldots,a_t)}$](https://dxdy-03.korotkov.co.uk/f/a/d/5/ad52f3636471bd3823d49d6695c3e45b82.png)
). А это, наверное, всё же рекурсия
![Sad :(](./images/smilies/icon_sad.gif)
Я теперь уже сам не понимаю, за каким чёртом в Аккермана полез. Ведь если разобраться, то и
![$f(n) = n!$ $f(n) = n!$](https://dxdy-03.korotkov.co.uk/f/6/a/e/6aefd21a029385e191cf48d51c460a5082.png)
без рекурсии не вычислить! Да и возведение в степень тоже. Сложение/умножение можно, в столбик там складываем/умножаем, а возведение в степень уже всё
-- Чт ноя 05, 2009 08:19:24 --Проблема с формализацией в том, что непонятно, какие вещи следует считать рекурсией, а какие нет. Для примера рассмотрим два варианта кода, вычисляющего функцию
![$F(n) = n!$ $F(n) = n!$](https://dxdy-04.korotkov.co.uk/f/f/c/a/fcaf6e1db898db1cc98a0f0ee5856bda82.png)
function F(n: integer): integer;
begin
if n = 0 then F := 1 else F := F(n-1)*n
end;
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)$ $F(0),F(1), \ldots,F(n)$](https://dxdy-03.korotkov.co.uk/f/6/f/3/6f37d94d76371e052fa0881754c796b482.png)
, причём каждый следующий член последовательности выражаем через предыдущий! Тот же хрен, только в профиль. Можно ещё третий вариант предложить:
function F(n: integer): integer;
var i,m: integer;
begin
m := 1;
for i := n downto 1 do m := m*i;
F := m
end;
С одной стороны, он ничем не отличается от второго, только что цикл "в другую сторону направлен". А с другой стороны, здесь даже "направление вычислений" (только не спрашивайте, что это такое, я сам не знаю
![Smile :)](./images/smilies/icon_smile.gif)
) то же самое, что в первом варианте.