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

Анотація

Робота присвячена спробіматематичного уточнення загального поняттяалгоритму. Пропонуєтьсявідійти від існуючоївтеорії алгоритмів практики визначати якийсь конкретний представницькийклас алгоритмів[1]і пов’язувати з ним загальне поняття алгоритму. Наш підхід базується на ідеїматематичного уточненнябільш абстрактногоі ширшогопоняття -обчислювальної процедури [2], а потім у звуженні йогодо поняття алгоритму. Вводиться поняття оперативної таблиці процедур і в основу звуження покладена розв’язність цих таблиць.Розглядаєтьсямісце основних математичних моделей алгоритмів та обчислень в межахзапропонованої процедурної платформи таких як скінченні автомати, машини Тюринга,нормальні алгоритми, дискретні перетворювачі Глушкова, формальні граматики, системи Поста та інші. Як з’ясувалося, майже всім цим моделям відповідають процедури зі скінченнимиоперативними таблицями. Обговорюються питання упорядкування та систематизації всіх існуючих на сьогодні моделей алгоритмівта числень в межах даної платформи.