Most complex algorithm

もっとも複雑なアルゴリズム

受賞者:Paul E. Black

引用元:https://www.ioccc.org/1989/paul.c

審査員・作者による説明:https://github.com/ioccc-src/winner/blob/main/1989/paul.hint

動作

2進数でフィボナッチ数を列挙していく。

$ gcc -m32 -o paul paul.c

$ ./paul
1
10
11
101
1000
1101
10101
100010
110111
1011001
10010000
11101001
101111001
1001100010
1111011011
11000111101
101000011000
1000001010101
1101001101101
10101011000010
100010100101111
...

解説

チューリングマシンのシミュレータ。 詳細未解読だが、3文字1組で状態遷移の規則を表現しているらしい(遷移元状態、遷移先状態、遷移条件やヘッダ移動や出力など)。 デフォルトのチューリングマシンが組み込まれていて、それがフィボナッチ列挙になっている。

独自のVMやシミュレータによる難読化の先駆けか。 1994年のguidelineから、この方式の難読化はもっとクリエイティブになること(面白い挙動をするとか)が期待されるようになっている。

ポインタをintに変換しているので、-m32が必要。