Ways of Synthesizing Binary Programs Admitting Recursive Call of Procedures
V. V. Zhukov · Moscow University Computational Mathematics and Cybernetics · 2021
Abstract A model of binary programs implementing the functions of the algebra of logic (Boolean functions) is considered. The programs consist of one or several modules containing instructions of three types: computational and redirecting instructions and instructions for summoning the procedures. In contrast to earleir models of binary programs, a model is introduced that admits the recursive summoning of procedures; i.e., the procedures can directly summon themselves while executing a binary program, or through other procedures. The functioning of this model of programs is described, as is its relationship to other discrete control systems (e.g., circuits made of functional elements or binary decision diagrams). Ways are presented for obtaining lower and upper estimates of the Shannon function for the complexity of using Boolean functions in the class of binary programs. The proposed technique allows the asymptotics of the Shannon function to be established under certain structural and parametric limitations imposed on the model of binary programs.