Категорії як формальні моделі обчислень
Various formal models of calculations are considered. In particular, recursive functions, fuzzy models and categorical models. It is shown how functions are calculated based on such models. In each of these models, the concept of number and basic arithmetic operations are i...
Збережено в:
| Дата: | 2023 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України
2023
|
| Теми: | |
| Онлайн доступ: | https://www.fmmit.lviv.ua/index.php/fmmit/article/view/313 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Physico-mathematical modeling and informational technologies |
| Завантажити файл: |  |
Репозитарії
Physico-mathematical modeling and informational technologies| _version_ | 1867479685817958400 |
|---|---|
| author | Provotar, Oleksandr Ilkun, Oleksandr |
| author_facet | Provotar, Oleksandr Ilkun, Oleksandr |
| author_institution_txt_mv | [
{
"author": "Oleksandr Provotar",
"institution": "д.ф.-м.н., професор, Київський національний університет імені Тараса Шевченка, 03127, Київ, пр. Глушкова 2"
},
{
"author": "Oleksandr Ilkun",
"institution": "Аспірант, Київський національний університет імені Тараса Шевченка, 03127, Київ, пр. Глушкова 2"
}
] |
| author_sort | Provotar, Oleksandr |
| baseUrl_str | http://www.fmmit.lviv.ua/index.php/fmmit/oai |
| collection | OJS |
| datestamp_date | 2025-02-21T17:31:10Z |
| description | Various formal models of calculations are considered. In particular, recursive functions, fuzzy models and categorical models. It is shown how functions are calculated based on such models. In each of these models, the concept of number and basic arithmetic operations are introduced. It is concluded that the considered formal models of calculations can be represented within certain categories and an abstract theory of computability and relevant programming languages can be built on a categorical basis. That is, we are talking about the creation of a universal programming language in which it would be possible to describe problems from various subject areas by interpreting them in the appropriate categories with the futher use of a universal categorical apparatus for their solution. Such a language should be oriented to scientific problems. |
| first_indexed | 2026-06-09T01:10:12Z |
| format | Article |
| fulltext |
98
doi.org/10.15407/fmmit2023.37.098
Категорії як формальні моделі обчислень
Олександр Провотар1, Олександр Ількун2
1д.ф.-м.н., професор, Київський національний університет імені Тараса Шевченка, 03127, Київ, пр. Глушкова 2,
е-mail: a.i.provotar@gmail.com
2Аспірант, Київський національний університет імені Тараса Шевченка, 03127, Київ, пр. Глушкова 2,
е-mail: alexander.ilkun@gmail.com
Розглядаються різні формальні моделі обчислень. Зокрема, рекурсивні функції, нечіткі
моделі та категорні моделі. Показано, як обчислюються функції на основі таких моделей. В
кожній з цих моделей вводиться поняття числа та основні арифметичні операції.
Робиться висновок про те, що розглянуті формальні моделі обчислень можна моделювати
в рамках тих чи інших категорій і будувати абстрактну теорію обчислюваності і
відповідні мови програмування на категорній основі. Тобто мова йде про створення
універсальної мови програмування на якій можна було б описувати задачі з різних
предметних областей шляхом їх інтерпретації у відповідних категоріях з подальшим
використанням універсального категорного апарату для їх розв’язання. Така мова повинна
бути орієнтована на наукові задачі.
Ключові слова: категорія, нечітка множина, рекурсивна функція
Вступ. Розглянемо простий приклад. Нехай маємо скінченну множину М
натуральних чисел. Необхідно знайти мінімальний елемент цієї множини.
Припустимо, що в нас є середовище, яке дозволяє описувати довільні структури
даних, зокрема множину М та поняття мінімального елемента. Крім цього, в
цьому середовищі є засоби описання і виконання алгоритмів над структурами
даних. Тоді в такому середовищі може бути знайдений мінімальний елемент
множини М як елемент відповідної структури даних.
Наприклад, множину М можна описати відношенням предпорядку . За
відношенням предпорядку побудувати категорію предпорядку (М, ).
Мінімальний елемент множини М в цьому випадку можна знайти, як початковий
об’єкт категорії.
1. Рекурсивні функції
Показати алгоритмічну обчислюваність функцій шляхом її належності до класу
частково рекурсивних функцій досить складно, окрім найпростіших функцій.
Крім того, в кожному конкретному випадку це потребує побудови математичної
моделі функції у вигляді терма із обчислюваних операцій над базовими
функціями. Базовими функціями, як відомо [1], називаються найпростіші функції
УДК 681.3, 517.11
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 37, 98-102
99
o(x) = 0, s(x) = x+ 1 та функції-селектори (x1, … , xn) = xm, де nm 1.
Основними обчислюваними операціями будуть оператори суперпозиції
S
n+1
, примітивної рекурсії R та мінімізації M.
Таким чином, функція алгоритмічно обчислювана, якщо існує операторний
терм, який її задає.
Виникає цілком закономірне питання про можливість використання
конкретних алгоритмів для доведення фундаментальних результатів теорії
рекурсивних функцій. Для цього потрібно точно описати основні конструкції
алгоритму і переформулювати (конкретизувати) тезу Чорча для більш вузьких
класів алгоритмічно обчислюваних функцій.
Теза 1. Клас функцій, що обчислюються всюди визначеними алгоритмами
без використання оператора while … doспівпадає з класом примітивно
рекурсивних функцій.
Теза 2. Клас функцій, що обчислюються всюди визначеними алгоритмами
співпадає з класом рекурсивних функцій.
Теза 3. Клас функцій, що обчислюються довільними алгоритмами
співпадає з класом частково рекурсивних функцій.
Таким чином, з одного боку ми маємо алгебраїчний терм, як формальну
модель обчислень (алгоритм), з іншого – синтаксичну конструкцію, яка теж є
формальною моделлю обчислень (алгоритмом), але дуже наближеною до мов
програмування. Тобто, якщо обмежитись, наприклад, множиною натуральних
чисел і ввести найпростіші логічні та арифметичні операції, обчислювальні в
рамках класичної обчислювальної парадигми, то можна говорити про побудову
теорії обчислювальності в рамках того чи іншого формалізму.
2. Нечіткі моделі
В бінарній логіці, як відомо, істинність твердження (висловлювання) виводиться
на підставі істинності складових тверджень (висловлювань). Подібне виведення
задається у вигляді схеми: над горизонтальною рискою записуються всі складові
твердження, а під – саме твердження.
В нечіткій логіці [2] використовується узагальнене (нечітке) правило
виведення modus ponens визначається наступною схемою виведення:
Умова Імплікація
x це А
якщо x це A, то y це B
Висновок y це В
де A, AX і B, BX – нечіткі множини, x, y – так звані лінгвістичні змінні,
значеннями яких є нечіткі висловлювання на природній мові. Висновок
нечіткого правила відноситься до деякої нечіткої множини B, яка визначається
композицією нечіткої множини А і нечіткої імплікації АВ, тобто
B = A (АВ).
Олександр Провотар, Олександр Ількун
Категорії як формальні моделі обчислень
100
Нечітка імплікація АВ рівнозначна деякому нечіткому відношенню RXY з
функцією належності R(x,y). Тому функцію належності нечіткої множини В
можна подати у вигляді
' '( ) sup{ ( ) ( , )}
T
B A A B
x X
y x x y
причому AB(x,y)=R(x,y).
3. Арифметика нечітких чисел
В теорії нечітких систем виділяються нечіткі множини, які визначаються на осі
дійсних чисел і є нормальними, випуклими, а також мають неперервні функції
належності. Такі нечіткі множини називається нечіткими числами.
Основні арифметичні операції – сума, різниця, множення і ділення двох
нечітких чисел А1, А2R задаються за допомогою принципу розширення.
Наприклад, cума двох нечітких чисел А1 і А2(позначається А1А2 = В)
обчислюється як
)}(),(min{sup)( 21 21
21
21
xxy AA
xxy
xx
B
.
Натуральні числа в цьому випадку можуть ототожнюватись з нечіткими
трикутними числами.
Алгоритм обчислення довільних функцій над множиою натуральних чисел
може бути описаний наступною синтаксичною конструкцією:
function s(x, y)
begin
if x is (a1, x, b1) and y is (a2, y , b2) then
s is (a1+a2, x+y, b1+b2)
s = x+y
end,
де (a1, x, b1) та (a2, y, b2) – нечіткі трикутні числа, які моделюють натуральні
числа x та y відповідно.
4. Категорії
Нехай – категорія [3] з кінцевим об’єктом 1 і класифікатором підоб’єктів .
Декартово замкнута категорія з класифікатором підоб’єктів називається топосом.
4.1. Логічні функції в топосі. Виходячи з того, що область значень будь-якої
класичної логічної функції – це двохелементна множина 2 = {0,1}, таку функцію
можна розглядати, як характеристичну функцію деякої підмножини її області
визначення. Або, іншими словами, як характеристичну функцію образу деякого
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2023, вип. 37, 98-102
101
мономорфізму. Саме це дозволяє дати визначення логічних функцій за
допомогою діаграм в довільному топосі.
Наприклад, функція кон’юнкції : визначається декартовим
квадратом
тобто є характером добутку морфізмів <true, true>: 1.
Інші логічні функції , та визначаються аналогічно відповідними
декартовими квадратами.
Справедлива
Теорема. Морфізми , , , ведуть себе згідно наступних таблиць:
true false true false true false true false
false true true true false true true false true true true
false false false false true true false true false
4.2. Натурально-числовий об’єкт. Натурально-числовий об’єкт (NNO) – це
об’єкт N разом з парою морфізмів
sO
NN1 таких, що для будь-якого обєкта a
і морфізмів
fx
aa1 існує єдиний морфізм h: Na для якого діаграма
комутує.
Таким чином, натуральне число – це морфізм n:1N в топосах з
натурально-числовим об’єктом.
В топосі з NNO можна визначати арифметичні операції. Зокрема, операція
додавання визначається як єдиний морфізм, для якого діаграма
комутує.
Наприклад, обчислення суми m + 0 натуральних чисел зводиться до
обчислення композицій
Олександр Провотар, Олександр Ількун
Категорії як формальні моделі обчислень
102
m <1N, ON> = m 1N =m.
Переваги останнього підходу до побудови формальних моделей алгоритмів
полягають в тому, що під натурально-числовим об’єктом можна розуміти все що
завгодно, починаючи від класичних моделей в категорії Set і кінчаючи
категорією доведень, об’єкти якої – формули, а морфізми – формальні виведення
одних формул із інших в деякій системі дедуктивного виведення.
Висновки. Оскільки існують категорії нечітких множин, нечітких функцій,
частково рекурсивних функцій, то розглянуті моделі обчислень можна
розглядати в рамках тих чи інших категорій і будувати абстрактну теорію
обчислюваності і відповідні мови програмування на категорній основі. Розробка
мови Нaskell є першим кроком в цьому напрямку.
Література
[1] E. Mendelson. Introduction to Mathematical Logic. D. Van Nostrand Company, INC. – 1975. –
320 p.
[2] L. Rutkowski. Metody i TechnikiSztucznejInteligencji (inPolish). Wydawnictwo Naukove PWN,
Warszava, 2009. – 452 p.
[3] M. Barr, C. Wells. Category Theory for Computing Science. Reprints in Theory and Applications
of Categories, No. 22, 2012.
Categories as formal models of calculations
Oleksandr Provotar, Oleksandr Ilkun
Various formal models of calculations are considered. In particular, recursive functions, fuzzy
models and categorical models. It is shown how functions are calculated based on such models. In
each of these models, the concept of number and basic arithmetic operations are introduced. It is
concluded that the considered formal models of calculations can be represented within certain
categories and an abstract theory of computability and relevant programming languages can be
built on a categorical basis. That is, we are talking about the creation of a universal programming
language in which it would be possible to describe problems from various subject areas by
interpreting them in the appropriate categories with the futher use of a universal categorical
apparatus for their solution. Such a language should be oriented to scientific problems.
Отримано 31.03.23
|
| id | oai:ojs2.www.fmmit.lviv.ua:article-313 |
| institution | Physico-mathematical modeling and informational technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-06-09T01:10:12Z |
| publishDate | 2023 |
| publisher | Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України |
| record_format | ojs |
| resource_txt_mv | wwwfmmitlvivua/49/b6b22d2929e6758a26a07a4702d64c49.pdf |
| spelling | oai:ojs2.www.fmmit.lviv.ua:article-3132025-02-21T17:31:10Z Categories as formal models of calculations Категорії як формальні моделі обчислень Provotar, Oleksandr Ilkun, Oleksandr категорія, нечітка множина, рекурсивна функція Various formal models of calculations are considered. In particular, recursive functions, fuzzy&nbsp;models and categorical models. It is shown how functions are calculated based on such models. In&nbsp;each of these models, the concept of number and basic arithmetic operations are introduced. It is&nbsp;concluded that the considered formal models of calculations can be represented within certain&nbsp;categories and an abstract theory of computability and relevant programming languages can be&nbsp;built on a categorical basis. That is, we are talking about the creation of a universal programming&nbsp;language in which it would be possible to describe problems from various subject areas by&nbsp;interpreting them in the appropriate categories with the futher use of a universal categorical&nbsp;apparatus for their solution. Such a language should be oriented to scientific problems. Розглядаються різні формальні моделі обчислень. Зокрема, рекурсивні функції, нечіткі&nbsp;моделі та категорні моделі. Показано, як обчислюються функції на основі таких моделей. В&nbsp;кожній з цих моделей вводиться поняття числа та основні арифметичні операції.&nbsp;Робиться висновок про те, що розглянуті формальні моделі обчислень можна моделювати&nbsp;в рамках тих чи інших категорій і будувати абстрактну теорію обчислюваності і&nbsp;відповідні мови програмування на категорній основі. Тобто мова йде про створення&nbsp;універсальної мови програмування на якій можна було б описувати задачі з різних&nbsp;предметних областей шляхом їх інтерпретації у відповідних категоріях з подальшим&nbsp;використанням універсального категорного апарату для їх розв’язання. Така мова повинна&nbsp;бути орієнтована на наукові задачі. Інститут прикладних проблем механіки і математики ім. Я. С. Підстригача НАН України 2023-06-27 Article Article application/pdf https://www.fmmit.lviv.ua/index.php/fmmit/article/view/313 PHYSICO-MATHEMATICAL MODELLING AND INFORMATIONAL TECHNOLOGIES; No. 37 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 98-102 ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; № 37 (2023): ФІЗИКО-МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ; 98-102 2617-5258 1816-1545 10.15407/fmmit2023.37 uk https://www.fmmit.lviv.ua/index.php/fmmit/article/view/313/281 Авторське право (c) 2023 Олександр Провотар, Олександр Ількун (Автор) |
| spellingShingle | категорія нечітка множина рекурсивна функція Provotar, Oleksandr Ilkun, Oleksandr Категорії як формальні моделі обчислень |
| title | Категорії як формальні моделі обчислень |
| title_alt | Categories as formal models of calculations |
| 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/313 |
| work_keys_str_mv | AT provotaroleksandr categoriesasformalmodelsofcalculations AT ilkunoleksandr categoriesasformalmodelsofcalculations AT provotaroleksandr kategorííâkformalʹnímodelíobčislenʹ AT ilkunoleksandr kategorííâkformalʹnímodelíobčislenʹ |