2022-05-25

アッカーマン関数(2)

ハイパー演算子

『計算論計算可能性とラムダ計算 (コンピュータサイエンス大学講座)』の「問 1.3.17 (4)」が簡単にはできそうにないので、まず『コンピュータと数学 (現代基礎数学)』の第5章を見ていきます。第5章では「ハイパー演算子」(wikipedia:ハイパー演算子と同様ですが記法は異なります)から関数族の階層を定義しています。この階層は「グジェゴルチク階層」(wikipedia:グジェゴルチク階層、『数学基礎論の応用』*1参照)と同様のものと考えられます(定義は異なります)。この階層から「問 1.3.17 (4)」が得られると考えられます。

定義 5.2.1 自然数 $j$ に対して $h_j: \mathbb{N} \to \mathbb{N}$ を
$\begin{cases} h_0(x) = \mathrm{suc}(x) \\ h_{j+1}(x) = h_j^*(x, x) = h_j^x(x) \\ \end{cases}$
と定義します。ここで
$\mathrm{suc}(x) = x + 1$
$h_j^*(n, x) = h_j^n(x) = \underbrace{h_j(h_j(\cdots(h_j(}_{n 回}x))\cdots))$
を表しています。

補題 5.2.2 任意の自然数 $j, k, x$ に対して

$0 < x$ のとき $h_j^k(x) < h_j^{k+1}(x)$
$h_j^k(x) < h_j^{k}(x+1)$
$0 < x$ のとき $h_j^k(x) \le h_{j+1}^{k}(x)$
$h_j^{kx}(x) \le h_{j+1}^{k}(x)$

が成り立ちます。以下でこれを示します。

(1) $0 < x$ のとき $h_j^k(x) < h_j^{k+1}(x)$

「 $0 < x$ のとき $x < h_j(x)$ 」 (*)ならば主張が成り立ちます。

$j = 0$ のとき $h_0(x) = \mathrm{suc}(x) > x$ なので成り立っています。

$j$ のときに成り立つ(すなわち $x < h_j(x)$ )と仮定すると $x < h_j(x) < h_j^2(x) < h_j^3(x) < \cdots$ となるので
$x < h_j(x) < h_j^2(x) < \cdots < h_j^x(x) = h_{j+1}(x)$
となります。 $0 < x$ なので $x < h_{j+1}(x)$ となって $j + 1$ のときにも成り立ちます。

よって帰納法により(*)が成り立ちます。

(2) $h_j^k(x) < h_j^{k}(x+1)$

$h_0^k(x) = \mathrm{suc}^k(x) = x + k < (x + 1) + k = \mathrm{suc}^{k}(x+1) = h_0^{k}(x+1)$
となるので $j = 0$ のとき成り立ちます。

$h_j^k(x) < h_j^{k}(x+1)$ と仮定すると
$h_{j+1}(x) = h_j^x(x) < h_j^{x}(x+1) < h_j^{x+1}(x+1) = h_{j+1}(x+1)$
となります。よって任意の $x, y$ に対して $x < y$ ならば $h_{j+1}(x) < h_{j+1}(y)$ が成り立ちます。

$h_{j+1}^n(x) < h_{j+1}^n(y)$ と仮定すると $h_{j+1}^{n+1}(x) < h_{j+1}^{n+1}(y)$ が成り立つので任意の $n$ に対して $h_{j+1}^n(x) < h_{j+1}^n(y)$ となります。よって $h_{j+1}^k(x) < h_{j+1}^{k}(x+1)$ となって $j + 1$ のときも成り立ちます。

よって帰納法により主張が成り立ちます。

(3) $0 < x$ のとき $h_j^k(x) \le h_{j+1}^{k}(x)$

(1)より $x < h_j(x) < h_j^2(x) < \cdots < h_j^x(x) = h_{j+1}(x)$
であり $k = 0$ のときは成り立ちます。

$0 < h_j^k(x) \le h_{j+1}^{k}(x)$ と仮定すると $k = 0$ の結果と(2)から
$h_j^{k+1}(x) = h_j(h_j^k(x)) \le h_j(h_{j+1}^{k}(x)) \le h_{j+1}(h_{j+1}^{k}(x)) = h_{j+1}^{k+1}(x)$
となって $k + 1$ のときも成り立ちます。

よって帰納法により主張が成り立ちます。

(4) $h_j^{kx}(x) \le h_{j+1}^{k}(x)$

$k = 0$ のときは明らかに成り立ちます。

$x \le y \le z$ のとき(2)と(1)から
$h_j^{x}(y) \le h_j^{x}(z) \le h_{j}^z(z) = h_{j+1}(z)$
が成り立ちます。

$h_j^{kx}(x) \le h_{j+1}^{k}(x)$ と仮定します。
$h_j^{(k+1)x}(x) = h_j^{x}(h_j^{kx}(x)) \le h_{j+1}(h_{j+1}^{k}(x)) = h_{j+1}^{k+1}(x)$
となって $k + 1$ のときも成り立ち、帰納法により主張が成り立ちます。

計算論計算可能性とラムダ計算 (コンピュータサイエンス大学講座)

作者:高橋正子
近代科学社

Amazon

コンピュータと数学 (現代基礎数学)

作者:高橋正子
朝倉書店

