Конкретна алгоритміка
Розглядаються питання конкретизації тези Чорча та її застосування в методології обчислюваності. Рассматриваются вопросы конкретизации тезисов Чорча и их применения в методологии вычислимости. The questions of Cherch’s theses specification and its application in the methodology of computability are c...
Gespeichert in:
| Veröffentlicht in: | Компьютерная математика |
|---|---|
| Datum: | 2016 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/168421 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Конкретна алгоритміка / О.І. Провотар, О.О. Провотар // Компьютерная математика. — 2016. — № 2. — С. 87-93. — Бібліогр.: 2 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860260202193879040 |
|---|---|
| author | Провотар, О.І. Провотар, О.О. |
| author_facet | Провотар, О.І. Провотар, О.О. |
| citation_txt | Конкретна алгоритміка / О.І. Провотар, О.О. Провотар // Компьютерная математика. — 2016. — № 2. — С. 87-93. — Бібліогр.: 2 назв. — укр. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Розглядаються питання конкретизації тези Чорча та її застосування в методології обчислюваності.
Рассматриваются вопросы конкретизации тезисов Чорча и их применения в методологии вычислимости.
The questions of Cherch’s theses specification and its application in the methodology of computability are considerеd.
|
| first_indexed | 2025-12-07T18:54:07Z |
| format | Article |
| fulltext |
Компьютерная математика. 2016, № 2 87
Вычислительный
эксперимент
Розглядаються питання конкре-
тизації тези Чорча та її засто-
сування в методології обчислюва-
ності.
О. І. Провотар, О.О. Провотар,
2016
УДК 681.3
О.І. ПРОВОТАР, О.О. ПРОВОТАР
КОНКРЕТНА АЛГОРИТМІКА
Вступ. Всім відома теза Чорча [1, 2] про те,
що клас алгоритмічно обчислюваних функ-
цій співпадає з класом частково рекурсивних
функцій. Клас частково рекурсивних функцій
визначається математично точно. Тому, тезу
можна використовувати як для доведення
алгоритмічної обчислюваності функцій, так і
для доведення того, що функція не є алго-
ритмічно обчислюваною. Для цього треба
лише показати, що така функція належить до
класу частково рекурсивних функцій і в цьо-
му випадку вона є алгоритмічно обчислюва-
ною, або не належить і, відповідно, не є алго-
ритмічно обчислюваною.
Показати алгоритмічну обчислюваність
функцій шляхом її належності до класу част-
ково рекурсивних функцій досить складно,
окрім найпростіших функцій. Крім того,
в кожному конкретному випадку це потребує
побудови математичної моделі функції
у вигляді терма із обчислюваних операцій
над базовими функціями. Базовими
функціями, як відомо, [1, 2] називаються
найпростіші функції o(x) = 0, s(x) = x + 1
та функції-селектори n
mI (x1, … , xn) = xm,
де n m 1.
Основними обчислюваними операціями
будуть операції суперпозиції Sn+1, примітив-
ної рекурсії R та мінімізації M, які задаються
наступними співвідношеннями: операція су-
перпозиції Sn+1 дозволяє із
n-арної функції g(x1, …, xn) та n функцій
g1(x1, … , xm), ... , gn(x1, … , xm), однакової ар-
ності утворити функцію
f(x1, … , xm) = g(g1(x1, … , xm), … ,
gn(x1, … , xm)).
Таку функцію позначають Sn+1(g, g1, … , gn).
O.І. ПРОВОТАР, O.О. ПРОВОТАР
Компьютерная математика. 2016, № 288
Операція примітивної рекурсії R дозволяє із n-арної функції g та n + 2-арної
функції h утворити n + 1-арну функцію f за допомогою наступних спів-
відношень:
f(x1, … , xn, 0) = g(x1, … , xn),
f(x1, … , xn, y + 1) = h(x1, … , xn, y, f(x1, … , xn, y)).
Таку функцію позначають R(g, h).
Операція мінімізації М дозволяє із n-арної функції g утворити n-арну
функцію f, що задається співвідношенням:
f(x1, …, xn) = y(g(x1, …, xn-1, y) = xn).
Тобто, значення функції f(x1, … , xn) дорівнює найменшому y для якого
g(x1, … , xn-1, y) = xn.
Значення функції f(x1, … , xn) вважається невизначеним у випадках:
1) для всіх y значення g(x1, … , xn-1, y) xn;
2) для всіх y < t значення g(x1, … , xn-1, y) визначене і xn, а значення
g(x1, … , xn-1, t) невизначене;
3) значення g(x1, … , xn-1, 0) невизначене.
Таку функцію позначають M(g).
Конкретизації тези Чорча. Відомо [1, 2], що функцію, яку можна отримати
з базових функцій за допомогою скінченної кількості застосувань операцій су-
перпозиції та примітивної рекурсії, називають примітивно рекурсивною
функцією (ПРФ).
Функцію, яку можна отримати з базових функцій за допомогою скінченної
кількості застосувань операцій суперпозиції, примітивної рекурсії та мінімізації,
називають частково рекурсивною функцією (ЧРФ).
Всюди визначену ЧРФ називають рекурсивною функцією (РФ).
Зрозуміло, що оператори суперпозиції, примітивної рекурсії та мінімізації
теж породжують алгоритмічно обчислювані функції із алгоритмічно обчислю-
ваних функцій.
Дійсно, у випадку суперпозиції, якщо ми можемо обчислювати значення
функцій g, g1, … , gn , то значення їх суперпозиції f = Sn+1(g, g1, … , gn) в точці
(a1, …, am) можна обчислити за допомогою наступного алгоритму:
function f(x1, … , xm)
begin
b1 = g1(x1, … , xm)
………………….
bn = gn(x1, … , xm)
b = g (b1, … , bn)
end.
Число b буде значенням функції f в точці (a1, … , am).
У випадку примітивної рекурсії, якщо ми можемо обчислювати значення
функцій g, h, то значення функції f = R(g, h) в точці (a1, … , an, m + 1) може бути
обчислене за допомогою наступного алгоритму:
КОНКРЕТНА АЛГОРИТМІКА
Компьютерная математика. 2016, № 2 89
function f(x1, … , xn, y)
begin
if y = 0 then f = g(x1, … , xn)
else f = h(x1, …, xn, y – 1, f(x1, … , xn, y – 1))
end.
В результаті рекурсивних викликів, отримаємо наступну послідовність чисел:
b0 = g(a1, … , an),
b1 = h(a1, … , an, 0, b0),
b2 = h(a1, … , an, 1, b1),
……………………….. ,
bm+1 = h(a1, … , an, m, bm).
Число bm+1 буде значенням функції f в точці (a1, … , an, m + 1).
У випадку операції мінімізації, якщо ми можемо обчислювати значення
функції g, то значення функції f = M(g) в точці (a1, … , an) може бути обчислене
за допомогою наступного алгоритму
function f(x1, … , xn)
begin
i = 0
while g(x1, … , xn-1, i) xn
do i = i + 1
f = i
end.
Іншими словами, ми послідовно обчислюємо значення
g(a1, … , an, 0),
g(a1, … , an, 1),
… .
Найменше значення a, для якого
g(a1, … , an-1, a) = an
і є значенням функції f в точці (a1, … , an).
Виникає цілком закономірне питання про можливість використання кон-
кретних алгоритмів для доведення фундаментальних результатів теорії рекур-
сивних функцій. Для цього потрібно точно описати основні конструкції алго-
ритму і переформулювати (конкретизувати) тезу Чорча для більш вузьких класів
алгоритмічно обчислюваних функцій.
Домовимося далі записувати алгоритми в мові ПсевдоPaskal, яка є спроще-
ним діалектом мови Paskal. Операторами цієї мови будуть наступні:
<ідентифікатор> = <вираз>,
if <вираз> then <оператор> {<оператор>, … , <оператор>}
else <оператор> {<оператор>, … , <оператор>},
while <вираз> do <оператор> {<оператор>, … , <оператор>},
for <вираз> to <вираз> <оператор> {<оператор>, … , <оператор>}.
O.І. ПРОВОТАР, O.О. ПРОВОТАР
Компьютерная математика. 2016, № 290
Конкретизуємо тезу Черча для класів ПРФ, РФ та ЧРФ відповідно.
1. Клас функцій, що обчислюються всюди визначеними алгоритмами без
використання оператора while … do. Цей клас описується наступним чином:
1) вважатимемо, що найпростіші функції обчислюються всюди визначеними
алгоритмами без використання оператора while … do, а, отже належать
до цього класу;
2) всі функції, які обчислюються всюди визначеними алгоритмами без вико-
ристання оператора while … do і при їх обчисленні використовуються функції,
які обчислюються всюди визначеними алгоритмами без використання оператора
while … do теж відносимо до цього класу.
Таким чином, справедлива наступна
Теза 1. Клас функцій, що обчислюються всюди визначеними алгоритмами
без використання оператора while … do співпадає з класом примітивно рекур-
сивних функцій.
2. Клас функцій, що обчислюються всюди визначеними алгоритмами. Цей
клас описується наступним чином:
1) всі ПРФ належать до цього класу;
2) всі функції, які обчислюються всюди визначеними алгоритмами і при їх
обчисленні використовуються функції, які обчислюються всюди визначеними
алгоритмами теж відносимо до цього класу.
Таким чином, справедлива наступна
Теза 2. Клас функцій, що обчислюються всюди визначеними алгоритмами
співпадає з класом рекурсивних функцій.
3. Клас функцій, що обчислюються довільними алгоритмами. Цей клас опи-
сується наступним чином:
1) всі РФ належать до цього класу;
2) всі функції, які обчислюються довільними алгоритмами і при їх обчис-
ленні використовуються функції, які обчислюються довільними алгоритмами
теж відносимо до цього класу.
Таким чином, справедлива наступна
Теза 3. Клас функцій, що обчислюються довільними алгоритмами співпадає
з класом частково рекурсивних функцій.
Конкретні алгоритми. Покажемо, як доводити алгоритмічну обчислю-
ваність функцій, використовуючи запропоновані вище тези. Нехай, треба дове-
сти, що функція
[ / ], 0
( , )
, 0
x y y
f x y
x y
ПР функція.
Розглянемо послідовність
1y ∸ x, 2y ∸ x, … , [x/y] ∸ x, … , xy ∸ x.
КОНКРЕТНА АЛГОРИТМІКА
Компьютерная математика. 2016, № 2 91
Оскільки частка [x/y] означає скільки разів число y «поміщається» в числі x,
то [x/y] дорівнює числу нулів у цій послідовності. Дійсно, якщо, наприклад,
y два рази «поміщається» в числі x, то
1y ∸ x = 0, 2y ∸ x = 0, а 3y ∸ x 0.
Тому алгоритм обчислення функції наступний:
function f(x, y)
begin
s = 0
if y = 0 then f = x
else {for i = 1 to x
if iy ∸ x = 0 then s = s + 1
f = s}
end.
Отже, функція f(x, y) є ПРФ.
Якщо всі пари натуральних чисел розташувати в послідовність
<0, 0>, <0, 1>, <1, 0>, <0, 2>, <1, 1>, <2, 0>, <0, 3>, … ,
тобто, впорядкувати всі пари так, що пара <x, y> іде раніше за пару <u, v>,
якщо
x + y < u + v,
або якщо
x + y = u + v і x < u,
то співвідношенням
<x, y> n,
де n – номер пари в цій послідовності, задається бієкція між множиною пар
та множиною натуральних чисел.
Така бієкція називається нумерацією Кантора пар чисел і позначається
c(x, y), тобто c(x, y) – це номер пари <x, y> у послідовності Кантора.
Лівий та правий елементи пари <x, y> з номером n визначають функції l(n)
і r(n), які називаються лівою та правою координатними функціями.
Покажемо, що функції с(x, y), l(n), r(n) – ПР функції.
Дійсно, функція с(x, y) обчислюється наступним алгоритмом:
function с(x, y)
begin
s = 0
for i = 0 to (x + y)
s = s + i
for i = 0 to (x + y)
{j = (x + y) ∸ i
if x = i y = j then k = i}
с = s + k
end.
O.І. ПРОВОТАР, O.О. ПРОВОТАР
Компьютерная математика. 2016, № 292
Враховуючи, що l(n) n, r(n) n функція l(n) обчислюється алгоритмом:
function l(n)
begin
for i = 0 to n
for j = 0 to n
if с(i, j) = n then l = i
end,
а функція r(n) обчислюється алгоритмом:
function r(n)
begin
for i = 0 to n
for j = 0 to n
if с(i, j) = n then r = j
end.
Таким чином, с(x, y), l(n) та r(n) – ПР функції.
Графіком функції F(x1, …, xn) [1] називається сукупність (n + 1)-ок вигляду
<x1, …, xn, F(x1, … , xn)>.
Покажемо, що якщо графік Gf всюди визначеної функції f(x1, … , xn) є ре-
курсивно перелічимою множиною [ ], то функція f рекурсивна.
Дійсно, графік Gf – це сукупність (n + 1)-ок вигляду:
<f1(t), … , fn (t), g(t)>,
де fi, g – ПРФ. Тоді значення функції f в довільній точці можна обчислити
за допомогою наступного алгоритму:
function f(x1, … , xn)
begin
i = 0
while f1(i) x1 … fn(i) xn
do i = i +1
f = g(i)
end,
отже, функція f рекурсивна.
Висновки. Таким чином, в статті пропонується підхід, за допомогою якого
належність функцій до класів алгоритмічно обчислюваних можна аргументувати
побудовою відповідних алгоритмів, на відміну від алгебраїчних термів. Він мо-
же бути корисним для програмістів різних вікових категорій, які хочуть позна-
йомитися з основами теорії обчислюваності та теорії алгоритмів, а також сту-
дентам відповідних спеціальностей.
КОНКРЕТНА АЛГОРИТМІКА
Компьютерная математика. 2016, № 2 93
А.И. Провотар, А.А. Провотар
КОНКРЕТНАЯ АЛГОРИТМИКА
Рассматриваются вопросы конкретизации тезисов Чорча и их применения в методологии
вычислимости.
О.I. Provotar, О.O. Provotar
CONCRETE ALGORYTHMICS
The questions of Cherch’s theses specification and its application in the methodology of comput-
ability are considerеd.
1. Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1965. 390 с.
2. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. М.:
Наука, 1987. 288 с.
Одержано 31.08.2016
Про авторів:
Провотар Олександр Іванович,
доктор фізико-математичних наук,
профессор Київського національного університету імені Тараса Шевченка,
professor of the University of Rzeszow (Poland)
Е-mail: aprowata1@bigmir.net
Провотар Олександр Олександрович,
аспірант Київського національного університету імені Тараса Шевченка.
Е-mail: aprovata@gmail.com
|
| id | nasplib_isofts_kiev_ua-123456789-168421 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 2616-938Х |
| language | Ukrainian |
| last_indexed | 2025-12-07T18:54:07Z |
| publishDate | 2016 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Провотар, О.І. Провотар, О.О. 2020-05-01T19:39:51Z 2020-05-01T19:39:51Z 2016 Конкретна алгоритміка / О.І. Провотар, О.О. Провотар // Компьютерная математика. — 2016. — № 2. — С. 87-93. — Бібліогр.: 2 назв. — укр. 2616-938Х https://nasplib.isofts.kiev.ua/handle/123456789/168421 681.3 Розглядаються питання конкретизації тези Чорча та її застосування в методології обчислюваності. Рассматриваются вопросы конкретизации тезисов Чорча и их применения в методологии вычислимости. The questions of Cherch’s theses specification and its application in the methodology of computability are considerеd. uk Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Вычислительный эксперимент Конкретна алгоритміка Конкретная алгоритмика Concrete algorythmics Article published earlier |
| spellingShingle | Конкретна алгоритміка Провотар, О.І. Провотар, О.О. Вычислительный эксперимент |
| title | Конкретна алгоритміка |
| title_alt | Конкретная алгоритмика Concrete algorythmics |
| title_full | Конкретна алгоритміка |
| title_fullStr | Конкретна алгоритміка |
| title_full_unstemmed | Конкретна алгоритміка |
| title_short | Конкретна алгоритміка |
| title_sort | конкретна алгоритміка |
| topic | Вычислительный эксперимент |
| topic_facet | Вычислительный эксперимент |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/168421 |
| work_keys_str_mv | AT provotaroí konkretnaalgoritmíka AT provotaroo konkretnaalgoritmíka AT provotaroí konkretnaâalgoritmika AT provotaroo konkretnaâalgoritmika AT provotaroí concretealgorythmics AT provotaroo concretealgorythmics |