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

• 安藤, 聡

• 酒井, 正彦

• 坂部, 俊樹

• 草刈, 圭一朗

• 西田, 直樹

• ANDO, Satoshi

• SAKAI, Masahiko

• SAKABE, Toshiki

• KUSAKARI, Keiichirou

• NISHIDA, Naoki

書誌事項

タイトル別名

• サンチ カンスウ オ ジツゲン スル Malbolge メイレイレツ ノ ハッケン ノ タメ ノ SAT エンコーディング
• A SAT Encoding for Finding Operation Sequences of Malbolge that Implement Trit-wise Functions

抄録

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

収録刊行物

• 電子情報通信学会技術研究報告. SS, ソフトウェアサイエンス

  電子情報通信学会技術研究報告. SS, ソフトウェアサイエンス 112 (275), 7-12, 2012-10

  一般社団法人電子情報通信学会

キーワード

• 難解プログラミング言語
• Malbolge
• SATエンコーディング
• 三値関数
• Esoteric programming language
• SAT encoding
• Trit-wise function

詳細情報

• CRID: 1050564288758100864
• NII論文ID: 110009465419
• NII論文ID: 110009642349
• NII書誌ID: AA1123312X
• HANDLE: 2237/23558
• NDL書誌ID: 024148989
• ISSN: 09135685
• Web Site: https://nagoya.repo.nii.ac.jp/records/21415
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I024148989
• 本文言語コード: ja
• 資料種別: journal article
• データソース種別:
  • IRDB
  • NDL
  • CiNii Articles
  • KAKEN