タッパーの自己言及式 part 2 - 球面倶楽部零八式 mark II

では、タッパーの自己言及式を導いてみよう。

縦 $a$ 横 $b$ の長方形のバイナリ画像を縦に1列に並べて2進数で表現したものを $n$ とする。 $n$ から $(p,q)$ の値を復元することを考える。それは、 $2^{ap+q}$ の位の数字を求めれば良いので、

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

つまり

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

となる。しかし、与えるのは $n$ ではなく座標 $(x,y)$ なので、工夫が必要である。そこで、

$x=p,y=q+an$

とおく。これが見事である。すると $\displaystyle n=\lfloor \frac{y}{a}\rfloor$ であり、 $\mod(y,a)=q=\mod(n,a)$ であるから、 $\displaystyle x=\lfloor\frac{n}{a}\rfloor$ に注意すると

$\displaystyle\frac{1}{2} \lt \mod (\lfloor \lfloor \frac{y}{a}\rfloor\times 2^{-a x -\mod(y,a)}\rfloor,2 )$

となる。あとは、ピクセルの正方形を塗りつぶすために整数 $x,y$ を $\lfloor x\rfloor,\lfloor y\rfloor$ に換えてやれば

$\displaystyle\frac{1}{2} \lt \mod (\lfloor \lfloor \frac{y}{a}\rfloor\times 2^{-a \lfloor x\rfloor -\mod(\lfloor y\rfloor,a)}\rfloor,2 )$

が得られる。個人的には、modと床関数の順番は、こっちの方がしっくりくる。

ここで $y\in [na,(n+1)a]$ である。

なお、タッパーの自己言及式には横幅 $b$ が明示されていないことに注意しよう。 $y$ の範囲から $n$ と $a$ が求まるので自動的に $x$ の範囲である横幅が、 $n$ の2進数表示の桁数を $a$ で割った商の天井関数として決まるのである。

$a=5$ として、 $5\times 5$ の正方形に好きな絵を書かせたとして、25bit だから、5倍しても 28bit 以下。 4byte の int の範囲で収まる。これって pbm 画像の生成と絡めてプログラミングの演習問題に使えんじゃね？

参考:

$a=17,b=106$ の場合に $k=na$ を生成してくれる web page

keelyhill.github.io

の最下位ビット(右上)だけ立てると17になる。

タッパーの論文の値は

960939379918958884971672962127852754715004339660129306651505519271702802395266424689642842174350718121267153782770623355993237280874144307891325963941337723487857735749823926629715517173716995165232890538221612403238855866184013235585136048828693337902491454229288667081096184496091705183454067827731551705405381627380967602565625016981482083418783163849115590225610003652351370343874461848378737238198224849863465033159410054974700593138339226497249461751545728366702369745461014655997933798537483143786841806593422227898388722980000748404719

であり、これは17で割り切れて、その商は

56525845877585816763039586007520750277353196450595841567735618780688400140898024981743696598491218713015714928398271962117249251816126135758313291996549277852226925632342583919395030421983352656778405325777741906072873874481412543269713885225217255170734791425252274534182128499770100304909062813395973629729728331022409858974448530410675416671693127285242093542682941391314786490816144814610513955188130873521380296068200591469100034890490542735132321279502689903923668808556530273882231399913969596693343635681966013405787571940000044023807

となる。そしてこれを2進数に直すと

110010101000100001010101011111000010010010100000000000000000000000000000001000000000000000101000000000000010001000000000000000000000001111111111111111110000000000000000100000111100000000000000001000000000000011100000000000000000100000000000001110000000000000000000000000000000011000000000000001001000000000000010010000000000000011000000000000000000000000000000001100000000000000100100000000000001001000000000000011111100000000000000000000000000011111110000000111000000011100110000000000000110000000000000000011111111111111110100000000000000001011111010000000000000000101011000001100101001000001000111010001100010000000000000000111111111111111100000000000000000000000011001000000000000101001000000000001001010000000000010001000100000000000000001000000000000000000000000000000011111000000000000000000000000000001100100000000000000111000000000000000000000000001111111100000000010000000000000000100101000000000000000100000000000010010100000000000100000000000000001111111100000000000000000000000000000001000000000000000010000000000000000000000000000000111000000000000000010000000000000011100000000000000001000000000000001100000000000000000000000000000000111000000000000001010000000000000011100000000000000000000000000000001110000000000000010100000000000000111110000000000000000000000000000111100000000000110000110000000000000000000000000011111111000000000100000000000000001010110000000000000010000000000000100011000000000001000000000000000011111111000000000000000000000000001000000000000000001100000000000000000000000000000000001111100000000000000000000000000000110010000000000000011100000000000000000000000000110000110001000000011110000001100000000000000000000000000000000001100100000000000010100100000000000100101000001100001000100001100111000000011100100001111111000001000000000000000011111111111111111

となる。この2進数の桁数1800だから $17\times 106=1802$ に2足りないので頭に00つけて