球面倶楽部零八式 mark II

クソブログ

タッパーの自己言及式 part 1

数学プログラム

タッパーの自己言及式

http://www.dgp.toronto.edu/people/mooncake/papers/SIGGRAPH2001_Tupper.pdf

とは $\displaystyle\mod \lfloor (\lfloor \frac{y}{17}\rfloor 2^{-17\lfloor x\rfloor-\mod(\lfloor y\rfloor,17)},2)\rfloor$ の $[0,106]\times [k,k+17]$ のグラフを描くとこの式自体が表示されるというものだ。ここで $\lfloor a\rfloor$ は $a$ 以下の最大の整数で日本ではガウス記号 $[a]$ と同じ。 $\mod(a,b)$ は $x$ を $y$ で割ったあまりのこと。

この式を理解するための準備をしておこう。

(1) 2進数 $n$ の $2^k$ の位の数字が0か1かを知る方法

シフト演算子を使いたい所であるが、これを式で表現する。2で割ると1桁右にずれるので、 $2^{k}$ で割った商の $2^{0}$ の位を求めれば良い。つまり

$\mod(\lfloor n\times 2^{-k}\rfloor,2)$

となる。これは0または1の値をとるので、 $\displaystyle\frac{1}{2}$ と比べて、真なら1、偽なら0となる評価を行えば良いので、

$\displaystyle\frac{1}{2} \lt \mod (\lfloor n\times 2^{-k}\rfloor,2 )$

が2進数 $n$ の $2^k$ の位の数字となる。

原論文とは床関数をとる場所が少し違うが、タッパーの自己言及式の本質は、ここにある。

(2)2次元配列と1次元配列の行き来

縦 $a$ 横 $b$ の長方形の中の座標 $(x,y)$ を縦に一列に並べる。

但し座標は $x=0,1,...,b-1$ 及び $y=0,1,...,a-1$ とする。このとき、座標 $(p,q)$ は $ap+q$ 番目にあることになる。

この操作の逆を考える。1次元配列の $n$ 番目(最初は0番目)の要素を縦 $a$ 横 $b$ の長方形に並べるとき、

$\displaystyle\left(\lfloor\frac{n}{a}\rfloor,\mod(n,a)\right)$

という座標に対応する。

2023.12.25追記

言及されたという通知がきました。自己言及式だけに。

taq.hatenadiary.jp