2019年9月3日

タッパーの自己言及式の導出過程を想像してみる

タッパーの自己言及式というものを紹介するツイートがあったので、WikiPedia掲載の式を見てみると、なんだかそのものずばりで高尚な符号理論ではないっぽい雰囲気がした。ので、導出過程を想像してみた。

タッパーの自己言及式プログラミング数学

tdmiura
5876
5
1
0

横山明日希 @asunokibou

これすごく好き。どうやって思いついたのだろう。笑 pic.twitter.com/qYnLIEKamg

2019-08-31 21:40:36

拡大

脊髄反射

代数符号とか符号列を数式として扱うのに先人が苦労しただろう跡もあるし、ビット列を桁の多い数にするには算術符号とかもあったしなあ、と脊髄反射

Toshitaka Miura @tdmiura

@asunokibou 符号理論というやつがビットの並びと数式を関連付ける形で作られているし、実装例として算術符号という先例もあるとすれば、ビットマップを適当にエンコードした大きな数とそれをデコードしてビットマップに戻す数式の組は作れるんじゃないですかね。部品としての切捨てとモジュロもまあ使いやすい。

2019-09-02 19:53:44

式をよく見たらとても分かりやすかった。

ひとっ風呂浴びてから引用されたWikiPediaの記事を見たら、なんかすごくわかりやすくというかそのものずばりの、2次元座標に描いたドット絵を2進数として読み取ったのを2次元座標に展開し直すアルゴリズムを表現した式だった。

しかも発表されたのがACM SIGGRAPHときた。
ああ、こういうおふざけを堂々と発表できる学会いいよね。

思い立ってもやもやしてしまったので、想像をつけたアルゴリズムというか導出過程を書き残したくなった。

Toshitaka Miura @tdmiura

@asunokibou というか、式をよく見ると2値のビット列を座標に展開するそのものずばりのエンコードじゃん。 a) ビットマップの縦の長さを決める。タッパーの式では17。 b) ビット列を2進数に見立てて10進に変換したものを絵のコードと決める。 c) ビット列を縦の長さで折り畳んで2次元座標に展開する式を考える。

2019-09-03 01:46:46

Toshitaka Miura @tdmiura

@asunokibou c-0) ビットマップをコードする2進数Bの桁位置iの数えはじめを1桁目とする。 c-1) 座標(x,y)をBの桁位置iに折り畳む一例は、縦の長さ17よりx=floor(i/17), y=i mod 7 c-2) Bの各桁b_iを取り出すには、2^(i-1)で割って小数点以下を捨て、モジュロ2で上を捨てればいいので b_i=floor(B*2(1-i)) mod 2。

2019-09-03 02:12:24

Toshitaka Miura @tdmiura

@asunokibou タイプミス。 c-1) の y は y=i mod 17 。

2019-09-03 02:24:09

Toshitaka Miura @tdmiura

@asunokibou c-3) b_i の周りを1×1のサイズに四角く塗りつぶすのを場合分けを使わずに表現するには、b_iが0か1だから間の1/2を閾値とする不等式にする。 c-4) 式一本にまとめるために c-1) の(x,y)をiについて説き、c-2) に代入し表記を調える。

2019-09-03 02:20:08

Toshitaka Miura @tdmiura

@asunokibou d) c-4) の式を縦17のドット絵に描き、c-1) の順に 2^i の重みを与えて総和を取れば絵のコードBを与える。

2019-09-03 02:22:22

Toshitaka Miura @tdmiura

@asunokibou どうよ。もう、先にビットマップありきの泥縄導出だと思うな。