The Japanese Society for Artificial Intelligence

Expressivity and scalability are the primary challenges in inductive program synthesis. While constructive synthesis frameworks may address scalability through direct access to the proof structure, the current logic programming languages are not optimized for efficient constructive inductive inference. To solve this problem, we proposed an inference system named MPL. MPL's deduction model can be relatively easily inverted, due to its use of maximum sentence size and restriction of global symbols to predicates only. In this paper, we introduce the deductive inference model of MPL and demonstrate that MPL can be utilized to simulate Cyclic Tag System, a Turing complete computational model.