Brainfuck => ShaFuck translator
ShaFuck という言語があります。チューリング完全なのに、難解どころか、プログラムを書くことは不可能だと主張してる言語です。
http://esolangs.org/wiki/ShaFuck
不可能だと主張している理由は、入力として受け取ったコードを SHA1 した結果を BF として実行して、かつ 8 つの BF コマンドでないコードが実行されるとプログラムがエラー終了してしまうからです。
で、今回は Brainfuck から ShaFuck への翻訳機が書けたという話。コレ
http://shinh.skr.jp/obf/bf2sf.rb
shafuck-0.2 で実行可能な hello と cal
http://shinh.skr.jp/obf/hello.sf
http://shinh.skr.jp/obf/cal.sf.gz
どうやったかというと、 20 bytes (=160bits) のうち、 3 bytes くらいは 1/2**24 くらいの確率で狙ったやつが現われるので、先頭 3 bytes か末尾 3 bytes くらいは総当たりぶんまわせば欲しいものが見つかるので、後の 17 bytes をうまいこと無視するような組み合わせで、 Brainfuck の 8 命令を実現すればいい、と。今回私が使ったのは
+ => +>[ (17B) (18B) ]< - => ->[ (17B) (18B) ]< > => >[ (18B) (18B) ]> < => <[ (18B) (18B) ]< . => .>[ (17B) (18B) ]< , => ,>[ (17B) (18B) ]< [ => >[ (18B) (17B) ]<[ ] => >[ (18B) (17B) ]<]
というような対応。 Brainfuck コマンド 1 つに対して 2 code chunks 、つまり 2048 bytes を消費するという。
