Programming Methodology in Turing-Complete Languages
Sergey Savostyanovich Goncharov, Andrey Vitalievich Nechesov, Dmitriy Sviridenko · 2024
The paper delves into the intricacies of designing programs with polynomial computational complexity within Turing-complete languages. It proposes a novel approach to reducing high-level programming languages into p-complete ones. Based on the concept of semantic programming, the programming methodology in Turing-complete languages is developed, which allows to use of several crucial constructs such as loop operator FOR on lists, conditional operators, and specific types of recursion, albeit with certain limitations. This approach preserves the rich expressiveness of the language while ensuring polynomial complexity. The development of software products based on programming methodology allows us to guarantee their dependability, good readability, and predict the duration of their execution. These aspects are of paramount importance for the development of trustworthy artificial intelligence systems.