エレファント・コンピューティング調査報告

極限に関する順序を論理プログラミングの手法を使って指定することを目指すブロクです。

たらい回し関数(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} 以下となります。