Про процедурну платформу для теорії алгоритмів
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 a...
Gespeichert in:
| Datum: | 2023 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2023
|
| Schlagworte: | |
| Online Zugang: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/283 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Physico-mathematical modeling and informational technologies |
| Завантажити файл: |  |
Institution
Physico-mathematical modeling and informational technologies| _version_ | 1867479652112531456 |
|---|---|
| author | Zubenko, Vitaly |
| author_facet | Zubenko, Vitaly |
| author_institution_txt_mv | [
{
"author": "Vitaly Zubenko",
"institution": "к.ф.-м.н., доцент, КНУ ім.Тараса Шевченка, вул. Володимирська, 60, Київ, 01033"
}
] |
| author_sort | Zubenko, Vitaly |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:32:19Z |
| description | 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. |
| first_indexed | 2026-06-09T01:09:40Z |
| format | Article |
| fulltext |
92
doi.org/10.15407/fmmit2023.36.092
Про процедурну платформу для теорії алгоритмів
Віталій Зубенко
к.ф.-м.н., доцент, КНУ ім.Тараса Шевченка, вул. Володимирська, 60, Київ, 01033, e-mail: vvz1952@gmail.com
Робота присвячена спробі математичного уточнення загального поняття алгоритму.
Пропонується відійти від існуючої в теорії алгоритмів практики визначати якийсь
конкретний представницький клас алгоритмів1 і пов’язувати з ним загальне поняття
алгоритму. Наш підхід базується на ідеї математичного уточнення більш абстрактного і
ширшого поняття - обчислювальної процедури [2], а потім у звуженні його до поняття
алгоритму. Вводиться поняття оперативної таблиці процедур і в основу звуження
покладена розв’язність цих таблиць. Розглядається місце основних математичних моделей
алгоритмів та обчислень в межах запропонованої процедурної платформи таких як
скінченні автомати, машини Тюринга, нормальні алгоритми, дискретні перетворювачі
Глушкова, формальні граматики, системи Поста та інші. Як з’ясувалося, майже всім цим
моделям відповідають процедури зі скінченними оперативними таблицями.
Обговорюються питання упорядкування та систематизації всіх існуючих на сьогодні
моделей алгоритмів та числень в межах даної платформи.
Ключові слова: алгоритм, обчислювальна процедура, алгоритмічна
процедура, алгоритмічне числення, оперативна таблиця.
Вступ. Причина відсутності в теорії алгоритмів загального визначення
алгоритму – на поверхні. Існуючі моделі алгоритмів нерозривно пов’язані з
конкретними фінітними мовами їхнього подання, а скільки моделей – стільки й
мов. Щоб обійти цю першопричину, введемо абстрактне поняття процедури, а
потім сформулюємо місце алгоритмів серед процедур.
1. Покладемо {0,1,...}T , [0.. ]nT n , S та 0S S ) - сукупності станів та
вхідних станів. Трійка 0( , , )T S S називається обчислювальним простором.
Нехай *S , та S – сукупності відповідно усіх скінченних та нескінченних
процесів : , :np T S p T S , які подаються словами 0 1... ns s s або 0 1...s s
алфавіті S . Початкові скінченні відрізки процесів будемо називати їхніми
префіксами.
Серед усіх процесів виділимо обчислювальні процеси, в яких поява
чергового стану не довільна, а є результатом певної елементарної операції над
його крайнім станом. Зафіксуємо певну сукупність { : , 0,1,...}if S S i
часткових елементарних операцій на станах. Позначимо 2 множину всіх
скінченних підмножин . Оперативна функція має вигляд : 2S і
1
Тобто такий, що в ньому є еквівалентний алгоритм для кожного інтуїтивного алгоритму [1].
УДК 519.9
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 36, 92-95
93
регулює порядок застосування операцій в обчисленнях. Обчислювальною
процедурою у просторі із сукупністю елементарних операцій та
оперативною функцією називається трійка ( , , )P .
Кожна обчислювальна процедура породжує певну сукупність обчислень за
процедурою P , які визначаються рекурентно: 0p s і для всіх 0t
1( )t t tp f p , де Ss - початковий стан обчислення, а tf - одне зі значень
оперативної функції на префіксі 0 1... tp p .
До найпростіших видів процедур відносяться темпоральні, в яких
значення оперативної функції 0 1( ... )tp p визначається просто за номером
кроку обчислення та автоматні, в яких це значення залежить тільки від
останнього стану обчислення, тобто 0 1 1( ... ) ( )t tp p p . Більшість класичних
алгоритмічних систем є саме автоматними.
Основних механізмів завершення обчислень - два. Коли в процесі
обчислення оперативна функція чи елементарна операція не визначена або
крайній стан належить до виділеної підмножини fS S заключних станів.
Крайній стан обчислення з початковим станом s позначається
*( )P s . Він може
бути не один. Про відповідності
*
0:P S S та
*
0: fP S S говорять, що їх
обчислює процедура P , а саму процедуру називають процедурою-функцією.
В гіперобчисленнях процес може продовжуватися і після переходу в
заключний стан. Тоді результат
**( )P s складають усі його вихідні стани.
Часто цікавлять не самі стани, а тільки ті чи інші їхні складові і тоді
розглядають не саму відповідність, яку обчислює процедура, а її проекцію на ці
складові. Зустрічаються такі обчисленння, коли для отримання наступного його
стану є необхідність звернутися не тільки до поточного стану, а й до деяких
інших. Це спонукає перейти від унарних операцій до k арних, 1k , вигляду
: ...kf S S S , які, на відміну від елементарних операцій, можуть бути і
багатозначними. Нехай множина є сукупністю ik -арних операцій
ki
if . Вхідні
стани тепер називаються – аксіомами, а функція керування *: 2S тепер
визначена і на порожньому префіксі. Четвірка ( , , , )fP S називається
процедурою-численням. Наступний стан обчислення tp в численнях
визначається так. Для
ki
if 0 1( ... )tp p , (
ki
if ( ) для нульового кроку) з
попередніх станів 0 1 1, ,..., tp p p та аксіом формується довільний кортеж
1( ,..., )ki
q q з області визначення функції
ki
if і тоді 1( ,..., )
ki
t i ki
p f q q . Мають
місце гіперобчислення. Крайні стані і проміжні заключні складають теорію
( )Th P числення P .
Ми побудували загальну теоретико-множинну модель поняття
обчислювальної процедури. Тепер, щоб отримати математичне визначення
Віталій Зубенко
Про процедурну платформу для теорії алгоритмів
94
алгоритму, необхідно формально виокремити алгоритми серед всіх
обчислювальних процедур.
2. Алгоритми мають справу тільки з конструктивними об’єктами і самі є такими
об'єктами. Отже, всі стани алгоритмічної процедури, елементарні операції та
оперативна функція мають бути конструктивними в межах певної фінітної
дескриптивної системи. Конструктивність функції означає, що існує її фінітний
опис, який дозволяє за скінченну кількість кроків знайти значення функції за
даними аргументами.
Нагадаємо, що два елементи функції ядерно еквівалентні, якщо значень
функції на цих елементах збігаються. Індексом відношення еквівалентності
називається потужність множини його фактор-класів. Ядерна еквівалентність
оперативної функції завжди має скінченний індекс, якщо множина елементарних
операцій скінченна. Операційну функцію можна задати таблично –
оперативною таблицею, в першому стовпчику якої перераховані всі класи
ядерної еквівалентності, у другому – її значення на префіксах обчислень даного
класу. Отже, щоб знайти значення оперативної функції достатньо знайти рядок
таблиці, до якого належить префікс і взяти одну з операцій з другого стовпчика.
Оперативну таблицю назвемо розв’язною, якщо існує алгоритм, який дозволяє
знайти в ній рядок, до якого належить довільний префікс або дати відповідь, що
такого рядка немає. Розв’язність оперативної таблиці гарантує існування
скінченного опису оперативної функції. Отже, ми готові сформулювати, що таке
алгоритм в термінах обчислювальних процедур.
Алгоритм – це обчислювальна процедура з конструктивними станами і
такими ж елементарними операціями та розв’язною оперативною таблицею.
Тут не виникає «зачароване коло», пов’язане з розв’язністю оперативної
таблиці, тому що мова йде не про загальну розв’язність множин, а тільки про
окремі її часткові випадки, кожен з яких в разі потреби може бути математично
уточненим без апеляції до загального поняття. Далі алгоритми як алгоритмічні
процедури будемо називати А-процедурами.
Якщо звернутися до існуючих алгоритмічних систем та числень, то можна
помітити що: 1) вони, як А-процедури є в основному автоматними (за винятком
неавтоматних числень) і 2) для переходів визначальними є стани не в усьому
їхньому об’ємі, а тільки вмісти певних обмежених («активних» за [1]) їхніх
структурних фрагментів. Збіг вмістів цих обмежених фрагментів лежить в основі
ядерної еквівалентності більшості оперативних функцій А-процедур.
Розглянемо для прикладу машини Тюрінга (МТ). МТ має скінченнну
кількість внутрішніх станів і вхідну стрічку, в якій розміщується вхідне слово з
*X , один з символів якого є доступним для обробки. В процесі обчислення МТ
може змінити внутрішній стан, замінити доступний символ стрічки на інший і
залишити його доступним або зробити доступним символ справа чи зліва від
нього. МТ завжди зупиняється при переході в заключний внутрішній стан
(відсутні гіперобчислення). Заключне слово на стрічці є результатом обробки
МТ вхідного слова. Станами А-процедури МТ є пари (внутрішній стан МТ,
слово на стрічці з виділеною доступною коміркою). В початкових станах
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 36, 92-95
95
внутрішній стан МТ є початковим, в заключних – заключним. Функція-проекція
повертає вміст стрічки стану. Оперативна функція А-процедури відповідає
функції переходів МТ і є скінченою та автоматною. Два стани А-алгоритму МТ
ядерно еквівалентні, якщо їхні внутрішні стани та вмісти доступних комірок на
стрічках збігаються. Подібні А-процедурні еквіваленти можуть бути побудовані
і для решти існуючих алгоритмічних систем.
Загальні властивості А-процедур мають свою інтерпретацію в усіх
конкретних алгоритмічних системах і не потребують в останніх додаткових
доведень. Наприклад, відомо про існування певної регулярної алгебраїчної
форми для функцій, обчислювальних А-процедурами [4]. Існування подібних
форм для випадку функцій, обчислюваних машинами Тюрінга і дискретниими
перетворювачами свого часу було доведено в роботах Якопіні та Глушкова. Це
також стосується замкнення класів обчислювальних функцій відносно основних
функціональних композицій та теоретико множинних операцій.
Висновки. Отже, розглянута процедурна платформа для теорії алгоритмів, в
основу якої покладено поняття А-процедури. Проілюстровано як дана платформа
може бути використана для упорядкування існуючих алгоритмів та числень та
вивчення їхніх загальних властивостей. А-процедури можуть бути покладені в
основу розбудови та дослідження нових моделей обчислень.
Література
[1] Успенский В.А. Теория алгоритмов: ее основные открытия и приложения/ Cеменов
А.Л.- В кн. Алгоритмы в современной математике и ее приложениях/ под.ред.
А.П.Ершова, Д. Кнута.-Н.: ВЦ СО АН СССР.- 1982.-Ч.1.- с. 99-342.
[2] Зубенко В. В. Програмування: Навчальний посібник / Л.Л. Омельчук.– К.: ВПЦ
«Київський університет», 2011. - 625 с.
[3] Зубенко В.В. Темпоральні процедури та алгоритми // Проблеми програмування , 2006,
№ 2-3, c. 53-59.
On a procedural platform for the theory of algorithms
Vitaly Zubenko
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.
Отримано 15.03.23
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-283 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:09:40Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/38/b6924da370ac11c16e3ab730d513df38.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-2832025-02-21T17:32:19Z On a procedural platform for the theory of algorithms Про процедурну платформу для теорії алгоритмів Zubenko, Vitaly алгоритм, обчислювальна процедура, алгоритмічна процедура, алгоритмічне числення, оперативна таблиця 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. Робота присвячена спробіматематичного уточнення загального поняттяалгоритму. Пропонуєтьсявідійти від існуючоївтеорії алгоритмів практики визначати якийсь конкретний представницькийклас алгоритмів[1]і пов’язувати з ним загальне поняття алгоритму. Наш підхід базується на ідеїматематичного уточненнябільш абстрактногоі ширшогопоняття -обчислювальної процедури [2], а потім у звуженні йогодо поняття алгоритму. Вводиться поняття оперативної таблиці процедур і в основу звуження покладена розв’язність цих таблиць.Розглядаєтьсямісце основних математичних моделей алгоритмів та обчислень в межахзапропонованої процедурної платформи таких як скінченні автомати, машини Тюринга,нормальні алгоритми, дискретні перетворювачі Глушкова, формальні граматики, системи Поста та інші. Як з’ясувалося, майже всім цим моделям відповідають процедури зі скінченнимиоперативними таблицями. Обговорюються питання упорядкування та систематизації всіх існуючих на сьогодні моделей алгоритмівта числень в межах даної платформи. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-13 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/283 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 92-95 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 36 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 92-95 2617-5258 1816-1545 10.15407/fmmit2023.36 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/283/247 |
| spellingShingle | алгоритм обчислювальна процедура алгоритмічна процедура алгоритмічне числення оперативна таблиця Zubenko, Vitaly Про процедурну платформу для теорії алгоритмів |
| title | Про процедурну платформу для теорії алгоритмів |
| title_alt | On a procedural platform for the theory of algorithms |
| title_full | Про процедурну платформу для теорії алгоритмів |
| title_fullStr | Про процедурну платформу для теорії алгоритмів |
| title_full_unstemmed | Про процедурну платформу для теорії алгоритмів |
| title_short | Про процедурну платформу для теорії алгоритмів |
| title_sort | про процедурну платформу для теорії алгоритмів |
| topic | алгоритм обчислювальна процедура алгоритмічна процедура алгоритмічне числення оперативна таблиця |
| topic_facet | алгоритм обчислювальна процедура алгоритмічна процедура алгоритмічне числення оперативна таблиця |
| url | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/283 |
| work_keys_str_mv | AT zubenkovitaly onaproceduralplatformforthetheoryofalgorithms AT zubenkovitaly proprocedurnuplatformudlâteorííalgoritmív |