三値関数を実現するMalbolge命令列の発見のためのSATエンコーディング

概要

論文の詳細を見る
Malbolge は最も難解なプログラミング言語として知られている.低級アセンブリ言語の開発により Malbolge のループプログラムの作成が可能になったものの,低級アセンブリ言語には通常のプログラミング言語が持つような演算命令がなく, Malbolge 特有の演算を行う命令のみであるため,低級アセンブリ言語でのプログラミングにも困難が伴う.低級アセンブリプログラミングにおいては,目的のプログラムに必要な二引数三値関数を実現する Malbolge 特有の演算命令列の発見が求められる.しかしこれまで,そのような命令列を発見するための手法は網羅的な探索に限られており,低級アセンブリプログラミング上の制限となっていた.本稿では,二引数三値関数を実現する Malbolge 命令列の発見に SAT ソルバを利用した手法を提案することで,この問題の解決を試みる.そのため,二引数三値関数を実現する Malbolge 命令列を発見する問題を定式化し,その問題の SAT エンコーディングを提案する.実験により,既存手法より高速に,かつ,長い命令列が発見できることが分かった.
2012-10-25