講演抄録/キーワード |
講演名 |
2012-11-01 10:25
三値関数を実現するMalbolge命令列の発見のためのSATエンコーディング ○安藤 聡・酒井正彦・坂部俊樹・草刈圭一朗・西田直樹(名大) SS2012-37 |
抄録 |
(和) |
Malbolgeは最も難解なプログラミング言語として知られている.低級アセンブリ言語の開発によりMalbolgeのループプログラムの作成が可能になったものの,低級アセンブリ言語には通常のプログラミング言語が持つような演算命令がなく,Malbolge特有の演算を行う命令のみであるため,低級アセンブリ言語でのプログラミングにも困難が伴う.低級アセンブリプログラミングにおいては,目的のプログラムに必要な二引数三値関数を実現するMalbolge特有の演算命令列の発見が求められる.しかしこれまで,そのような命令列を発見するための手法は網羅的な探索に限られており,低級アセンブリプログラミング上の制限となっていた.本稿では,二引数三値関数を実現するMalbolge命令列の発見にSATソルバを利用した手法を提案することで,この問題の解決を試みる.そのため,二引数三値関数を実現するMalbolge命令列を発見する問題を定式化し,その問題のSATエンコーディングを提案する.実験により,既存手法より高速に,かつ,長い命令列が発見できることが分かった. |
(英) |
Malbolge is known to be one of the most esoteric programming languages. Although it becomes possible to write programs in Malbolge language due to the development of the low-level assembly language, the programming in the low-level assembly language is difficult. This is because the arithmetic instructions of the low-level assembly language are not those of ordinary programming languages, but the same as the ones of Malbolge. To construct a program in low-level assembly language, it is necessary to find instruction sequences of Malbolge that implement binary trit-wise functions. For finding such instruction sequences, however, an inefficient exhaustive search is the only known method, which is one of limitations in developing programs in the low-level assembly language. In this paper, to solve this problem, we propose a method to find instruction sequences of Malbolge that implement binary trit-wise functions, which is more efficient due to the use of state-of-art SAT solvers. We formalize a problem that finds an instruction sequence of Malbolge that implements a given binary trit-wise function,and propose a SAT encoding for this problem. Experiments shows that our method is able to find instruction sequences faster than the existing method and hence essentially longer ones. |
キーワード |
(和) |
難解プログラミング言語 / Malbolge / SATエンコーディング / 三値関数 / / / / |
(英) |
Esoteric programming language / Malbolge / SAT encoding / Trit-wise function / / / / |
文献情報 |
信学技報, vol. 112, no. 275, SS2012-37, pp. 7-12, 2012年11月. |
資料番号 |
SS2012-37 |
発行日 |
2012-10-25 (SS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
SS2012-37 |
|