著者

長坂 哲 酒井 正彦 坂部 俊樹 草刈 圭一朗 西田 直樹 NAGASAKA Satoshi SAKAI Masahiko SAKABE Toshiki KUSAKARI Keiichirou NISHIDA Naoki

出版者

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

雑誌

電子情報通信学会技術研究報告SS, ソフトウェアサイエンス (ISSN:09135685)

巻号頁・発行日

vol.110, no.227, pp.55-60, 2010-10

---

Malbolgeは最も難解なプログラミング言語として知られている.本研究では,飯澤らが提案したプログラミング手法に基づいて,Malbolgeが弱チューリング完全性を持つこと示す.そのために,チューリング完全性を持つ正規形のNプログラムをMalbolgeコードに変換できることを示す.ここで,本稿で示す性質が弱チューリング完全性であるのは,Malbolgeが固定されたメモリ空間およびレジスタ長の仮想機械により意味が定められているためである. Malbolge is known as one of the most esoteric programming languages. In this paper, we prove that Malbolge is weakly Turing complete. The proof is based on the Malbolge programming method proposed by Iizawa, et al. We give a transformation from the normal form N-programs known to be Turing complete into Malbolge programs. Completeness that this paper shows is weak one due to the fact that the semantics of Malbolge is hard coded into a virtual machine of which memory space and register length are fixed.

著者

馬野 洋平 酒井 正彦 西田 直樹 坂部 俊樹 草刈 圭一郎 UMANO Yohei SAKAI Masahiko NISHIDA Naoki SAKABE Toshiki KUSAKARI Keiichirou

出版者

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

雑誌

電子情報通信学会技術研究報告SS, ソフトウェアサイエンス (ISSN:09135685)

巻号頁・発行日

vol.107, no.392, pp.73-78, 2007-12 (Released:2015-01-20)

---

近年,論理式の充足可能性判定ツール(SATソルバ)の高速化が進み,これを利用した数独パズルの解法が提案されている.本稿では,この解法を応用して試作した,対話的に数独パズルの問題を作成するツールについて報告する.このツールでは,「セルに埋めても矛盾を生じない数字の表示」・「削除しても問題が一意性を保つセルの表示」・「問題を手筋のみで解ける範囲の図示」の三つの主要機能を実装している.前者二つの機能は,SATソルバを利用した解法を応用して問題め矛盾・解の一意性を高速に検出することにより実現している. In recent years, several efficient SAT solvers, which decide satisfiability of boolean formulae, have been developed and used in solving Sudoku puzzles. In this paper, we present the interactive tool for designing Sudoku puzzles that we constructed experimentally by using a SAT solver. This tool contains three main functions: 'displaying numbers that can be filled in a cell without a contradiction', 'displaying cells without contributing the uniqueness', 'displaying a partial solution obtained by fundamental techniques.' The implementation of the former two functions relies on efficient checks of a contradiction or uniqueness of the given problem by using a SAT solver.