Елементи конкретної алгоритміки: обчислюваність і розв’язність
Розглядається підхід до доведення фундаментальних результатів теорії рекурсивних функцій за допомогою використання конкретних алгоритмів. Для цього точно описуються основні конструкції алгоритму і переформульовується (конкретизується) теза Чорча для більш вузьких класів алгоритмічно обчислюваних фун...
Saved in:
| Date: | 2020 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут програмних систем НАН України
2020
|
| Series: | Проблеми програмування |
| Subjects: | |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/180465 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Елементи конкретної алгоритміки: обчислюваність і розв’язність / О.І. Провотар, О.О. Провотар // Проблеми програмування. — 2020. — № 2-3. — С. 198-207. — Бібліогр.: 5 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-180465 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1804652021-09-30T01:26:50Z Елементи конкретної алгоритміки: обчислюваність і розв’язність Провотар, О.І. Провотар, О.О. Теоретичні та методологічні основи програмування Розглядається підхід до доведення фундаментальних результатів теорії рекурсивних функцій за допомогою використання конкретних алгоритмів. Для цього точно описуються основні конструкції алгоритму і переформульовується (конкретизується) теза Чорча для більш вузьких класів алгоритмічно обчислюваних функцій. За допомогою такого підходу належність функцій до класів алгоритмічно обчислюваних аргументується побудовою відповідних алгоритмів. Рассматривается подход к доказательству фундаментальных результатов теории рекурсивных функций с помощью использования конкретных алгоритмов. Для этого точно описываются основные конструкции алгоритма и уточняется (конкретизируется) тезис Чорча для более узких классов алгоритмически вычислительных функций. С помощью такого подхода принадлежность функций к классам алгоритмически вычислимых аргументируется построением соответствующих алгоритмов. An approach to proving the fundamental results of the theory of recursive functions using specific algorithms is consider. For this, the basic constructions of the algorithm are describing exactly and Church's thesis for more narrow classes of algorithmically computational functions is specified (concretized). Using this approach, the belonging of functions to classes of algorithmically computable is argued by the construction of the corresponding algorithms. 2020 Article Елементи конкретної алгоритміки: обчислюваність і розв’язність / О.І. Провотар, О.О. Провотар // Проблеми програмування. — 2020. — № 2-3. — С. 198-207. — Бібліогр.: 5 назв. — укр. 1727-4907 http://dspace.nbuv.gov.ua/handle/123456789/180465 681.3 DOI: https://doi.org/10.15407/pp2020.02-03.198 uk Проблеми програмування Інститут програмних систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Теоретичні та методологічні основи програмування Теоретичні та методологічні основи програмування |
| spellingShingle |
Теоретичні та методологічні основи програмування Теоретичні та методологічні основи програмування Провотар, О.І. Провотар, О.О. Елементи конкретної алгоритміки: обчислюваність і розв’язність Проблеми програмування |
| description |
Розглядається підхід до доведення фундаментальних результатів теорії рекурсивних функцій за допомогою використання конкретних алгоритмів. Для цього точно описуються основні конструкції алгоритму і переформульовується (конкретизується) теза Чорча для більш вузьких класів алгоритмічно обчислюваних функцій. За допомогою такого підходу належність функцій до класів алгоритмічно обчислюваних аргументується побудовою відповідних алгоритмів. |
| format |
Article |
| author |
Провотар, О.І. Провотар, О.О. |
| author_facet |
Провотар, О.І. Провотар, О.О. |
| author_sort |
Провотар, О.І. |
| title |
Елементи конкретної алгоритміки: обчислюваність і розв’язність |
| title_short |
Елементи конкретної алгоритміки: обчислюваність і розв’язність |
| title_full |
Елементи конкретної алгоритміки: обчислюваність і розв’язність |
| title_fullStr |
Елементи конкретної алгоритміки: обчислюваність і розв’язність |
| title_full_unstemmed |
Елементи конкретної алгоритміки: обчислюваність і розв’язність |
| title_sort |
елементи конкретної алгоритміки: обчислюваність і розв’язність |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2020 |
| topic_facet |
Теоретичні та методологічні основи програмування |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/180465 |
| citation_txt |
Елементи конкретної алгоритміки: обчислюваність і розв’язність / О.І. Провотар, О.О. Провотар // Проблеми програмування. — 2020. — № 2-3. — С. 198-207. — Бібліогр.: 5 назв. — укр. |
| series |
Проблеми програмування |
| work_keys_str_mv |
AT provotaroí elementikonkretnoíalgoritmíkiobčislûvanístʹírozvâznístʹ AT provotaroo elementikonkretnoíalgoritmíkiobčislûvanístʹírozvâznístʹ |
| first_indexed |
2025-07-15T20:28:01Z |
| last_indexed |
2025-07-15T20:28:01Z |
| _version_ |
1837746128696639488 |
| fulltext |
Теоретичні і методологічні основи програмування
© О.І. Провотар, О.О. Провотар, 2020
198 ISSN 1727-4907. Проблеми програмування. 2020. № 2–3. Спеціальний випуск
УДК 681.3 https://doi.org/10.15407/pp2020.02-03.198
ЕЛЕМЕНТИ КОНКРЕТНОЇ АЛГОРИТМІКИ:
ОБЧИСЛЮВАНІСТЬ І РОЗВ’ЯЗНІСТЬ
О.І. Провотар, О.О. Провотар
Розглядається підхід до доведення фундаментальних результатів теорії рекурсивних функцій за допомогою використання
конкретних алгоритмів. Для цього точно описуються основні конструкції алгоритму і переформульовується (конкретизується) теза
Чорча для більш вузьких класів алгоритмічно обчислюваних функцій. За допомогою такого підходу належність функцій до класів
алгоритмічно обчислюваних аргументується побудовою відповідних алгоритмів.
Ключові слова: теза Чорча, розв’язність, універсальна функція.
Рассматривается подход к доказательству фундаментальных результатов теории рекурсивных функций с помощью использования
конкретных алгоритмов. Для этого точно описываются основные конструкции алгоритма и уточняется (конкретизируется) тезис
Чорча для более узких классов алгоритмически вычислительных функций. С помощью такого подхода принадлежность функций к
классам алгоритмически вычислимых аргументируется построением соответствующих алгоритмов.
Ключевые слова: тезис Чорча, разрешимость, универсальная функция.
An approach to proving the fundamental results of the theory of recursive functions using specific algorithms is consider. For this, the basic
constructions of the algorithm are describing exactly and Church's thesis for more narrow classes of algorithmically computational functions
is specified (concretized). Using this approach, the belonging of functions to classes of algorithmically computable is argued by the
construction of the corresponding algorithms.
Key words: Church thesis, solvability, universal function.
Вступ
Всім відома теза Чорча [1–3] про те, що клас алгоритмічно обчислюваних функцій співпадає з класом
частково рекурсивних функцій. Клас частково рекурсивних функцій визначається математично точно. Тому,
тезу можна використовувати як для доведення алгоритмічної обчислюваності функцій, так і для доведення
того, що функція не є алгоритмічно обчислюваною. Для цього треба лише показати, що така функція належить
до класу частково рекурсивних функцій і в цьому випадку вона є алгоритмічно обчислюваною, або не належить
і, відповідно, не є алгоритмічно обчислюваною.
Показати алгоритмічну обчислюваність функцій шляхом її належності до класу частково рекурсивних
функцій досить складно, окрім найпростіших функцій. Крім того, в кожному конкретному випадку це потребує
побудови математичної моделі функції у вигляді терма із обчислюваних операцій над базовими функціями.
Базовими функціями, як відомо [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).
Виникає цілком закономірне питання про можливість використання конкретних алгоритмів для
доведення фундаментальних результатів теорії рекурсивних функцій без побудови відповідних
обчислювальних термів. Або, іншими словами, розповісти мовою, зрозумілою для програмістів, про основні
результати теорії алгоритмів (рекурсивних функцій), зокрема про проблеми обчислюваності та розв’язності.
Отже, мета роботи полягає у тому, щоб запропонувати підходи і засоби для вирішення поставленої проблеми.
Для цього пропонується точно описати основні конструкції алгоритму і переформулювати (конкретизувати)
тезу Чорча для більш вузьких класів алгоритмічно обчислюваних функцій.
Конкретизація поняття алгоритму
Далі алгоритми будемо визначати як синтаксично правильні конструкції в мові ПсевдоPasсal, яка є
спрощеним діалектом мови Pasсal. Операторами цієї мови будуть наступні:
<ідентифікатор> = = <слово>,
<оператор> = = <ідентифікатор> = <арифметичний вираз>
Теоретичні і методологічні основи програмування
199
<оператор> = = if <відношення> then <оператор> else <оператор>
<оператор> = = while < відношення > do {<оператор>, … , <оператор>}
<оператор> = = for < відношення > to < відношення > {<оператор>, … , <оператор>}
Конкретизуємо тезу Чорча для класів ПРФ, РФ та ЧРФ відповідно.
1. Клас функцій, що обчислюються всюди визначеними алгоритмами без використання оператора
while … do. Цей клас описується наступним чином:
- вважатимемо, що найпростіші функції
o(x) = 0,
s(x) = x + 1 та функції-селектори
n
mI (x
1
, … , x
n
) = x
m
, де n m 1
обчислюються всюди визначеними алгоритмами без використання оператора while … do, а, отже належать до
цього класу;
- всі функції, які обчислюються всюди визначеними алгоритмами без використання оператора
while … do і при їх обчисленні використовуються допоміжні функції, які обчислюються всюди визначеними
алгоритмами без використання оператора while … do теж відносимо до цього класу. Таким чином, справедлива
наступна.
Теза 1. Клас функцій, що обчислюються всюди визначеними алгоритмами без використання оператора
while … do співпадає з класом примітивно рекурсивних функцій.
2. Клас функцій, що обчислюються всюди визначеними алгоритмами. Цей клас описується наступним
чином:
- всі ПРФ належать до цього класу;
- всі функції, які обчислюються всюди визначеними алгоритмами і при їх обчисленні
використовуються функції, які обчислюються всюди визначеними алгоритмами теж відносимо до цього класу.
Таким чином, справедлива наступна.
Теза 2. Клас функцій, що обчислюються всюди визначеними алгоритмами співпадає з класом
рекурсивних функцій.
3. Клас функцій, що обчислюються довільними алгоритмами. Цей клас описується наступним чином:
- всі РФ належать до цього класу;
- всі функції, які обчислюються довільними алгоритмами і при їх обчисленні використовуються
функції, які обчислюються довільними алгоритмами теж відносимо до цього класу. Таким чином, справедлива
наступна.
Теза 3. Клас функцій, що обчислюються довільними алгоритмами співпадає з класом частково
рекурсивних функцій.
Обчислюваність
Покажемо, як доводити алгоритмічну обчислюваність функцій, використовуючи запропоновані вище
тези. Нехай, треба довести, що функція
0,
0],/[
),(
yx
yyx
yxf
ПР функція.
Розглянемо послідовність
1y ∸ x, 2y ∸ x, … , [x/y] ∸ x, … , xy ∸ x.
Оскільки частка [x/y] означає скільки разів число y “поміщається” в числі x, то [x/y] дорівнює числу нулів в цій
послідовності. Дійсно, якщо, наприклад, y два рази “поміщається” в числі x, то
1y ∸ x = 0, 2y ∸ x = 0, а 3y ∸ x 0.
Тому алгоритм обчислення функції наступний:
Теоретичні і методологічні основи програмування
200
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.
Враховуючи, що 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
Теоретичні і методологічні основи програмування
201
if с(i, j) = n then r = j
end.
Таким чином, с(x, y), l(n) та r(n) – ПР функції.
Покажемо, що функція
f(x) = [ex]
є ПРФ.
Дійсно, справедлива нерівність
xS
n
< ex < x(S
n
+ 1/n!n),
де
e = 1 + 1/1! + 1/2! + … + 1/n! + /n!n, 0 < <1,
S
n
= 1 + 1/1! + 1/2! + … + 1/n!.
Оскільки
0))!/1((lim
nn
n
SxnnSx , то
0)][)]!/1([ nn SxnnSx для деякого n, тобто
)][)]!/1([ nn SxnnSx для деякого n.
Отже, для того, щоб знайти значення [ex], треба знайти мінімальне n, для якого виконується попередня
рівність і покласти
[ex] = [хSn].
Графіком функції F(x1, …, xn) [1–3] називається сукупність (n + 1)-ок виду <x1, …, xn, F(x1, … , xn)>.
Покажемо, що якщо графік Gf всюди визначеної функції f(x1, … , xn) є рекурсивно перелічимою множиною
[1–3], то функція 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 рекурсивна.
Фундаментальні результати теорії алгоритмів
Нехай – система часткових одномісних функцій. Часткова функція F(x, y) від двох змінних
називається універсальною для сімейства , якщо виконуються наступні умови:
- для кожного фіксованого i функція F(i, y) належить ;
- для кожної функції f(y) із існує таке число i, що для всіх y F(i, y) = f(y).
Теоретичні і методологічні основи програмування
202
Відомо [ ], що для класу одномісних ЧРФ існує універсальна ЧРФ Кліні K(n, x). Відображення, яке
кожному натуральному числу n ставить у відповідність одномісну ЧРФ K(n, x) називати нумерацією Кліні
одномісних ЧРФ. Число n називається клінівським номером функції K(n, x), яка також позначається Kn.
Справдлива також теорема Райса про те, що множина А клінівських номерів функцій, що належать до
непустого сімейство одномісних ЧРФ, відмінних від сукупності всіх таких функцій, не може бути рекурсивною.
Ця теорема використовується для обгрунтування результатів про алгоритмічну обчислюваність функцій.
Наприклад, покажемо, що функція
1, ( , ) 1
( )
0, в інших випадках
x x
f x
K
не є алгоритмічно обчислювальною.
Для цього розглядається множина M = {n0, n1, … } клінівських номерів ЧРФ K(n0, x), K(n1, x), … таких,
що K(n0, n0) = 1, K(n1, n1) = 1, … . За теоремою Райса множина М є нерекурсивною. Припустимо, що існує
алгоритм
function f(x)
begin
. . . . . .
f = . . .
end,
який обчислює функцію f(x). Тоді множина М буде рекурсивною. А це не так.
Алгоритмічна розв’язність. Розглянемо проблеми, для розв’язання яких не існує алгоритмів. Такі
проблеми будемо називати алгоритмічно нерозв’язними.
Однією з таких алгоритмічно нерозв’язних проблем є проблема зупинки [1, 3, 5] яка полягає у
наступному: треба дати відповідь на питання про те, чи існує алгоритм, виходом якого для довільної пари x, y
вхідних натуральних чисел є 0, якщо K(x, y) визначена і 1, якщо K(x, y) невизначена. Існування такого
алгоритму еквівалентне існуванню алгоритму виходом якого для довільної пари x, y вхідних натуральних чисел
є 0, якщо алгоритм обчислення ЧРФ f з клінівським номером x зупиняється на вході y і 1, якщо алгоритм
обчислення ЧРФ f з клінівським номером x на вході y працює нескінченно довго. Саме тому ця проблема
називається проблемою зупинки.
Теорема 1. Проблема зупинки алгоритмічно нерозв’язна.
Доведення. Випливає з того, що область визначення функції K(x, y) є нерекурсивною РПМ.
Іншою алгоритмічно нерозв’язною проблемою є проблема належності яка полягає в наступному: треба
дати відповідь на питання про те, чи існує алгоритм, виходом якого для довільної пари x, y вхідних натуральних
чисел є 0, якщо x y і 1, якщо x y.
Теорема 2. Проблема належності є алгоритмічно нерозв’язною.
Доведення. Дійсно, розв’язність проблеми належності означає рекурсивність множини пар <x, y> для
яких рівняння K(x, t) = y має розв’язок. А це не так.
Універсальні числові множини. Універсальною числовою множиною [4] будемо називати множину U
пар чисел (i, x) таких, що K(i, x) = 1, тобто
U = {(i, x), K(i, x) = 1}.
Теорема 3. Проблема належності до універсальної числової множини є алгоритмічно нерозв’язною.
Доведення. Дійсно, розв’язність цієї проблеми означає, що характеристична функція
U(i, x) =
1),(,0
1),(,1
xi
xi
K
K
є рекурсивною. Покажемо, що це не так. Дійсно, якби ця функція була рекурсивною, то функція f(x), яка
обчислюється алгоритмом
Теоретичні і методологічні основи програмування
203
function f(x)
begin
i := 0
while U(x, x) = 1 do
i := i + 1
f := 1
end,
буде ЧРФ, а, отже, f(x) = K(n, x), для деякого n. Обчислимо цю функцію для x = n.
Якщо U(n, n) = 1, то це означає, з одного боку, що K(n, n) не визначена (f(n) = K(n, n)). З іншого боку,
оскільки U(n, n) = 1 K(n, n) = 1, то K(n, n) – визначена.
Якщо U(n, n) 1, то це означає, з одного боку, що K(n, n) визначена і K(n, n) = 1. З іншого боку
K(n, n) 1.
Універсальні словарні множини. Нехай = {a1, …, an} – алфавіт. Кожну граматику над алфавітом
можна подати словом в алфавіті N, де N = { S, , , *}. Наприклад, граматику G з продукціями
{S aABb|Bbb, Bb C, AC aac} можна подати словом
A1A2 … A4,
де A1 = S a SSb, A2 = S Sbb, A3 = Sb S, A4 = SS aac.
Множину всих таких слів будемо називати базою.
Універсальною словарною множиною [4] будемо називати множину V слів A1A2 … Anw таких, що
слово w виводиться в граматиці G з продукціями A1, A2, … , An, тобто
V = {A1A2 … Anw, S G w}.
Зрозуміло, що кожна граматика G породжує РПМ – множину всих слів, які виводяться граматиці. Тому,
універсальна словарна множина – це множина слів A1A2 … Anw таких, що w належить РПМ, яка
породжується граматикою з продукціями A1, A2, … , An, тобто
V = {A1A2 … Anw, w РПМ, яка породжується G}.
Занумеруємо символи алфавіту N, числами 1, 2, …, p = n+4. Номером пустого слова є число 0.
Номером довільного слова
01
... iii bbb
m
в алфавіті N, називається число
(w) = i0 + i1p + … + impm.
Символом (n) будемо позначати слово з номером n. Так як при фіксованому p кожне додатнє число n
можна подати одним і лише одним способом у вигляді
n = i0 + i1p + … + impm (1 ik m),
то кожне число є номером одного і тільки одного слова множини ( N)*.
Довільну часткову функцію F:( N)* ( N)* будемо називати частковою словарною функцією в
алфавіті N. Часткова числова функція f:NN називається функцією, що представляє словарну функцію F в
нумерації , якщо
F((x)) = (f(x)).
Зрозуміло, що для кожної часткової словарної функції існує єдина часткова числова функція, яка
представляє словарну функцію і кожна часткова числова функція представляє єдину словарну функцію.
Часткова словарна функція F називається примітивно рекурсивною, рекурсивною або частково
рекурсивною, якщо такою є часткова числова функція f, яка її представляє. Те ж саме стосується і ПРМ,
РМ, РПМ.
Так як множина V є РПМ, то існує алгоритм, який по довільному вхідному слову A1A2 … Anw V
видає 1, якщо слово w породжується граматикою з продукціями з бази A1A2 … An. Тоді буде існувати
Теоретичні і методологічні основи програмування
204
алгоритм, який по номеру (A1A2 … Anw) видає 1, якщо слово w породжується граматикою з продукціями
з бази A1A2 … An. Цей алгоритм обчислює ЧРФ g(x). Припустимо, що ця функція рекурсивна, тобто
Vx
Vx
xg
)(,0
)(,1
)(
.
Оскільки множина слів V є РПМ, то існує граматика з продукціями B1, B2, … , Bk, яка породжує цю множину.
Утворимо слово
B1B2 … BkA1A2 … Anw
і знайдемо значення функyції g(n), де n = (B1B2 … BkA1A2 … Anw).
Якщо g(n) = 1, то (n) V. Але це слово відмінне від кожного слова з V, а, отже, (n) V.
Якщо g(n) = 0, то (n) V. Але слово A1A2…Anw породжується граматикою з продукціями
B1, B2, …, Bk, а, отже, (n) V.
В обох випадках отримуємо суперечність, а тому функція g(x) не може бути рекурсивною.
Тому, справедлива теорема.
Теорема 4. Проблема належності до універсальної словарної множини є алгоритмічно нерозв’язною.
Доведення. Якби ця проблема була алгоритмічно розв’язною, то функція g(x) була б рекурсивною, а
це не так.
Проблема відповідностей Поста. Розглянемо ще один приклад алгоритмічно нерозв’язної проблеми на
словах. Вона називається проблемою відповідностей Поста (ПВП) [4].
Нехай
P = {(v1, w1), (v2, w2), … , (vn, wn)}
множина пар слів в алфавіті . Говорять, що множина пар слів має розв’язок, якщо існує така послідовність
),(,...),,(),,(
2211 kk iiiiii wvwvwv
пар слів, що
kk iiiii wwwvvvi ......
2121
,
тобто слово, утворене лівими координатами послідовності пар співпадає зі словом, утвореним правими
координатами послідовності пар.
ПВП полягає в тому, щоб дати відповідь на питання про існування алгоритму, виходом якого для
довільної вхідної множини P пар слів є 0, якщо P має розвязок і 1, якщо P не має розв’язку.
Теорема 5. Проблема відповідностей Поста алгоритмічно нерозв’язна.
Доведення. За довільною словом A1A2 … Anw універсальної словарної множини будуємо ПВП
згідно наступних правил:
- пару (FS, F), де F – спеціальний символ, додаємо до множини пар слів;
- для кожного символа a алфавіту до множини пар слів додаємо пари (a, a);
- для кожного не термінального символа S, S, …, S… до множини пар слів додаємо пари (S, S),
(S, S), …, (S…, S…);
- для слова w до множини пар слів додаємо пару (E, wE), де E – спеціальний символ;
- для кожної продукції Ai = u v до множини пар слів додаємо пару (v, u);
- до множини пар слів додаємо пару (, ).
Можна показати, що справедливе співвідношення:
A1A2 … Anw V множина пар має розв’язок.
Тому, якщо проблема відповідностей Поста алгоритмічно розв’язна, то алгоритмічно розв’язною буде і
проблема належності до універсальної словарної множини. А це не так.
Теоретичні і методологічні основи програмування
205
Нерозв’язність в класі КВ-граматик (проблема неоднозначності). Ця проблема полягає у тому, щоб
дати відповідь на питання про існування алгоритму, виходом якого для довільної вхідної КВ-граматики G є 0,
якщо G неоднозначна і 1 в іншому випадку.
Нехай
Q = {(v1, w1), (v2, w2), … , (vn, wn)}
множина пар слів в алфавіті . Для множини A = {v1, v2, … , vn} лівих компонент елементів з Q будуємо
КВ-граматику GA з одним не терміналом А та множиною термінальних символів I, де I = {a1, a2, … , an},
причому I = . Алфавіт I називається алфавітом індексних символів. Продукції граматики GA мають
наступний вигляд:
A v1Aa1 v2Aa2 … vnAan v1a1 v2a2 … vnan.
Ця граматика породжує мову
}...,,1,......{)( 111
niiaaGL miiiiA mm
.
Аналогічно для множини B = {w1, w2, … , wn} правих компонент з Q будуємо КВ-граматику GB з одним не
терміналом B та множиною продукцій
B w1Ba1 w2Ba2 … wnBan w1a1 w2a2 … wnan.
Ця граматика породжує мову
}...,,1,......{)( 111
niiaawwGL miiiiB mm
.
Утворимо граматику
GAB = ({S, A, B}, {a1, a2, … , an}, P(GA) P(GB), S).
Cправедлива наступна
Теорема 6. Граматика GAB неоднозначна Q має розв’язок.
Доведення (достатність). Нехай i1, …, im – розв’язок множини пар слів Q. Розглянемо два виведення в
граматиці GAB:
1 1 1 2 2 1 1 2 2 1
... ... ...
m mi i i i i i i i i i i iS A Aa Aa a a a a ,
1 1 1 2 2 1 1 2 2 1
... ... ...
m mi i i i i i i i i i i iS B w Ba w w Ba a w w w a a a .
Так як i1, …, im – розв’язок, то
1 2 1 2
... ...
m mi i i i i iw w w ,
тобто ці два виведення породжують одне і теж слово. Оскільки ці виведення різні, то граматика GAB
неоднозначна.
(Необхідність). Для даного термінального слова існує не більше одного виведення в граматиці GA і не
більше одного виведення в граматиці GB. Тому, термінальне слово може мати два різні виведення тільки в тому
випадку, якщо одне з них починається з S A і продовжується виведенням в граматиці GA, а інше починається
з S B і продовжується виведенням в граматиці GB.
Таке слово має закінчення і символів
1
...
mi ia a для деякого m 1. Так як
1 2 1 2
... ...
m mi i i i i iw w w ,
то i1, …, im – розв’язок.
Теорема 7. Проблема неоднозначності КВ-граматик алгоритмічно нерозв’язна.
Теоретичні і методологічні основи програмування
206
Доведення. Якби проблема неоднозначносі була б розв’язною, то була б розв’язною і ПВП. А це не так.
Теорема 8. Проблема
L(G1) L(G2) =
алгоритмічно нерозв’язна.
Доведення. Розглянемо довільну ПВП в афавіті і побудуємо КВ-граматики GA та GB. Так як
L(GA) L(GB) – множина розв’язків ПВП, то
L(GA) L(GB) = ПВП не має розв’язку.
Отже, якби ця проблема була розв’язною для довільних G1 та G2, то була б розв’язною і ПВП. А це не так.
Теорема 9. Проблема
L(G1) = L(G2)
алгоритмічно нерозв’язна.
Доведення. Покажемо, що )( AGL – КВ-мова. Дійсно, існує алгоритм, який за довільним вхідним словом
в алфавіті I дає відповідь на питання про належність цього слова до мови )( AGL . Він грунтується на тому,
що таке слово повинно завершувать множиною індексних символів
1
... ,
mi ia a причому префікс цього слова
повинен бути словом
1
... .
mi i Якщо це не так, то вхідне слово не належить до )( AGL . Тому існує алгоритм,
який за довільним вхідним словом в алфавіті I дає відповідь на питання про належність цього слова до
мови )( AGL . Отже, ця мова є РПМ, тобто, породжується КВ-граматикою.
Розглянемо довільну ПВП в афавіті і побудуємо КВ-граматики G1 та G2, які породжують мови
BA LL та *( )Σ I відповідно, де I, як і раніше – алфавіт індексних символів. Але справедливе
співвідношення
A B A BL L L L .
Тому в L(G1) відсутні слова, які є розв’язками ПВП. Мова L(G2) містить всі слова із *)( IΣ . Тому,
L(G1) і L(G2) співпадають коли ПВП не має розв’язку.
Звідси випливає, що якби проблема еквівалентності для КВ-мов була б алгоритмічно розв’язною, то була б
розв’язною і ПВП. А це не так.
Теорема 10. Проблема L(G1) L(G2) – алгоритмічно нерозв’язна.
Доведення. Нехай G1 – КВ-граматика, яка породжує мову ( I)* і G2 – КВ-граматика, яка породжує
мову BA LL , де I – алфавіт індексних символів. Тоді справедливе співвідношення
L(G1) L(G2)
A B
L L = ( I)*.
Тобто, L(G1) L(G2) коли ПВП не має розв’язку. Звідси випливає, що якби проблема включення для КВ-мов
була б алгоритмічно розв’язною, то була б алгоритмічно розв’язною і ПВП. А це не так.
Висновки
Таким чином, в статті пропонується підхід, за допомогою якого належність функцій до класів
алгоритмічно обчислюваних можна аргументувати побудовою відповідних алгоритмів, на відміну від
алгебраїчних термів. Він може бути корисним для програмістів різних вікових категорій, які хочуть
познайомитися з основами теорії обчислюваності та теорії алгоритмів, а також студентам відповідних
спеціальностей.
Теоретичні і методологічні основи програмування
207
Слід також зазначити, що запропонований підхід на основі конкретизації тези Чорча дозволяє досягти
більш зрозумілого формулювання різних задач та процесів їх розв’язання. Це досягається в першу чергу за
рахунок так званих макрооператорів мови ПсевдоPasсal для реалізації найпростіших механічних операцій.
Література
1. Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука. 1965. 390 с.
2. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. М.: Наука. 1987. 288 с.
3. Провотар О.І. Конкретна алгоритміка. Київ. Наукова думка. 2017. 168 с.
4. Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. М: “Вильямс”, 2002. 528 с.
5. Нікітченко М.С., Шкільняк С.С. Математична логіка та теорія алгоритмів. К.: ВПС “Київський університет”, 2008. 528 с.
References
1. Maltsev A.I. Algorithms and recursive functions. M.: Science. 1965.390 p.
2. Uspensky V.A., Semenov A.L. Algorithm theory: basic discoveries and applications. M.: Science. 1987. 288 p.
3. Provotar O.І. The algorithm is specific. Kiev. Naukova dumka. 2017.168 p.
4. Hopcroft D., Motvani R., Ullman D. Introduction to the theory of automata, languages and computations. M: “Williams”, 2002. 528 p.
5. Nikitchenko M.S., Shkilnyak S.S. Mathematical logic and theory of algorithms. К.: VPS “Kiev University”, 2008. 528 p.
Одержано 10.03.2020
Про авторів:
Провотар Олександр Іванович,
доктор фізико-математичних наук, професор, професор.
Кількість наукових публікацій в українських виданнях – 100.
Кількість наукових публікацій в зарубіжних виданнях – 30.
Індекс Гірша – 4.
http://orcid.org/0000-0002-6556-3264, м.т. +38-050-444-17-35, email: aprowata1@bigmir.net.
Провотар Ольга Олександрівна,
кандидат фізико-математичних наук,
молодший науковий співробітник.
Кількість наукових публікацій в українських виданнях – 10.
Кількість наукових публікацій в зарубіжних виданнях – 1.
http://orcid.org/0000-0002-6591-3615, email: provotar@huspi.com.
Місце роботи авторів:
Київський національний університет імені Тараса Шевченка,
03187, Київ-187, Проспект Академіка Глушкова, 2, к. 6.
Тел.: (044) 259 0511.
Факс: (044) 259 7044.
E-mail: aprowata1@bigmir.net.
Інститут кібернетики імені В.М. Глушкова НАН України,
03680, МСП, Київ-187, проспект Академіка Глушкова, 40.
Тел.: (044) 259 0511.
Факс: (044) 259 7044.
E-mail: provotar@huspi.com.
mailto:aprowata1@bigmir.net
|