アッカーマン関数

0001１３２人目の素数さん

2006/02/25(土) 15:32:16

不思議

0002１３２人目の素数さん

2006/02/25(土) 15:33:16

>1000

0003１３２人目の素数さん

2006/02/25(土) 16:41:09

このスレ

　～～～終了～～～

0004１３２人目の素数さん

2006/02/25(土) 17:25:55

3:１３２人目の素数さん :2006/02/25(土) 16:41:09
このスレ

　～～～終了～～～

0005( ^ω^)

2006/02/25(土) 18:34:15

( ^ω^)

0006１３２人目の素数さん

2006/02/25(土) 20:40:13

原始帰納的関数でない帰納的関数の例として作られたけど、
値が急速に増加しちゃうせいで別の意味で有名になった関数。

0007１３２人目の素数さん

2006/02/25(土) 21:29:12

これ計算させられた記憶があるな。

0008１３２人目の素数さん

2006/02/26(日) 00:15:18

コレをPCで計算するとあっという間にスタックオーバーフローを起こすな。

0009１３２人目の素数さん

2006/02/26(日) 00:42:38

>>6
それじゃmod2でもしておけば良かったのかね

0010１３２人目の素数さん

2006/02/26(日) 00:48:49

xyzzy で試してみた

(defun ack (x y)
(cond ((zerop x) (1+ y))
((zerop y) (ack (1- x) 1))
(t (ack (1- x) (ack x (1- y))))))

(ack 4 1)

...バイトコンパイルしたのに一分待っても答えが返ってこねえ
ちなみに答えはたぶん 65533

0011１３２人目の素数さん

2006/02/26(日) 00:51:55

>>9
いや、それだと原始帰納
第一引数が小さいところを除いて全部奇数だから

0012１３２人目の素数さん

2006/02/27(月) 05:52:18

ヤッタ－マン

0013１３２人目の素数さん

2006/02/27(月) 15:49:27

ん？ノルディック複合の選手？

0014１３２人目の素数さん

2006/02/27(月) 19:14:52

疑問点：
　計算が出来ないというのに答えがなぜわかるの？

　帰納的ではない関数というけど、どういうこと、ぜんぜん判らない。
プログラムに出来るものは、帰納関数だということを聞いた覚えがあるのに。

0015１３２人目の素数さん

2006/02/27(月) 22:02:37

原始帰納じゃない関数だけど、帰納関数でしょ、アッカーマン関数。
ネット上に原始帰納じゃないけど帰納であることの証明載ってるところないかしら。

0016１３２人目の素数さん

2006/02/27(月) 22:21:32

>>15
あったよ
ttp://www.dumbo.ai.kyutech.ac.jp/hirata/lecture/computation/recursive_main.pdf

0017１３２人目の素数さん

2006/02/27(月) 22:44:11

>>16 ありがとうございます。
さっそく読んでみます。