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

Она примитивно рекурсивна и её можно запрограммировать только с циклами for. Затем напишем
v := 0;
while c(z,x,y,v) = 0 do inc(v);
A := v - 1;
Пока вроде рекурсии не наблюдается. Но... когда будем вычислять

, будет for и внутри него будет меняться параметр, причём меняться достаточно сложным образом, так, чтобы каждое текущее значение можно было развернуть и путём некоторых вычислений вытащить из него все предыдущие (типа если

--- все простые числа, перечисленные в порядке возрастания и

, то

). А это, наверное, всё же рекурсия

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

без рекурсии не вычислить! Да и возведение в степень тоже. Сложение/умножение можно, в столбик там складываем/умножаем, а возведение в степень уже всё
-- Чт ноя 05, 2009 08:19:24 --Проблема с формализацией в том, что непонятно, какие вещи следует считать рекурсией, а какие нет. Для примера рассмотрим два варианта кода, вычисляющего функцию

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;
Первый вариант однозначно "рекурсивный". А второй? С одной стороны нет, а с другой --- алгоритм тот же самый, просто мы "заранее" вычисляем значения, которые нам впоследствии понадобятся для рекурсивного вызова. Ведь мы по сути просто вычисляем последовательность

, причём каждый следующий член последовательности выражаем через предыдущий! Тот же хрен, только в профиль. Можно ещё третий вариант предложить:
function F(n: integer): integer;
var i,m: integer;
begin
m := 1;
for i := n downto 1 do m := m*i;
F := m
end;
С одной стороны, он ничем не отличается от второго, только что цикл "в другую сторону направлен". А с другой стороны, здесь даже "направление вычислений" (только не спрашивайте, что это такое, я сам не знаю

) то же самое, что в первом варианте.