関数の再帰的定義 ここではある形の関数の再帰的定義について考えます。 に対して を と定義します。、 とおきます。、 とおくと は を満たす最小の集合となります。 に対して と定義します。 とおくと が成り立つので、自然数の性質より となります。計算可…

ハイパー演算子 『計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)』の「問 1.3.17 (4)」が簡単にはできそうにないので、まず『コンピュータと数学 (現代基礎数学)』の第5章を見ていきます。第5章では「ハイパー演算子」(wikipedia:ハイパ…

アッカーマン関数についても調査します。アッカーマン関数は以下のように非負整数 と に対して帰納的に定義された関数です(wikipedia:アッカーマン関数、計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座) 参照)。 \begin{cases} f(0, y) & =…