1 :
非決定性名無しさん:
アッカーマン関数の計算論的意味に驚きますた。
2 :
非決定性名無しさん:02/04/10 07:52
int A(int x, int y)
{
if (x == 0)
return y + 1;
if (y == 0)
return A(x - 1, 1);
return A(x - 1, A(x, y - 1));
}
int main()
{
printf("A(3, 3) = %d\n", A(3, 3));
return 0;
}
3 :
非決定性名無しさん:02/04/10 07:53
↑の本でアッカーマン関数を知ったときは、意味あんのかよと思いました。
後に計算可能性の本を眺めていたら、帰納的関数ではないけど計算可能であ
ることを簡単に証明できると言っていてふーんって感じですた。
激しくイタチ害!!
6 :
非決定性名無しさん:02/04/10 15:01
>5 激しくイタチ害!!
情報システムって、もともとこういう、帰納的関数とか、λ算法とか、数理論理学とか、そういうこと煽るための板だよな。
情報システムにコンピュータ企業用のスレの話がでてくるほうがイタチ害なんじゃないのかな。
ま、企業のスレできても、そこで情報システムについて煽ってれば許せるけど、
「XX部のYYは逝ってよし」とかいう話のどこか情報システムなんだか。
とかいってるこの煽りが一番イタチ害か。「俺もナー」だな。スマソ。
>>5は車に轢かれたイタチに謝るべきだと思います!
8 :
非決定性名無しさん:02/04/10 19:45
廣瀬健『帰納的関数』共立出版
再版キボンヌ
9 :
非決定性名無しさん:02/04/10 21:28
グラハム数もアッカーマン関数がらみだよね?
聞きかじりでスマソ
10 :
非決定性名無しさん:02/04/11 20:34
学術スレあげ
11 :
他称キティー:02/04/12 00:32
勝手にアゲるな!!!
てか
∧∧ ミ _ ドスッ
( ,,)┌─┴┴─┐
/' つ 終了 │
〜′ /´ └─┬┬─┘
∪ ∪ ││ _ε3
゛゛'゛'゛
。
12 :
怪人アッカーマン:02/04/12 11:11
某大学工学部(電気情報系)一年次の宿題で、アッカーマン関数が任意の非負
整数の組に対して定義されることの証明がでました。できませんでした。
帰納法を2重に使うなんて高度なことはちょっと…
13 :
怪人アッカーマン:02/04/12 11:16
>>4 いや、アッカーマン関数は原始帰納的ではありませんが、帰納的関数の
仲間(=チューリングマシンで計算できる)にはなっていますよ。
14 :
非決定性名無しさん:02/04/13 00:18
数学は基礎だね
15 :
非決定性名無しさん:02/04/13 02:07
アッカーマン(・∀・)イイ!!
他称キティー(・A・)イクナイ!!
16 :
非決定性名無しさん:02/04/13 04:53
ベッセル関数のほうがいいのでは?
17 :
非決定性名無しさん:02/04/18 13:21
18 :
非決定性名無しさん:02/04/21 21:09
再起呼び出しとは違うものなの?
19 :
非決定性名無しさん:02/04/24 01:16
20 :
非決定性名無しさん:02/04/24 23:26
再帰呼び出しと帰納的関数は別物だろう。
21 :
非決定性名無しさん:02/04/26 23:35
似てる
22 :
非決定性名無しさん:02/04/29 00:28
質問
再帰関数と帰納的関数の違いはなんですか?
23 :
非決定性名無しさん:02/05/04 04:27
>>22 日本語訳が悪いんだと思う。英語ではどっちも recursive functionだよ。
ちなみに、帰納的関数というときは、数学的関数(partial recursive functionとかね)
のことを指していて、再帰関数というときは、プログラムのことを指すと思う。
24 :
非決定性名無しさん:02/05/04 14:28
普通、帰納はinduction、再帰はrecursionの訳語だよね。
帰納的関数はpremitive recursive functionだったよね。
本当なら原始再帰的関数とでも訳出すべきだったのかもね。
inductionってdeductionの対語でもある事だし。
25 :
非決定性名無しさん:02/05/04 23:36
それでは、英語圏ではinductionとrecursionは別物なのですか?
26 :
非決定性名無しさん:02/05/05 00:03
>>24 原始帰納的関数と帰納的関数は別物だよ。
手元の本だと,帰納的関数は原始-にμ演算を付加した物みたい
27 :
非決定性名無しさん:02/05/06 23:04
不完全性定理と帰納的関数の関係を俺様に教えろ下さい
>>26 そうそう。
ただ、premitive recursive functionにμ-recursionを加えたものは、
partial recursive functionと呼び、partial recursive functionのうちで
totalなものをrecursive functionっていう。
>>25 普通、inductionは数学的帰納法のことを指して、recursionは再帰の
ことを指す。
30 :
非決定性名無しさん:02/05/08 07:09
|
|_∧ / ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄
|д`) < (((( ;゚Д゚)))ガクガクブルブル
⊂ ノ \__________________________
|
|
|
|
|彡 サッ
|
|
|
計算理論つう科目の試験で
modの演算が原始機能的であることを証明しろって問題が
全くできなかった。アッカーマン数の問題が出ないなんて・・・。
最履修なのに・・・・鬱
原始機能的→原始帰納的
33 :
非決定性名無しさん:02/08/30 12:24
カコイイ!!!
34 :
非決定性名無しさん:03/02/22 10:25
int fibonacci(int n)
{
if (n > 1)
return fibonacci(n-1) + fibonacci(n-2);
return 1;
}
35 :
非決定性名無しさん:03/02/26 19:57
36 :
非決定性名無しさん:03/12/10 21:41
学術スレage
37 :
非決定性名無しさん:04/01/02 20:18
学術スレage
38 :
非決定性名無しさん:04/01/03 11:35
学術スレage
39 :
非決定性名無しさん:04/01/08 00:17
学問上げ
40 :
非決定性名無しさん:04/05/14 08:18
premitive->primitive
41 :
非決定性名無しさん:04/05/16 13:04
なんでしょう?
42 :
非決定性名無しさん:04/05/22 22:06
学術スレage
43 :
非決定性名無しさん:04/06/23 21:30
ジョン・健・ヌッツォ
44 :
非決定性名無しさん:04/07/29 00:19
久々に学問上げ
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
327 :
非決定性名無しさん:04/08/11 11:42
必死にsageてるのでageてみる
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage
sage