When Every Total Program Is a Finite Tree-Program: A Study of Program-Saturated Classes of Structures
Mikhail Moshkov · Axioms · 2025
This paper investigates classes of structures and individual structures where programs implementing functions defined everywhere (total programs) are equivalent to finite tree-programs. The programs considered may include cycles and contain at most countably many nodes. The analysis begins with programs where arbitrary terms of a given signature are used in function nodes, and arbitrary formulas of this signature are used in predicate nodes. The results are then extended to programs that closely resemble computation trees: if such a program is a finite tree-program, it can be classified as an ordinary computation tree.