26 февр. 2010 г.

Задачка: A(4,3)

функция A(x,y) определена как
A(0,y) = 1, y ≥ 0
A(1,0) = 2
A(x,0) = x + 2, x ≥ 2
A(x + 1, y + 1) = A( A(x, y + 1), y), x ≥ 0, y ≥ 0

A(4,3) = ?


Данная функция есть функция Аккермана - простой пример вычислимой функции, которая не является примитивно рекурсивной.


F(z) = A(4, z)


Попытки вычислить A(4, 3) в лоб обречены на провал (код на clojure):
(defn A([x y]
(cond
(zero? x) 1
(and (= x 1) (zero? y)) 2
(and (>= x 2) (zero? y)) (+ x 2)
:else (recur (A (dec x) y) (dec y))
)
))

Однако, на erlang прямо в лоб решается запросто:
-module(ack).
-export([a/2]).

a(0,_) -> 1;
a(1,0) -> 2;
a(X,0) -> X+2;
a(X,Y) -> a( a(X-1,Y), Y-1).

запускаем...
$ erl
1> c(ack.erl).
{ok,ack}
2> ack:a(4,3).
ответ скрыт


Решить данную задачу на clojure вполне реально - дерзайте!

Tetrahedron
Level 1
ps. Я тем временем заработал Level 1 на Project Euler - на мой взгляд, отличный способ прокачать навыки в функциональном программировании.

5 комментариев:

Mike комментирует...
Этот комментарий был удален автором.
zahardzhan комментирует...

У меня получилось вычислить A(4, 2) с помощью стрелки Кнута. Конца вычисления A(4, 3) я не могу дождаться.

Вот функция Аккермана на Clojure, но она работает не для всех m и n:

http://gist.github.com/331757

Владимир Долженко комментирует...

@zahardzhan

a(4 3) считается - и в общем-то за приемлемое время

zahardzhan комментирует...

У archimag'а недавно видел решение на Common Lisp. А самому чото лень оптимизировать числодробилку и обходить недостатки JVM. Даёшь интересную задачу!

Gabriel комментирует...

Несколько парадоксально говорить так в контексте сравнения с Эрлангом, но я воспользовался многопоточными фичами Кложура.

(defn ack [x y]
(cond
(zero? x) 1
(and (= x 1) (zero? y)) 2
(and (>= x 2) (zero? y)) (+ x 2)
:else (let [x1 (future (ack3 (dec x) y))]
(recur @x1 (dec y)))))


Совсем не оптимально - не смог дождаться результата - но стек не переполняет. :)