2進数を4進数ではさむ

有限長さの自然数列を1つの自然数に突っこむ計算をします。

1. 具体的に計算してみる

例として、
a_{1} = 7, a_{2} = 5, a_{3} = 2
を考えてみます。

1-1. よく見るゲーデル数化の方法

素因数分解を用いた有名なゲーデル数化の場合、

2^{7} × 3^{5} × 5^{2} = 777600

となります。

1-2. 2進数を4進数ではさむ方法

この記事のテーマです。
次のような計算を行います*1。
(1) 数列の各数を2進数にする
(2) 2 \, [3番目] \, 2 \, [2番目] \, 2 \, [1番目] \, 2
    というように、2進数化した各数を2で挟む
(3) 全体を4進数として計算する

上記の例の場合、
a_{1} = 111 (2進数)
a_{2} = 101 (2進数)
a_{3} = 10 (2進数)

であるので、
210210121112(4進数)=9586262(10進数)
となります。

 

2. 増加具合を見てみる

この2つの方法の、関数としての増加具合を考えてみたいと思います。問題を簡略化するため、扱う数列を a_{1}=x, a_{2}=yの2つとします。

なんとなく、素因数分解作戦を f_{1}(x, y)、4進数作戦を f_{2}(x, y)としておきます。

2-1. よく見るゲーデル数化の方法

f_{1}(x, y)=2^{x} × 3^{y}
となるので、
2^{x + y} \lt f_{1}(x, y)
であることを考えると、だいたい指数関数くらいの増え方をするんだろうなということが分かります。

 

2-2. 2進数を4進数ではさむ方法

まず xの2進数表記は、小数点以下を切り捨てる関数 \lfloor n\rfloorを用いて、 \lfloor log_2(x)\rfloor + 1 桁になります。
（同様に、 yの2進数表記は \lfloor log_2(y)\rfloor + 1 桁となります）

したがって、
f_{2}(x, y) を4進数で表記したときの桁数は、
(\lfloor log_2(x)\rfloor + 1) + (\lfloor log_2(y)\rfloor + 1)+3
= \lfloor log_2(x)\rfloor + \lfloor log_2(y)\rfloor + 5
くらいになるでしょうか。

ここで、 23333…3 という N 桁の4進数は、10進数に直すと
3×4^{N-1} - 1
くらいになることを考えると、
f_{2}(x, y) \lt  3×4^{\lfloor log_2(x)\rfloor + \lfloor log_2(y)\rfloor + 4}-1
\leqq 3×4^{log_2(x) + log_2(y) + 4}-1
= 3×4^{log_2(x×y×16)}-1
= 3×2^{log_2(x×y×16)}×2^{log_2(x×y×16)}-1
くらいの関数であることが分かります。

 

3. まとめ

以上から分かることは、
フルの指数関数ではなく、肩が対数となるような増加度の指数関数を使ってどうにかこうにかすれば、有限数列が表現できる
ということです。

そのため、
・ x \# y = 2^{\lfloor log_2(x)\rfloor + \lfloor log_2(y)\rfloor} という関数を使用可能とする
・通常の指数関数の使用に一部制限を加える
ような縛りプレイをしたとしても、有限数列を自然数に突っこむことが可能となります。

この x \# y という関数は、ネルソンのスマッシュ関数と呼ばれ、証明力の弱い自然数のシステムでメタ数学的議論をするために使用されているようです*2。

 

*1:E. Nelson, Predicative Arithmetic, Princeton University Press, 1986.

*2:Buss, S. "Nelson's Work on Logic and Foundations and Other Reflections on Foundations of Mathematics" In Diffusion, Quantum Theory, and Radically Elementary Mathematics, edited by W. Faris, Princeton University Press, Princeton and Oxford, 2006, pp.183-208.