Efficient program synthesis in computational models

AbstractStarting from the system PRIZ, the method of automatic program synthesis is used in AI systems. We determine (1) the precise description of a class of computational models; (2) the precise description (acute semantics) of such concepts as “a solution of a computational task” and “solvability of a computational task”; (3) the calculus of dependencies OLD, which is proved to be correct and strongly complete with respect to the proposed semantics. On the basis of OLD, we construct an algorithm which analyzes a computational task and synthesizes a program for its solution and which runs in small (subquadratic) space with quasi polynomial time (the degree of the polynomial does not exceed the minimal number of subtasks that must interact in any solution of the main task). This algorithm can synthesize optimal programs which have minimal execution time