Abstract: 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 program- ming 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.

Cite: Goncharov S. , Nechesov A. , Sviridenko D.
Programming Methodology in Turing-complete languages.
2024 IEEE International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), Novosibirsk, Russian Federation, 2024 30 Sep - 2 Oct 2024