Про процедурну платформу для теорії алгоритмів

• Дата: 2023
• Автор: Zubenko, Vitaly
• Формат: Стаття
• Мова: Українська
• Опубліковано: Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023
• Теми: алгоритм; обчислювальна процедура; алгоритмічна процедура; алгоритмічне числення; оперативна таблиця
• Онлайн доступ: https://www.fmmit.lviv.ua/index.php/fmmit/article/view/283
• Назва журналу: Physico-mathematical modeling and informational technologies

The work is devoted to an attempt to mathematically clarify the general concept of an algorithm. It is proposed to move away from the practice existing in the theory of algorithms to define a specific representative class of algorithms and associate the general concept of an algorithm with it. Our approach is based on the idea of mathematically specifying a more abstract and broader concept  -  a  computational  procedure[2],  and  then  in  narrowing  it  down  to  the  notion  of  an algorithm.  The  concept  of  operational  table  of  procedures  is  introduced,  and  the  basis  of narrowing is the solvability of these tables. The place of basic mathematical models of algorithms and  calculations  within  the  proposed  procedural  platform,  such  as  finite  automata,  Turing machines, normal algorithms, discrete Glushkov transforms, formal grammars, Post systems, and others,  is  considered.  As  it  turns  out,  procedures  with  finite  operational  tables  correspond  to almost all of these models. Issues of arrangement and systematization of all currently existing models of algorithms and calculus within the framework of this platform are discussed.