Amazon

*1:数学基礎論の応用 (日本評論社): 1981｜書誌詳細｜国立国会図書館サーチ

2022-05-15

アッカーマン関数(1)

アッカーマン関数

アッカーマン関数についても調査します。

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

$f(x, y)$ を $\widehat{f}(x)(y)$
$\widehat{f}(x_1) ( \widehat{f}(x_2) ( \cdots \widehat{f}(x_n) (y) \cdots ))$ をかっこを省略して $\widehat{f}(x_1) \widehat{f}(x_2) \cdots \widehat{f}(x_n) (y)$
$\underbrace {\widehat{f}(x) \cdots \widehat{f}(x)} _{n \ 個} (y)$ を $\widehat{f}(x)^n(y)$

と書くことにするとアッカーマン関数の定義は
\begin{cases}
\widehat{f}(0)(y) & = & y + 1 & (a1') \\
\widehat{f}(x + 1)(0) & = & \widehat{f}(x)(1) & (a2') \\
\widehat{f}(x + 1)(y + 1) & = & \widehat{f}(x) \widehat{f}(x + 1)(y) & (a3') \\
\end{cases}
となります。
\begin{eqnarray*}
f(x, y) & = & \widehat{f}(x)(y) \\
& \underset{(a3')}{=} & \widehat{f}(x-1) \widehat{f}(x) (y-1) \\
& \underset{(a3')}{=} & \widehat{f}(x-1)^2 \widehat{f}(x) (y-2) \\
& \vdots & \\
& \underset{(a3')}{=} & \widehat{f}(x-1)^y \widehat{f}(x) (0) \\
& \underset{(a2')}{=} & \widehat{f}(x-1)^y \widehat{f}(x-1) (1) \\
& = & \widehat{f}(x-1)^{y+1} (1) \\
\end{eqnarray*}
が成り立ちます。(a4')

アッカーマン関数は原始帰納的関数ではない帰納的関数であるということの証明が計算論計算可能性とラムダ計算 (コンピュータサイエンス大学講座)の問題にあるのでそれを見ていきます。

まず $f(1, y)$ 、 $f(2, y)$ 、 $f(3, y)$ 、 $f(4, y)$ がどうなるか調べます。

$f(1, y)$

$\widehat{f}(0)(y) = y + 1$ を $n$ 回繰り返すと
$\widehat{f}(0)^n (y) = y + \underbrace {1+\cdots +1} _{n \ 個} = y + n$
となります。よって
$\widehat{f}(1)(y) = \widehat{f}(0)^{y+1} (1) = 1 + (y + 1) = y + 2$

$f(2, y)$

$\widehat{f}(1)(y) = y + 2$ を $n$ 回繰り返すと
$\widehat{f}(1)^n (y) = y + \underbrace {2+\cdots +2} _{n \ 個} = y + 2n$
となります。よって
$\widehat{f}(2)(y) = \widehat{f}(1)^{y+1} (1) = 1 + 2(y + 1) = 2y + 3$

$f(3, y)$

$\widehat{f}(2)(y) + 3 = 2(y + 3)$ となるので、これを $n$ 回繰り返すと
$\widehat{f}(2)^n(y) = (y + 3) \cdot \underbrace {2 \cdot \cdots \cdot 2} _{n \ 個} - 3 = 2^n(y + 3) - 3$
となります。よって
$\widehat{f}(3)(y) = \widehat{f}(2)^{y+1} (1) = 2^{y+1}(1 + 3) - 3 = 2^{y+3} - 3$

$f(4, y)$

$a^b$ を $a \wedge b$ と書くと、 $\widehat{f}(3)(y) + 3 = 2^{y + 3} = 2 \wedge (y + 3)$ となります。これを $n$ 回繰り返すと
$\widehat{f}(3)^n(y) = \underbrace {2 \wedge ( \cdots \wedge (2} _{n \ 個} \wedge (y + 3)) \cdots ) - 3$
このかっこは省略することにします。
$\widehat{f}(3)^n(y) = \underbrace {2 \wedge \cdots \wedge 2} _{n \ 個} \wedge (y + 3) - 3$
$\underbrace {a \wedge \cdots \wedge a} _{b \ 個}$ を $a \barwedge b$ と書くことにすると
$\widehat{f}(4)(y) = \widehat{f}(3)^{y+1} (1) = \underbrace {2 \wedge \cdots \wedge 2} _{y+1 \ 個} \wedge (1 + 3) - 3 = 2 \barwedge (y+3) - 3$

問 1.3.17 について考えます。

(1) $x + y + 1 \le f(x, y)$

$x = 0$ のとき

$f(0, y) \underset{(a1)}{=} y + 1 = x + y + 1$

$x - 1$ のとき成り立つ(1-1)として $x \ (\ge 1)$ のとき

$y = 0$ のとき

$f(x, 0) \underset{(a2)}{=} f(x-1, 1) \underset{(1-1)}{\ge} (x-1) + 1 + 1 = x + y + 1$

$y - 1$ のとき成り立つ(1-2)として $y \ (\ge 1)$ のとき

$\begin{eqnarray*} f(x, y) & \underset{(a3)}{=} & f(x-1, f(x, y-1)) \\ & \underset{(1-1)}{\ge} & (x-1) + f(x, y-1) + 1 \\ & \underset{(1-2)}{\ge} & (x-1) + (x + (y-1) + 1) + 1 \\ & = & 2x + y \ge x + y + 1 \end{eqnarray*}$

(2) $f(x, y) < f(x, y+1) \le f(x + 1, y)$

(2-1) $f(x, y) < f(x, y+1)$

$x = 0$ のとき

$f(0, y) \underset{(a1)}{=} y + 1 < y + 2 \underset{(a1)}{=} f(0, y + 1)$

$x \ \ge 1$ のとき

$\begin{eqnarray*} f(x, y+1) & \underset{(a3)}{=} & f(x-1, f(x, y)) \\ & \underset{(1)}{\ge} & (x-1) + f(x, y) + 1 \\ & = & x + f(x, y) > f(x, y) \end{eqnarray*}$

(2-2) $f(x, y+1) \le f(x + 1, y)$

$x = 0$ のとき

$f(x, y+1) = f(0, y+1) \underset{(a1)}{=} y + 2 = f(1, y) = f(x+1, y)$

$y = 0$ のとき

$f(x, y+1) = f(x, 1) \underset{(a2)}{=} f(x+1, 0) = f(x+1, y)$

$x, y \ge 1$ のとき

$f(x+1, y-1) \underset{(1)}{\ge} (x+1) + (y-1) + 1 = x + y + 1$
よって
$f(x+1, y) \underset{(a3)}{=} f(x, f(x+1, y-1)) \underset{(2-1)}{>} f(x, y+1)$

(3) 任意の $a, b \ge 0$ に対して $f(a, f(b, y)) < f(c, y)$ ( $\forall y \in \mathbb{N}$ )を満たす $c \ge 0$ がある

$b = 0$ のとき

$f(a, f(0, y)) \underset{(a1)}{=} f(a, y + 1) \underset{(2-2)}{\le} f(a + 1, y) \underset{(2)}{<} f(a + 2, y)$

$b$ のとき成り立つ(3-1)と仮定して $b + 1$ のとき

$y = 0$ のとき

$f(a, f(b+1, 0)) \underset{(a2)}{=} f(a, f(b, 1)) \underset{(3-1)}{<} f(c, 1) \underset{(a2)}{=} f(c+1, 0)$
を満たす $c$ が存在します。

$y$ のとき成り立つ(3-2)と仮定して $y + 1$ のとき

$f(a, f(b+1, y+1)) \underset{(a3)}{=} f(a, f(b, f(b+1, y))) \underset{(3-1)}{<} f(c, f(b+1, y)) \underset{(3-2)}{<} f(c', y)$
を満たす $c, c'$ が存在します。

計算論計算可能性とラムダ計算 (コンピュータサイエンス大学講座)

作者:高橋正子
近代科学社

Amazon

2022-05-10

たらい回し関数(6)

たらい回し関数

while の繰り返しが2回以下であることを考えると、以下のように書き直すことができます。これを見ると a2 と c2 は計算する必要がありません。

        public static string Test()
        {
            int count = 0;
            int depth = 0;
            float tarai(float x, float y, float z, int d)
            {
                count++;
                d++;
                depth = d > depth ? d : depth;
                if (x <= y)
                {
                    return y;
                }
                else
                {
                    float a = tarai(x - 1, y, z, d);
                    float b = tarai(y - 1, z, x, d);
                    float c = tarai(z - 1, x, y, d);
                    (x, y, z) = (a, b, c);
                    count++;
                    d++;
                    depth = d > depth ? d : depth;
                    if (x <= y)
                    {
                        return y;
                    }
                    else
                    {
                        float a2 = tarai(x - 1, y, z, d);
                        float b2 = tarai(y - 1, z, x, d);
                        float c2 = tarai(z - 1, x, y, d);
                        (x, y, z) = (a2, b2, c2);
                        count++;
                        d++;
                        depth = d > depth ? d : depth;
                        return y;
                    }
                }
            }
            return $"{tarai(12, 6, 0, 0)}, count = {count}, depth = {depth}";
        }

2022-05-08

たらい回し関数(5)

たらい回し関数

たらい回し関数についてはクロージャーの説明には使えそうにないので変数を使わないように書き直す意味はあまりないとは思いますが、やってみます。

たらい回し関数をできるだけ変数を使わないように書き直します。このために前回「呼び出しの深さ」について考えました。「呼び出しの深さ」別に tarai_0、tarai_1、tarai_2 のように関数を作っていきます。以下では「呼び出しの深さ」2 でかなり複雑になるので以下の関数では 2 までしかありません.が、これが無限に続くと考えると擬似的に無限の場合を表しています。

C# ではあまりうまく書くことができないのでわかりにくいですし、「呼び出しの深さ」2 までしかないので「幅」0 の場合しか計算できません(これはあまり意味がありません)。これが続いていくことを想像できるようコードを掲載します。

        public static string Test()
        {
            float tarai_0(float x, float y, float z)
            {
                return (x <= y ?
                        y :
                        0);
            }
            float tarai_1(float x, float y, float z)
            {
                return (x <= y ?
                        y :
                        ((x - 1 <= y ?
                            y :
                            0) <= (y - 1 <= z ?
                            z :
                            0) ?
                            (y - 1 <= z ?
                                z :
                                0) :
                            0));
            }
            float tarai_2(float x, float y, float z)
            {
                return (x <= y ?
                        y :
                        ((x - 1 <= y ?
                            y :
                            ((x - 1 - 1 <= y ?
                                y :
                                0) <= (y - 1 <= z ?
                                z :
                                0) ?
                                (y - 1 <= z ?
                                    z :
                                    0) :
                                0)) <= (y - 1 <= z ?
                            z :
                            ((y - 1 - 1 <= z ?
                                z :
                                0) <= (z - 1 <= x ?
                                x :
                                0) ?
                                (z - 1 <= x ?
                                    x :
                                    0) :
                                0)) ?
                            (y - 1 <= z ?
                                z :
                                ((y - 1 - 1 <= z ?
                                    z :
                                    0) <= (z - 1 <= x ?
                                    x :
                                    0) ?
                                    (z - 1 <= x ?
                                        x :
                                        0) :
                                    0)) :
                            (((x - 1 <= y ?
                                y :
                                ((x - 1 - 1 <= y ?
                                    y :
                                    0) <= (y - 1 <= z ?
                                    z :
                                    0) ?
                                    (y - 1 <= z ?
                                        z :
                                        0) :
                                    0)) - 1 <= (y - 1 <= z ?
                                z :
                                ((y - 1 - 1 <= z ?
                                    z :
                                    0) <= (z - 1 <= x ?
                                    x :
                                    0) ?
                                    (z - 1 <= x ?
                                        x :
                                        0) :
                                    0)) ?
                                (y - 1 <= z ?
                                    z :
                                    ((y - 1 - 1 <= z ?
                                        z :
                                        0) <= (z - 1 <= x ?
                                        x :
                                        0) ?
                                        (z - 1 <= x ?
                                            x :
                                            0) :
                                        0)) :
                                0) <= ((y - 1 <= z ?
                                z :
                                ((y - 1 - 1 <= z ?
                                    z :
                                    0) <= (z - 1 <= x ?
                                    x :
                                    0) ?
                                    (z - 1 <= x ?
                                        x :
                                        0) :
                                    0)) - 1 <= (z - 1 <= x ?
                                x :
                                ((z - 1 - 1 <= x ?
                                    x :
                                    0) <= (x - 1 <= y ?
                                    y :
                                    0) ?
                                    (x - 1 <= y ?
                                        y :
                                        0) :
                                    0)) ?
                                (z - 1 <= x ?
                                    x :
                                    ((z - 1 - 1 <= x ?
                                        x :
                                        0) <= (x - 1 <= y ?
                                        y :
                                        0) ?
                                        (x - 1 <= y ?
                                            y :
                                            0) :
                                        0)) :
                                0) ?
                                ((y - 1 <= z ?
                                    z :
                                    ((y - 1 - 1 <= z ?
                                        z :
                                        0) <= (z - 1 <= x ?
                                        x :
                                        0) ?
                                        (z - 1 <= x ?
                                            x :
                                            0) :
                                        0)) - 1 <= (z - 1 <= x ?
                                    x :
                                    ((z - 1 - 1 <= x ?
                                        x :
                                        0) <= (x - 1 <= y ?
                                        y :
                                        0) ?
                                        (x - 1 <= y ?
                                            y :
                                            0) :
                                        0)) ?
                                    (z - 1 <= x ?
                                        x :
                                        ((z - 1 - 1 <= x ?
                                            x :
                                            0) <= (x - 1 <= y ?
                                            y :
                                            0) ?
                                            (x - 1 <= y ?
                                                y :
                                                0) :
                                            0)) :
                                    0) :
                                0)));
            }
            int diff(float x, float y)
            {
                if (x <= y)
                {
                    return 0;
                }
                else
                {
                    return (int)Math.Ceiling(x - y);
                }
            }
            int dist(float x, float y, float z)
            {
                float m = Math.Min(Math.Min(x, y), z);
                return diff(x, m) + diff(y, m) + diff(z, m);
            }
            float tarai(float x, float y, float z)
            {
                switch (dist(x, y, z) * 3 + 1)
                {
                    case 0:
                        return tarai_0(x, y, z);
                    case 1:
                        return tarai_1(x, y, z);
                    case 2:
                        return tarai_2(x, y, z);
                }
                return -1;
            }
            return tarai(0, 0, 0).ToString();
        }

このように x、y、z 以外の変数を使わないように書き直すことができました。

2022-05-07

たらい回し関数(4)

たらい回し関数

たらい回し関数(以下の $t$ または tarai)の呼び出しが重なっている(呼び出しが終了する前に呼び出しが行われる)回数の最大値を「呼び出しの深さ」と呼ぶことにします(以下の depth)。

        public static string Test()
        {
            int count = 0;
            int depth = 0;
            float tarai(float x, float y, float z, int d)
            {
                count++;
                depth = d + 1 > depth ? d + 1 : depth;
                if (x <= y)
                {
                    return y;
                }
                else
                {
                    return tarai(tarai(x - 1, y, z, d + 1), tarai(y - 1, z, x, d + 1), tarai(z - 1, x, y, d + 1), d + 1);
                }
            }
            return $"{tarai(12, 6, 0, 0)}, count = {count}, depth = {depth}";
        }

$\mathbb{R}$ を実数全体の集合、 $\mathbb{N}$ を自然数(負ではない整数)全体の集合)とします。 $x, y \in \mathbb{R}$ に対して $x \setminus y = \min\{m \in \mathbb{N} \mid x-m \leq y\}$ とおきます。 $x, y, z \in \mathbb{R}$ に対して $x, y, z$ の「幅」 $\delta(x, y, z)$ を $\delta(x, y, z) = (x \setminus \min \{ x, y, z \}) + (y \setminus \min \{ x, y, z \}) + (z \setminus \min \{ x, y, z \})$ と定義します。 $x, y, z$ の「幅」と「呼び出し深さ」(depth)、「呼び出しの回数」(count)の関係を考えます。

上記の C# のコードを while を使って書き直します。

        public static string Test()
        {
            int count = 0;
            int depth = 0;
            float tarai(float x, float y, float z, int d)
            {
                count++;
                d++;
                depth = d > depth ? d : depth;
                while (x > y)
                {
                    float a = tarai(x - 1, y, z, d);
                    float b = tarai(y - 1, z, x, d);
                    float c = tarai(z - 1, x, y, d);
                    (x, y, z) = (a, b, c);
                    count++;
                    d++;
                    depth = d > depth ? d : depth;
                }
                return y;
            }
            return $"{tarai(12, 6, 0, 0)}, count = {count}, depth = {depth}";
        }

while の中の繰り返しの回数を考えます。

$x > y$ とします。

「幅」が $\delta(x, y, z) - 1$ 以下のときの「呼び出しの深さ」は $d$ 以下、「呼び出しの回数」は $c$ 以下であるとします。

「幅」が $\delta(x, y, z) - 1$ 以下である $x', y', z'$ に対して
$\begin{eqnarray*} t(x', y', z') & = & \begin{cases} y' & (x' \leq y') \\ z' & (x' > y', & y' \leq z') & \cdots (*)\\ x' & (x' > y', & y' > z') \\ \end{cases} \\ \end{eqnarray*}$
が成り立っているとします。

(1) $t(x-1, y, z) = x - 1$ のとき

(*)より $t(x-1, y, z) = x-1, y, \operatorname{or} z$ で、 $t(x-1, y, z) = x - 1$ となるのは $x -1 > y > z$ の場合となります。このとき
$\begin{eqnarray*} t(y-1, z, x) & = & \begin{cases} z & (y-1 \leq z) \\ x & (y-1 > z, & z \leq x) \\ y-1 & (y-1 > z, & z > x) \\ \end{cases} \\ & = & \begin{cases} z & (y-1 \leq z) \\ x & (y-1 > z) \\ \end{cases} \\ \end{eqnarray*}$
$\begin{eqnarray*} t(z-1, x, y) & = & \begin{cases} x & (z-1 \leq x) \\ y & (z-1 > x, & x \leq y) \\ z-1 & (z-1 > x, & x > y) \\ \end{cases} \\ & = & x \end{eqnarray*}$
となります。よって $t(x-1, y, z) = x - 1$ のとき $t(y-1, z, x)$ 、 $t(z-1, x, y)$ は $x, z$ のどれかとなります。(*)より $t(t(x-1, y, z), t(y-1, z, x), t(z-1, x, y))$ の引数の「呼び出しの深さ」は $d$ 以下、「呼び出しの回数」は $3c$ 以下となります。

(2) $t(y-1, z, x) = y - 1$ のとき

(*)より $t(y-1, z, x) = y-1, z, \operatorname{or} x$ で、 $t(y-1, z, x) = y - 1$ となるのは $y -1 > z > x$ の場合となりますが、 $x > y$ なのでこれは起こりません。

(3) $t(z-1, x, y) = z - 1$ のとき

(*)より $t(z-1, x, y) = z-1, x, \operatorname{or} y$ で、 $t(z-1, x, y) = z - 1$ となるのは $z -1 > x > y$ の場合となります。このとき
$\begin{eqnarray*} t(x-1, y, z) & = & \begin{cases} y & (x-1 \leq y) \\ z & (x-1 > y, & y \leq z) \\ x-1 & (x-1 > y, & y > z) \\ \end{cases} \\ & = & \begin{cases} y & (x-1 \leq y) \\ z & (x-1 > y, & y \leq z) \\ \end{cases} \\ \end{eqnarray*}$
$\begin{eqnarray*} t(y-1, z, x) & = & \begin{cases} z & (y-1 \leq z) \\ x & (y-1 > z, & z \leq x) \\ y-1 & (y-1 > z, & z > x) \\ \end{cases} \\ & = & \begin{cases} z & (y-1 \leq z) \\ x & (y-1 > z, & z \leq x) \\ \end{cases} \\ \end{eqnarray*}$
となります。よって $t(z-1, x, y) = z - 1$ のとき $t(y-1, z, x)$ 、 $t(z-1, x, y)$ は $x, y, z$ のどれかとなります。(*)より $t(t(x-1, y, z), t(y-1, z, x), t(z-1, x, y))$ の引数の「呼び出しの深さ」は $d$ 以下、「呼び出しの回数」は $3c$ 以下となります。

(4) それ以外のとき

(1)(2)(3)以外のとき、 $t(x-1, y, z)$ 、 $t(y-1, z, x)$ 、 $t(z-1, x, y)$ は $x, y, z$ のどれかとなります。
$\begin{eqnarray*} a = t(x-1, y, z) & = & \begin{cases} y & (x-1 \leq y, & x > y) \\ z & (x-1 > y, & y \leq z, & x > y) \\ \end{cases} \\ \end{eqnarray*}$
$\begin{eqnarray*} b = t(y-1, z, x) & = & \begin{cases} z & (y-1 \leq z, & x > y) \\ x & (y-1 > z, & z \leq x, & x > y) \\ \end{cases} \\ \end{eqnarray*}$
$\begin{eqnarray*} c = t(z-1, x, y) & = & \begin{cases} x & (z-1 \leq x, & x > y) \\ \end{cases} \\ \end{eqnarray*}$

(4-1) $a = y$ 、 $b = x$ のとき

$a \le b$ となるので $t(a, b, c) = b = x$ となります。

(4-2) $a = z$ 、 $b = z$ のとき

$a \le b$ となるので $t(a, b, c) = b = z$ となります。

(4-3) $a = z$ 、 $b = x$ のとき

$z \le x$ であり、よって $a \le b$ となるので $t(a, b, c) = b = x$ となります。

(4-4) $a = y$ 、 $b = z$ 、 $y \le z$ のとき

$a \le b$ となるので $t(a, b, c) = b = x$ となります。

(4-5) $a = y$ 、 $b = z$ 、 $y > z$ のとき

while の繰り返しを抜けずに次の段階に進むことになります。しかし $x > y > z$ なので次の繰り返しの段階では $a > b$ かつ $b < c$ となり、(4-5)の状態は起こりません。よって繰り返しの回数は最大2回となります。

よって「幅」が $\delta(x, y, z)$ ときの「呼び出しの深さ」は $d + 3$ 以下、「呼び出しの回数」は $6c + 3$ 以下となります。

帰納法によって「幅」が $\delta(x, y, z)$ ときの「呼び出しの深さ」は $3 \delta(x, y, z) + 1$ 以下、「呼び出しの回数」は $\frac{8}{5} \cdot 6^{\delta(x, y, z)} - \frac{3}{5}$ 以下となります。

2022-05-06

たらい回し関数(3)

たらい回し関数

(3)の場合を $\delta(x, y, z)$ に関する帰納法の仮定から証明することができます。

(3) $x > y$ かつ $y > z$ ならば $t(x, y, z) = x$

$x - 1 \le y$ のときは定義より $t(x-1, y, z) = y$ 、 $x - 1 > y$ のときは $\delta(x, y, z)$ に関する帰納法の仮定(*)より $t(x-1, y, z)$ は定義されていて
$t(x-1, y, z) = \begin{cases} y & (x-1 \leq y\ のとき) \\ z & (x-1 > y \ かつ \ y \leq z \ のとき) \\ x-1 & (x-1 > y \ かつ \ y > z \ のとき) \\ \end{cases}$
となります。よって
$\begin{eqnarray*} t(x, y, z) & = & t(t(x-1, y, z), t(y-1, z, x), t(z-1, x, y)) \\ & = & \begin{cases} t(y, z, x) & (x - 1 \le y \ かつ \ y - 1 \le z \ のとき) \\ t(y, x, x) & (x - 1 \le y \ かつ \ y - 1 > z \ のとき) \\ t(x-1, z, x) & (x - 1 > y \ かつ \ y - 1 \le z \ のとき) \\ t(x-1, x, x) & (x - 1 > y \ かつ \ y - 1 > z \ のとき) \\ \end{cases} \\ & = & \begin{cases} x & (x - 1 \le y \ かつ \ y - 1 \le z \ のとき) \\ x & (x - 1 \le y \ かつ \ y - 1 > z \ のとき) \\ x & (x - 1 > y \ かつ \ y - 1 \le z \ のとき) \\ x & (x - 1 > y \ かつ \ y - 1 > z \ のとき) \\ \end{cases} \\ & = & x \end{eqnarray*}$

2022-05-03

たらい回し関数(2)

たらい回し関数

前回の説明ではたらい回し関数が「定義されている」とはどういうことなのかという説明が不足していました。たらい回し関数の定義
$\mathrm{tarai}(x,y,z)= \\ \begin{cases} y & (x \leq y \ のとき) \\ \mathrm{tarai}(\mathrm{tarai}(x-1,y,z), \mathrm{tarai}(y-1,z,x), \mathrm{tarai}(z-1,x,y)) & (x > y \ のとき) \\ \end{cases}$
は、以下の関数「tarai」の呼び出し回数(count)が有限(「tarai」が有限時間で終了する)のとき「定義されている」とします。ここで float は(コンピューター上の実数ではなく)数学的な実数と同じものとします。

        public static string Test()
        {
            int count = 0;
            float tarai(float x, float y, float z)
            {
                count++;
                if (x <= y)
                {
                    return y;
                }
                else
                {
                    float a = tarai(x - 1, y, z);
                    float b = tarai(y - 1, z, x);
                    float c = tarai(z - 1, x, y);
                    return tarai(a, b, c);
                }
            }
            return $"{tarai(12, 6, 0)}, count = {count}";
        }

$t(x, y, z) = \begin{cases} y & (x \leq y\ のとき) & (1) \\ t(t(x-1, y, z), t(y-1, z, x), t(z-1, x, y)) & (x > y \ のとき) & (2) \\ \end{cases}$
$t'(x, y, z) = \begin{cases} y & (x \leq y\ のとき) \\ z & (x > y \ かつ \ y \leq z \ のとき) \\ x & (x > y \ かつ \ y > z \ のとき) \\ \end{cases}$
とおきます。

$\mathbb{R}$ を実数全体の集合、 $\mathbb{N}$ を自然数(負ではない整数)全体の集合)とします。任意の $x, y, z \in \mathbb{R}$ に対して $t(x, y, z)$ が(上の意味で)定義されていて、 $t(x, y, z) = t'(x, y, z)$ であることを示します。

$x \setminus y = \min\{m \in \mathbb{N} \mid x-m \leq y\}$ とおきます。

$\delta(x, y, z) = (x \setminus \min \{ x, y, z \}) + (y \setminus \min \{ x, y, z \}) + (z \setminus \min \{ x, y, z \})$ とおいて $\delta(x, y, z)$ に関する帰納法で証明します。 $\delta(x, y, z) = 0$ のときは $x = y = z$ となるので $t(x, y, z) = y = t'(x, y, z)$ が成り立っています。

$\delta(x, y, z) \ge 1$ として $\delta(x, y, z) - 1$ では成り立っていると仮定します。(*)

(1) $x \le y$ ならば $t(x, y, z) = y$

定義の(1)の場合から成り立ちます。

(2) $x > y$ かつ $y \le z$ ならば $t(x, y, z) = z$

定義の(1)の場合から $t(y-1, z, *) = z$ となります。

(2-1) $x - 1 \le y$ のとき

定義の(1)の場合から $t(x-1, y, *) = y$ 、 $t(y, z, *) = z$ となります。よって
$\begin{eqnarray*} t(x, y, z) & = & t(t(x-1, y, z), t(y-1, z, x), t(z-1, x, y)) \\ & = & t(y, z, t(z-1, x, y)) \\ \end{eqnarray*}$
となって、 $z - 1 \le x$ のときは定義の(1)の場合から $t(z-1, x, y) = x$ であり $z - 1 > x$ のときは仮定(*)から $t(z-1, x, y)$ は定義されているので、 $t(y, z, t(z-1, x, y))$ は定義されていて $t(y, z, t(z-1, x, y)) = z$ となります。

(2-2) $x - 1 > y$ かつ $t(x-1, y, z) = z$ のとき

定義の(1)の場合から $t(z, z, *) = z$ となります。よって
$\begin{eqnarray*} t(x, y, z) & = & t(t(x-1, y, z), t(y-1, z, x), t(z-1, x, y)) \\ & = & t(z, z, t(z-1, x, y)) \\ \end{eqnarray*}$
となって、 $z - 1 \le x$ のときは定義の(1)の場合から $t(z-1, x, y) = x$ であり $z - 1 > x$ のときは仮定(*)から $t(z-1, x, y)$ は定義されているので、 $t(y, z, t(z-1, x, y))$ は定義されていて $t(y, z, t(z-1, x, y)) = z$ となります。

(2-3) (2)の証明

$m = x \setminus y$ とおくと $m \ge 1$ となります。(2-1)から $m = 1$ のときは成り立ちます。 $m \ge 2$ として $m - 1$ のとき成り立つと仮定すると(2-2)から $m$ のときも成り立ちます。よって帰納法により(2)が成り立ちます。

(3) $x > y$ かつ $y > z$ ならば $t(x, y, z) = x$

定義の(1)の場合から $t(z-1, x, *) = x$ となります。

(3-1) $y - 1 \le z$ のとき

定義の(1)の場合から $t(y-1, z, *) = z$ となります。

(3-1-1) $x - 1 \le y$ のとき

定義の(1)の場合から $t(x-1, y, *) = y$ となり、(2)から $t(y, z, x) = x$ となります。よって
$\begin{eqnarray*} t(x, y, z) & = & t(t(x-1, y, z), t(y-1, z, x), t(z-1, x, y)) \\ & = & t(y, z, x) \\ & = & x \end{eqnarray*}$

(3-1-2) $x - 1 > y$ かつ $t(x-1, y, z) = x$ のとき

(2)から $t(x, z, x) = x$ となります。よって
$\begin{eqnarray*} t(x, y, z) & = & t(t(x-1, y, z), t(y-1, z, x), t(z-1, x, y)) \\ & = & t(x, z, x) \\ & = & x \end{eqnarray*}$

(3-1-3) (3-1)の証明

$m = x \setminus y$ とおくと $m \ge 1$ となります。(3-1-1)から $m = 1$ のときは成り立ちます。 $m \ge 2$ として $m - 1$ のとき成り立つと仮定すると(3-1-2)から $m$ のときも成り立ちます。よって帰納法により(3-1)が成り立ちます。

(3-2) $y - 1 > z$ のとき

(2)から $t(y-1, z, x) = x$ となります。

(3-2-1) $x - 1 \le y$ のとき

定義の(1)の場合から $t(x-1, y, *) = y$ となり、(2)から $t(y, x, x) = x$ となります。よって
$\begin{eqnarray*} t(x, y, z) & = & t(t(x-1, y, z), t(y-1, z, x), t(z-1, x, y)) \\ & = & t(y, x, x) \\ & = & x \end{eqnarray*}$

(3-2-2) $x - 1 > y$ かつ $t(x-1, y, z) = x$ のとき

定義の(1)の場合から $t(x, x, *) = x$ となります。よって
$\begin{eqnarray*} t(x, y, z) & = & t(t(x-1, y, z), t(y-1, z, x), t(z-1, x, y)) \\ & = & t(x, x, x) \\ & = & x \end{eqnarray*}$

(3-2-3) (3-2)の証明

$m = x \setminus y$ とおくと $m \ge 1$ となります。(3-2-1)から $m = 1$ のときは成り立ちます。 $m \ge 2$ として $m - 1$ のとき成り立つと仮定すると(3-2-2)から $m$ のときも成り立ちます。よって帰納法により(3-2)が成り立ちます。

(3-1)と(3-2)から(3)がわかります。(1)と(2)と(3)から $t(x, y, z) = t'(x, y, z)$ となります。

よって $\delta(x, y, z)$ の場合も成り立ちます。

ハイパー演算子

(1) のとき

(2)

(3) のとき

(4)

(1)

のとき

のとき成り立つ(1-1)として のとき

のとき

のとき成り立つ(1-2)として のとき

(2)

(2-1)

のとき

のとき

(2-2)

のとき

のとき

のとき

(3) 任意の に対して ()を満たす がある

のとき

のとき成り立つ(3-1)と仮定して のとき

のとき

のとき成り立つ(3-2)と仮定して のとき

(1) のとき

(2) のとき

(3) のとき

(4) それ以外のとき

(4-1) 、 のとき

(4-2) 、 のとき

(4-3) 、 のとき

(4-4) 、、 のとき

(4-5) 、、 のとき

(3) かつ ならば

(1) ならば

(2) かつ ならば

(2-1) のとき

(2-2) かつ のとき

(2-3) (2)の証明

(3) かつ ならば

(3-1) のとき

(3-1-1) のとき

(3-1-2) かつ のとき

(3-1-3) (3-1)の証明

(3-2) のとき

(3-2-1) のとき

(3-2-2) かつ のとき

(3-2-3) (3-2)の証明

(1) $0 < x$ のとき $h_j^k(x) < h_j^{k+1}(x)$

(2) $h_j^k(x) < h_j^{k}(x+1)$

(3) $0 < x$ のとき $h_j^k(x) \le h_{j+1}^{k}(x)$

(4) $h_j^{kx}(x) \le h_{j+1}^{k}(x)$

(1) $x + y + 1 \le f(x, y)$

$x = 0$ のとき

$x - 1$ のとき成り立つ(1-1)として $x \ (\ge 1)$ のとき

$y = 0$ のとき

$y - 1$ のとき成り立つ(1-2)として $y \ (\ge 1)$ のとき

(2) $f(x, y) < f(x, y+1) \le f(x + 1, y)$

(2-1) $f(x, y) < f(x, y+1)$

$x = 0$ のとき

$x \ \ge 1$ のとき

(2-2) $f(x, y+1) \le f(x + 1, y)$

$x = 0$ のとき

$y = 0$ のとき

$x, y \ge 1$ のとき

(3) 任意の $a, b \ge 0$ に対して $f(a, f(b, y)) < f(c, y)$ ( $\forall y \in \mathbb{N}$ )を満たす $c \ge 0$ がある

$b = 0$ のとき

$b$ のとき成り立つ(3-1)と仮定して $b + 1$ のとき

$y = 0$ のとき

$y$ のとき成り立つ(3-2)と仮定して $y + 1$ のとき

(1) $t(x-1, y, z) = x - 1$ のとき

(2) $t(y-1, z, x) = y - 1$ のとき

(3) $t(z-1, x, y) = z - 1$ のとき

(4-1) $a = y$ 、 $b = x$ のとき

(4-2) $a = z$ 、 $b = z$ のとき

(4-3) $a = z$ 、 $b = x$ のとき

(4-4) $a = y$ 、 $b = z$ 、 $y \le z$ のとき

(4-5) $a = y$ 、 $b = z$ 、 $y > z$ のとき

(3) $x > y$ かつ $y > z$ ならば $t(x, y, z) = x$

(1) $x \le y$ ならば $t(x, y, z) = y$

(2) $x > y$ かつ $y \le z$ ならば $t(x, y, z) = z$

(2-1) $x - 1 \le y$ のとき

(2-2) $x - 1 > y$ かつ $t(x-1, y, z) = z$ のとき

(3) $x > y$ かつ $y > z$ ならば $t(x, y, z) = x$

(3-1) $y - 1 \le z$ のとき

(3-1-1) $x - 1 \le y$ のとき

(3-1-2) $x - 1 > y$ かつ $t(x-1, y, z) = x$ のとき

(3-2) $y - 1 > z$ のとき

(3-2-1) $x - 1 \le y$ のとき

(3-2-2) $x - 1 > y$ かつ $t(x-1, y, z) = x$ のとき