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 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.

Cite: Goncharov S. , Nechesov A. , Sviridenko D.
Programming Methodology in Turing-Complete Languages
In compilation Proceedings 2024 IEEE International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), Novosibirsk, Russian Federation, 2024. – IEEE., 2024. – C.272-276. – ISBN 979-8-3315-3202-4. DOI: 10.1109/sibircon63777.2024.10758446 Scopus OpenAlex

Dates:

Published print:	Nov 26, 2024
Published online:	Nov 26, 2024

Identifiers:

Scopus:	2-s2.0-85212159329
OpenAlex:	W4404741295

Citing:

DB	Citing
Scopus	1

Altmetrics: