computeralgebra https://blog.hatena.ne.jp/computeralgebra/ 非専門的シンギュラリティー研究所 https://computeralgebra.hatenablog.com/ アッカーマン関数 関数の再帰的定義 ここではある形の関数の再帰的定義について考えます。 に対して を と定義します。、 とおきます。、 とおくと は を満たす最小の集合となります。 に対して と定義します。 とおくと が成り立つので、自然数の性質より となります。計算可能性の議論にはこれだけでも良いとは思うのですが によって関数 を定義するには、任意の と任意の に対して かつ ならば が成り立つ必要があります。以下でこれを示します。 となるので となります。 とすると なので となります。よって となります。よって のときには成り立ちます。次に のときには成り立つと仮定します。 とします。、 とおくと となり… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fcomputeralgebra.hatenablog.com%2Fentry%2F2022%2F06%2F01%2F201840" title="アッカーマン関数(3) - 非専門的シンギュラリティー研究所" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://m.media-amazon.com/images/I/41Ksz3r9-oL._SL500_.jpg Hatena Blog https://hatena.blog 2022-06-01 20:18:40 rich https://computeralgebra.hatenablog.com/entry/2022/06/01/201840 1.0 100%