SICP по-русски

Что ж, рассчитаем функцию Аккермана для указанных значений.

Сразу хочу уточнить, что определение функции Аккермана, данное в SICP, отличается от определения из некоторых других источников, например из Википедии (не только русскоязычной) и MathWorld. Впрочем, для решения поставленной перед нами задачи это не является существенным.

Сначала из условия сразу увидим, что

(f n) = (A 0 n) = 2*n.

Далее вычислим (A 1 10):

(A 1 10)
(A 0 (A 1 9))
(A 0 (A 0 (A 1 8)))
...
(A 0 (A 0 (... (A 0 (A 0 (A 1 1))) ...)))
(A 0 (A 0 (... (A 0 (A 0 2)) ...)))
(A 0 (A 0 (... (A 0 (* 2 2)) ...)))
(A 0 (A 0 (... (A 0 4) ...)))
...
(A 0 (A 0 2^8))
(A 0 (* 2 2^8))
(A 0 2^9)
2^10
1024

Таким образом

(g n) = (A 1 n) = 2^n, n>0,

(g 0) = 0.

где 2^n означает 2 в степени n

Теперь вычислим (A 2 4):

(A 2 4)
(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
...
(A 1 (A 1 2^2))
...
(A 1 2^2^2))
...
2^2^2^2 = 2^2^4 = 2^16 = 65536

Таким образом

(h n) = (A 2 n) = 2^2^...^2, n > 0

(h 0) = 0.

где число двоек равно n (на бумаге или доске это можно было бы записать в виде формулы, но HTML накладывает свои ограничения, а вставлять рисунки не хочется)

Наконец, вычисляя (A 3 3), получим:

(A 3 3)
(A 2 (A 3 2))
(A 2 (A 2 (A 3 1)))
(A 2 (A 2 2))
...
(A 2 2^2)
(A 2 4)
...
2^2^2^2 = 65536