Решение упражнения 1.10 из SICP

18 August, 2007 (19:34) | Решения упражнений

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

Сразу хочу уточнить, что определение функции Аккермана, данное в 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

Comments

Comment from Sergey Khenkin
Date: September 24, 2007, 10:43 am

По ссылкам http://newsgroups.derkeiler.com/Archive/Comp/comp.lang.scheme/2007-09/msg00124.html , http://newsgroups.derkeiler.com/Archive/Comp/comp.lang.scheme/2007-09/msg00126.html и http://newsgroups.derkeiler.com/Archive/Comp/comp.lang.scheme/2007-09/msg00128.html есть интересное обсуждение различий в функции Аккермана, о которых я упоминал.

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

Ддим Хефферон в ответ отмечает, что это, на его взгляд, нестандартное использование термина. Как он пишет, большинство людей понимают функцию Аккермана как обобщение следующего ряда: сложение – это многократно повторенный инкремент, умножение – это многократно повторенное сложение, возведение в степень – это многократно повторенное умножение и т.д. Тогда можно ввести функцию двух аргументов A(level,j), где, например, уровень 1 соответствует сложению, то есть A(1,j)=2j, уровень 2 – умножению, то есть A(2,j)=j^2 и т.д.

Comment from Эребус
Date: January 20, 2011, 10:04 pm

В случае (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 1 7))))
(A 0 (A 0 (A 0 (A 0 (A 1 6)))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))
(A 0 (A 0 (A 0 (A 0 (A 0 32)))))
(A 0 (A 0 (A 0 (A 0 64))))
(A 0 (A 0 (A 0 128)))
(A 0 256)
512

Comment from Эребус
Date: January 20, 2011, 10:06 pm

Извиняюсь, это я сам накосячил. Пропустил одну строку вычислений

Comment from oleg
Date: July 6, 2011, 7:05 pm

>> (A 2 4)
>> ..
>> 2^2^2^2 = 2^2^4 = 2^16 = 65536
>> ..
>> (h n) = (A 2 n) = 2^2^…^2, n > 0, где число двоек равно n

Но ведь (A 2 4) = 2^16, а не 2^4.

Comment from oleg
Date: July 6, 2011, 7:08 pm

упс .. все верно – символ “^” запутал.

Comment from Александр
Date: July 23, 2012, 5:33 pm

еще вариант:
(h n) = 0 при n = 0
(h n) = 2 при n = 1
(h n) = 2 ^ (h (- n 1)) при n > 1

n (h n) 2^(h (- n 1))
0 0 –
1 2 –
2 4 2^2
3 16 2^4
4 65536 2^16
5 ??? 2^65536

Write a comment