Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій (реферат)

Реферат на тему:

Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій.

1. МАШИНИ З НАТУРАЛЬНОЗНАЧНИМИ РЕГІСТРАМИ Машина з натуральнозначними регiстрами (скорочено МНР) є iдеалiзованою моделлю комп’ютера. МНР мiстить, взагалі кажучи, нескiнченну кiлькiсть регiстрiв, вмiстом яких є натуральнi числа. Регiстри нумеруємо натуральними числами, починаючи з 0, позначаючи їх R0, R1, …, Rn, … Вмiст регiстру Rn позначаємо 'Rn .

Послiдовнiсть ('R0, 'R1, …, 'Rn, …) вмiстiв регiстрiв МНР назвемо конфiгурацiєю МНР.

МНР може змiнити вмiст регiстрiв згiдно виконуваної нею команди. Скiнченний список команд утворює програму МНР. Команди програми послiдовно нумеруємо натуральними числами, починаючи з 1. Номер команди в програмі називатимемо адресою команди. МНР-програму з командами I1, I2 ,…, Ik будемо позначати I1I2… Ik. Довжину (кiлькiсть команд) МНР-програми P позначимо |P|.

Команди МНР бувають 4-х типiв.

Тип 1. Обнулення n-го регiстру Z (n): 'Rn :

Тип 2. Збiльшення вмiсту n-го регiстру на 1 S (n): 'Rn :+1.

Тип 3. Копіювання вмісту регістру T (m, n): 'Rn :

(при цьому 'Rm не змiнюється).

Тип 4. Умовний перехiд J (m, n, q): якщо 'Rn ='Rm, то перейти до виконання q-ї команди, iнакше виконувати наступну за списком команду програми.

Число q в команді J (m, n, q) назвемо адресою переходу.

Команди типiв 1−3 називають арифметичними. Пiсля виконання арифметичної команди МНР повинна виконувати наступну за списком команду програми.

Виконання однiєї команди МНР назвемо кроком МНР.

Зауважимо, що формальними моделями алгоритмів є саме МНР-програми, поняття МНР використовується для опису функціонування МНР-програм.

Виконання програми МНР починає, перебуваючи в деякiй початковiй конфiгурацiї, з виконання 1-ї за списком команди. Наступна для виконання команда програми визначається так, як описано вище. Виконання програми завершується (програма зупиняється), якщо наступна для виконання команда вiдсутня (тобто номер наступної команди перевищує номер останньої команди програми). Конфiгурацiя МНР в момент завершення виконання програми називається фiнальною, вона визначає результат роботи МНР-програми над даною початковою конфiгурацiєю.

Якщо МНР-програма P при роботi над початковою конфiгурацiєю (a0, a1, …) нiколи не зупиняється, цей факт позначаємо P (a0, a1, …)якщо ж коли-небудь зупиниться, цей факт позначаємо P (a0, a1,…)Якщо МНР-програма P при роботi над початковою конфiгурацiєю (a0, a1, …) зупиняється iз фiнальною конфiгурацiєю (b0, b1, …), цей факт позначатимемо так: P (a0, a1, …), b1, …).

МНР-програми як моделі алгоритмів є фінітними об'єктами, тому обмежимося розглядом скінченних конфігурацій. Конфiгурацiю вигляду (a0, a1, …, aп, 0, 0, …), в якiй 'Rm= 0 для всiх m>n, назвемо скiнченною. Таку конфігурацію позначаємо (a0, a1, …, an). Зрозуміло, що якщо МНР-програма P починає роботу над скiнченною початковою конфiгурацiєю, то в процесi виконання P МНР перебуватиме тiльки в скiнченних конфiгурацiях.

МНР-програми P та Q назвемо еквiвалентними, якщо при роботi над однаковими початковими конфiгурацiями вони або обидві зупиняються з однаковими фiнальними конфiгурацiями, або обидвi не зупиняються.

МНР-програма P обчислює часткову n-арну функцiю f: Nп->N, якщо f (a1, a2, …, aп)=b (a1, a2, …, aп)…).

Замiсть P (a1, a2 ,…)…) надалі будемо писати P (a1, a2 ,…)/p>

Функцiю f: Nп->N називають МНР-обчислюваною, якщо iснує МНР-програма, яка обчислює цю функцiю.

Кожна МНР-програма обчислює безліч функцій, заданих на N, але, зафіксовуючи наперед арність функцій (тобто кількість компонент початкових конфігурацій), отримуємо, що кожна МНР-програма обчислює єдину функцію заданої арності.

Зауважимо, що кожну функцiю, задану на N, можна трактувати як предикат, інтерпретуючи значення 1 та 0 як істиннісні значення «Т» та «F» відповідно. В цьому випадку в ролі предикату виступає його характеристична функція.

Розглянемо приклади МНР-програм для функцій та предикатів.

Приклад 1. МНР-програма для всюди невизначеної функції:

1. 1)J (0,0,1).

Приклад 2. МНР-програма для предикату «x=y» :

1. 1)J (0,1,3).

2. 2)J (0,0,4).

3. 3)S (2).

4. 4)T (2,0).

Приклад 3. МНР-програма для функцiї f (x, y)=x+y:

1. 1)J (1,2,5).

2. 2)S (0).

3. 3)S (2).

4. 4)J (0,0,1).

Приклад 4. МНР-програма для функцiї f (x)=2x:

1. 1)T (0,1).

2. 2)J (1,2,6).

3. 3)S (0).

4. 4)S (2).

5. 5)J (0,0,2).

Приклад 5. МНР-програма для функцiї f (x, y)=x-y:

1. 1)J (0,1,5).

2. 2)S (1).

3. 3)S (2).

4. 4)J (0,0,1).

5. 5)Т (2,0).

Приклад 6. МНР-програма для функцiї f (x, y)= $$\begin{array}{c}x\stackrel{}{-}y\\ \end{array}$$.

1. 1)J (0,1,7).

2. 2)J (0,2,6).

3. 3)S (1).

4. 4)S (2).

5. 5)J (0,0,1).

6. 6)Z (2).

7. 7)Т (2,0).

Приклад 7. МНР-програма для функцiї f (x, y)=max (x, y):

1. 1)J (0,2,5).

2. 2)J (1,2,6).

3. 3)S (2).

4. 4)J (0,0,1).

5. 5)Т (1,0).

Приклад 8. МНР-програма для функцiї f (x)=x/2:

1. 1)J (0,2,6).

2. 2)S (2).

3. 3)S (2).

4. 4)S (1).

5. 5)J (0,0,1).

6. 6)Т (1,0).

Приклад 9. МНР-програма для функцiї f (x)=[x/2]:

1. 1)J (0,2,7).

2. 2)S (2).

3. 3)J (0,2,7).

4. 4)S (2).

5. 5)S (1).

6. 6)J (0,0,1).

7. 7)Т (1,0).

Приклад 10. МНР-програма для функцiї f (x)=sg (x):

1. 1)J (0,1,4).

2. 2)Z (0).

3. 3)S (0).

Приклад 11. МНР-програма для функцiї f (x, y)=x/p>

1. 1)J (3,1,9).

2. 2)J (0,2,6).

3. 3)S (2).

4. 4)S (4).

5. 5)J (0,0,2).

6. 6)Z (2).

7. 7)S (3).

8. 8)J (0,0,1).

9. 9)Т (4,0).

2. МАШИНИ ТЬЮРIНГА Пiд (детермінованою) машиною Тьюрiнга (скорочено МТ) будемо розумiти впорядковану 5-ку (Q, T,0, q*), де:

Q скiнченна множина внутрiшнiх станiв;

T кiнченний алфавiт символiв стрiчки, причому T мiстить спецiальний символ порожньої клiтки p>

Q->QL, днозначна функцiя переходiв;

q0очатковий стан;

q*iнальний стан.

Функцiю переходiв на практицi задають скiнченною множиною команд одного з 3-х видiв: qa, qa та qa де p, q a, bQ При цьому, як правило, не для всiх пар (q, a) iснує команда з лiвою частиною qa. Це означає, що функцiя не є тотальною. Проте зручніше вважати функцію тотальною, тому для всiх пар (q, a) неявно (не додаючи вiдповiднi команди вигляду qa, вводимо довизначення a)=(q, a,/p>

Неформально МТ складається з скiнченної пам’ятi, роздiленої на клiтки нескiнченної з обох бокiв стрiчки та голiвки читання-запису. В кожнiй клiтцi стрiчки мiститься єдиний символ iз T, причому в кожен даний момент стрiчка мiстить скiнченну кiлькiсть символiв, вiдмiнних вiд символа Голiвка читання-запису в кожен даний момент оглядає єдину клiтку стрiчки.

Якщо МТ знаходиться в станi q та голiвка читає символ a, то при виконаннi команди qa (команди qa, команди qa МТ переходить в стан p, замiсть символу a записує на стрiчцi символ b та змiщує голiвку на 1 клiтку направо (відповідно на 1 клiтку налiво, залишає голiвку на мiсцi).

Конфiгурацiя, або повний стан МТ е слово вигляду xqy, де x, y q Неформально це означає, що на стрiчцi записане слово xy, тобто злiва i справа вiд xy можуть стояти тiльки символи МТ знаходиться в станi q, голiвка читає 1-й символ пiдслова y.

Конфiгурацiю вигляду q0x, де 1-й та останнiй символи слова x вiдмiннi вiд називають початковою. Конфiгурацiю вигляду xq*y називають фiнальною. Пiсля переходу до фiнального стану, отже, до фiнальної конфiгурацiї, МТ зупиняється.

Нехай МТ знаходиться в конфiгурацiї xcqay, де x, y a, c q Пiсля виконання команди qa (команди qa, команди qa МТ перейде до конфiгурацiї xcbpy (вiдповiдно до конфiгурацiї xpcby, конфiгурацiї xcpby).

Кожна МТ задає вербальне вiдображення T* ->T* таким чином.

МТ М переводить слово uв слово v якщо вона з почат-кової конфiгурацiї q0u переходить до фiнальної конфiгурацiї xqy, де q xy={. При цьому перший та останнiй символи слова v вiдмiннi вiд або v= Цей факт записуємо так: v=M (u).

Якщо МТ M, починаючи роботу з початкової конфiгурацiї q0u, нiколи не зупиниться, кажуть, що M зациклюється при роботi над словом u. Тодi M (u) не визначене.

МТ M1 та M2 еквiвалентнi, якщо вони задають одне і те ж вербальне вiдображення.

МТ M обчислює часткову функцiю f: Nk->N, якщо вона кожне слово вигляду $$\begin{array}{c}{|}^{x_1}\\ \text{.}\text{.}\text{.}\\ {|}^{x_2}{|}^{x_k}\end{array}$$ переводить в слово $${|}^{f(x_1,\text{.}\text{.}\text{.},x_k)}$$ у випадку (x1,…, xk), та M ($$\begin{array}{c}{|}^{x_1}\\ \text{.}\text{.}\text{.}\\ {|}^{x_2}{|}^{x_k}\end{array}$$) невизначене при (x1,…, xk).

Функцiя називається обчислюваною за Тьюрiнгом, або МТ-обчислюваною, якщо iснує МТ, яка її обчислює.

Зауважимо, що кожна МТ обчислює безліч функцій натуральних аргументів та значень, але зафіксовуючи наперед арність функцій, дістаємо, що кожна МТ обчислює єдину функцію заданої арності.

Розглянемо приклади МT.

Приклад 1. МТ, яка обчислює функцiю x+y:

q0||R.

q0#|R.

q0 q1p>

q1| /p>

Приклад 2. МТ, яка обчислює функцiю f (x, y) =x-y:

q0|p>

q1||R.

q1##R.

q1 q2p>

q2|p>

q3||L.

q3##L.

q3 q0p>

q2#|.

q0#p>

q4 q*>

Приклад 3. МТ, яка обчислює функцiю f (x, y)= $$\begin{array}{c}x\stackrel{}{-}y\\ \end{array}$$.

q0|p>

q1||R.

q1##R.

q1 q2p>

q2|p>

q3||L.

q3##L.

q3 q0p>

q2#|.

q0#p>

q4| (єдина відмінність від МТ для f (x, y) =x-y).

q4 q*>

Приклад 4. МТ, яка обчислює функцiю f (x)=sg (x):

q0 q*>

q0||R.

q1|p>

q1 q*>

Приклад 5. МТ, яка обчислює предикат «x парне» :

q0|p>

q1|p>

q0 q*|.

q1 q*>

Приклад 6. МТ, яка обчислює функцiю f (x, y)=x+2y:

q0||R.

q0##R.

q0 q1p>

q1|p>

q2||R.

q2 q3|L.

q3||L.

q3 q1|L.

q1#|L.

q4||L.

q4 q5p>

q5|>

Приклад 7. МТ, яка обчислює функцiю f (x)=2x.

q0||R.

q0 q1aL.

q1||L.

q1 q2p>

q2|p>

q3||R.

q3a aR.

q3 q4p>

q4ap>

q5a aR.

q5 q6 aL.

q6a aL.

q6 q4aL.

q4||L.

q4 q2p>

q2a|R.

q2 q*>

Приклад 8. МТ, яка обчислює функцiю f (x, y)=xp>

q0#p>

q1|p>

q1 q*>

q1a|R.

q0|p>

q2||R.

q2##R.

q3|p>

q4||R.

q4a aR.

q4 q5 aL.

q5||L.

q5a aL.

q5 q3|R.

q3a aL.

q6||L.

q6# #L.

q6 q0p>

q3 q7p>

q7#p>

q7|p>

q7 q*>

Приклад 9. МТ, яка обчислює функцiю f (x)=[x/3]:

q0 q*>

q0|p>

q1|p>

q2||R.

q2 q3p>

q3 a aL.

q3|aL.

q4||L.

q4 q0p>

q1 a a.

q2 a a.

q0a|R.

Приклад 10. МТ, яка кожне слово х переводить в слово х#х.

(тут #.

q0 t tR для всіх tp>

q0 q1#L.

q1 t tL для всіх tp>

q1 q2p>

q2 t для всіх tp>

qt p pR для всіх t p.

qt q’t tL для всіх tp>

q’t pt pL для всіх t p.

q’t q2tR для всіх tp>

q2##.

3. НОРМАЛЬНІ АЛГОРИТМИ МАРКОВА Пiд нормальним алгоритмом (скорочено НА) в алфавiтi T розумiють впорядковану послiдовнiсть продукцiй (правил) вигляду або, де T* та T. Продукцiї вигляду називають фiнальними.

Кожен НА в алфавiтi T задає деяке вербальне вiдображення T*->T*. Слово, яке є результатом обробки слова x нормальним алгоритмом A, позначимо A (x). Обробка слова x нормальним алгоритмом A проводиться поетапно таким чином.

Покладемо x0=x i скажемо, що x0 отримане iз x пiсля 0 етапiв. Нехай слово xn отримане iз слова x пiсля n етапiв. Тодi (n+1)-й етап виконується так.

Шукаємо першу за о порядком продукцiю або таку, що пiдслово xn. Застосуємо цю продукцiю до xn, тобто замiнимо в xn найлiвiше входження на Отримане слово позначимо xn+1. Якщо застосована на (n+1)-му етапi продукцiя нефiнальна, тобто то переходимо до (n+2)-го етапу. Якщо ця продукцiя фiнальна, тобто, то пiсля її застосування A зупиняється i A (x)=xn+1. Якщо ж на (n+1)-му етапi жодна продукцiя A не застосовна до xn+1, тобто в A немає продукцiї, лiва частина якої - пiдслово слова xn+1, то A зупиняється i A (x)=xn.

Якщо в процесi обробки слова x НА A не зупиняється нi на якому етапi, то вважаємо, що A (x) невизначене.

Нормальний алгоритм називають нормальним алгоритмом над алфавiтом T, якщо вiн є нормальним алгоритмом в деякому розширеннi T' НА над T задає певне вiдображення T*->T*, використовуючи в процесi обробки слiв допомiжнi символи поза алфавiтом T. Зупинка НА A над T при роботі над словом х результативна, коли вона вiдбулась на словi y iнакше вважаємо, що результат роботи A над х невизначений.

НА A i B еквiвалентнi вiдносно алфавiту T, якщо для всiх x A (x) та B (x) одночасно визначенi або невизначенi, та у випадку визначеностi A (x)=B (x).

Відомо [7], що для кожного НА над алфавітом Т існує еквiвалентний йому вiдносно T НА в алфавіті Т з єдиним допоміжним символом s Відомо також [7], що вербальне відображення, яке кожне слово x переводить в слово хх, не може бути заданим жодним НА в алфавіті Т. В той же час маємо Приклад 1. НА, який кожне x переводить в слово xх (тут #:

##aа## для всіх a/p>

#ab для всіх a, b/p>

#а для всіх a/p>

##>

##.

НА A обчислює часткову функцiю f: Nk->N, якщо він кожне слово вигляду $$\begin{array}{c}{|}^{x_1}\\ \text{.}\text{.}\text{.}\\ {|}^{x_2}{|}^{x_k}\end{array}$$ переводить в слово $${|}^{f(x_1,\text{.}\text{.}\text{.},x_k)}$$ у випадку (x1,…, xk), та A ($$\begin{array}{c}{|}^{x_1}\\ \text{.}\text{.}\text{.}\\ {|}^{x_2}{|}^{x_k}\end{array}$$) невизначене при (x1 ,…, xk).

Функцiя називається обчислюваною за Марковим, або НА-обчислюваною, якщо iснує НА, який її обчислює.

Зауважимо, що кожний НА обчислює безліч функцій натуральних аргументів та значень, але зафіксовуючи наперед арність функцій, дістаємо, що кожний НА обчислює єдину функцію заданої арності.

Приклад 2. НА для функцiї f (x, y)=x+y:

#.

Приклад 3. НА для функцiї f (x, y)=x-y:

|#|p>

#|/p>

#.

Приклад 4. НА для функцiї f (x)=x/2:

#||/p>

#|/p>

#>

#.

Приклад 5. НА, який кожне слово виду ax переводить в слово $$d^{2^x}$$ :

da.

adp>

dp>

d.

Приклад 6. НА для функцiї f (x)=2х:

|>

#|#.

#>

#>

>

Приклад 7. НА, який кожне слово виду axby переводить в слово dxy :

ab.

db/p>

a.

bp>

Приклад 8. НА для функцiї f (x, y)=x/p>

#>

|/p>

>

>

аb.

|b/p>

a.

b.

Приклад 9. НА, який переводить натуральні числа із 1-ї в 10-ву систему числення:

# |10/p>

# |9p>

# |8p>

… …

#|p>

#p>

|/p>

… …

p>

Приклад 10. НА, який кожне слово x переводить в його дзер-кальне відображення лово xR (тут #:

#ab для всіх a, b/p>

##a# для всіх a/p>

##>

#.

4. СИСТЕМИ ПОСТА.

Канонiчною системою Поста над алфавiтом T називають формальну систему (T*, A, P), в якої множина аксiом A є скiнчен-ною підмножиною множини T*, а множина правил виведення P складається з слiв вигляду. Smath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >0Sj11…n-1Sjnn. Тут T, всі та iксованi слова iз T*, всі символи Sk причому всi ji…, m}.

Символи Sk призначенi для позначення довiльних слiв iз T*.

Системи Поста звичайно позначають у вигляді P =(T, A, P).

Множина правил P визначає на словах iз T* вiдношення безпосереднього виведення таким чином: Р якщо iснує правило. Smath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >0Sj11…n-1Sjnn таке, що для деяких слiв …, маємо. math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >0j11…n-1jnn .

Рефлексивно-транзитивне замикання вiдношення позначаємо $${=>}_{Р}^{}$$. Інакше кажучи, ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >=>Р означає, що слово отримане iз слова за допомогою скiнченної кiлькостi застосувань правил iз P.

Слово породжується системою Поста P, якщо ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >=>Р для деякої A. Цей факт записуємо P | i називаємо таке слово теоремою системи Поста P.

Множину Th (P)={T*| P |} називатимемо множиною теорем системи Поста P.

Для завдання системи Поста достатньо вказати множину правил та множину аксiом. У випадку необхiдностi вказуємо i алфавiт T.

Приклад 1. Система Поста iз A={a, b, та P={S, S} породжує всi слова-палiндроми в алфавiтi {a, b}, тобто слова, якi читаються однаково злiва направо i справа налiво.

Множина X породжувана за Постом, якщо iснують алфавiт T’та система Поста P=(T', A, P) такi, що Th (P))=X.

Обчислюванiсть функцiй за Постом е породжуванiсть за Постом графiкiв таких функцiй.

Часткова функцiя f: Nk->N обчислювана за Постом, якщо породжуваною за Постом є множина { $$\begin{array}{c}{|}^{x_1}\\ \text{.}\text{.}\text{.}\\ {|}^{x_2}{|}^{x_k}{|}^{f(x_1,\text{.}\text{.}\text{.},x_k)}\end{array}$$ 1,…, xk)}.

Наведемо приклади функцій та предикатів, обчислюваних за Постом.

Приклад 2. Система Поста для функцiї f (x, y)=x+y :

A ={##};

P ={X#Y#RY#R|,.

X#Y#R|#R| }.

Приклад 3. Система Поста для функцiї f (x, y)=x.

A ={##};

P ={X#Y#RY#R|,.

X#Y#R||#R }.

Приклад 4. Ще одна система Поста для функцiї f (x, y)=x.

A ={##};

P ={X#Y#RY|#R,.

X##R#R| }.

Приклад 5. Cистема Поста для функцiї $$\begin{array}{c}f(x,y)=x\stackrel{}{-}y\\ \end{array}$$ ;

A ={##};

P ={X#Y#RY|#R,.

X##R#R|,.

#Y## }.

Приклад 6. Cистема Поста для функцiї f (x, y)=|x:

A ={##};

P ={X#Y#RY|#R,.

X##R#R|,.

X#Y#R#R }.

Приклад 7. Система Поста для функцiї f (x, y)=x.

A ={##};

P ={X#Y#RY#RY,.

X#Y#R|#RX }.

Приклад 8. Система Поста для функцiї f (xy)=x2 :

A ={#};

P ={X#RRХХ| }.

Приклад 9. Система Поста для функцiї f (x)=2x :

A ={#};

P ={X#RRR }.

Приклад 10. Cистема Поста для функцiї f (x, y)=max (x, y):

A ={##};

P ={X#X#XX|#X|,.

X#XS#XSS|#XS|,.

XS#X#XS#X#XS| }.

Приклад 11. Система Поста для функцiї f (x, y)=x+2y :

A ={## |};

P ={X#Y#XSY#XS|,.

X#Y#XS|#XSS }.

Приклад 12. Система Поста для функцiї f (x, y)=x.

A ={##};

P ={X##R#R|,.

X#Y#RYY||#R }.

Приклад 13. Система Поста для функцiї f (x)=x2.

A ={#, ||#};

P ={X|#R#RXX| }.

В цьому прикладі треба врахувати, що f (1)p>

Приклад 14. Система Поста для функцiї f (x)=x3 :

A ={};

P ={XХ|QXXX|,.

X }.

Для обчислення значення f (x+1)=(x+1)3=f (x)+3×2+3х+1 потрібне x2, тому теоремами СП мусять також бути коди трійок (х, x2, x3). Але теоремами в алфавіті {|, #} можуть бути тільки коди елементів графіка f (x), тому для кодування трійок (х, x2, x3) використано p>

Приклад 15. Система Поста для функцiї f (x)=x! :

A={#|};

P ={X#Fp>

S.

S.

S }.

До теорем СП належать коди 5-рок (х+1, x!, a, b, ab), для їх коду-вання використано Із кодів 5-рок (х+1, x!, х+1, x!, (х+1) можна вивести закодовані в алфавіті {|, #} коди пар (х+1, (х+1)!).

Приклад 16. Система Поста для функцiї f (x)= $$[\sqrt{х}]$$ :

A={};

P ={X,.

QS||.

X,.

X }.

До теорем СП належать коди трійок (х, r2, r), для їх кодування використано Із кодів трійок (х, x, r) та (х, (r+1)2, r+1) при умові r2lt-(r+1)2 можна вивести закодовані в алфавіті {|, #} коди пар (х, r).

Приклад 17. Система Поста для предикату «x=y» :

A ={## |};

P ={X#Y#RY|#R|,.

X##R#,.

#Y#R# }.

5. ОБЧИСЛЮВАНІСТЬ КВАЗИАРНИХ ФУНКЦІЙ НА N.

Основними обчислюваними операцiями для випадку еквітонних V-квазиарних функцій на множині N є параметричні операцiї суперпозицiї S $${}^{v_1,\text{.}\text{.}\text{.}{v}_n}$$, примiтивної рекурсiї Ry, z та мiнiмiзацiї My .

Операцiя примiтивної рекурсiї Ry, z з параметрами у, z двом V-квазиарним функцiям g та h ставить у вiдповiднiсть V-квазиарну функцiю f, яку позначають Ry, z (g, h).

Для кожного d значення f (d) визначається таким чином:

при ут (d) значення f (d) невизначене;

при ут (d) значення f (d) визначається рекурсивною схемою.

f (d= g (d.

f (d1) = h (d) для всіх a<d (y).

Це означає, що для всiх d таких, що ут (d) та d (y)=b, значення f (d) обчислюється так:

f (d= g (d.

f (d= h (d.

… … … … … … … … … … …

f (d) = f (d= h (d)).

Операцiя мiнiмiзацiї My з параметром у V-квазиарній функцiї g ставить у вiдповiднiсть V-квазиарну функцiю f, яку позначають My (g). Для кожного d значення f (d) визначається як перше атаке, що g (d0 і для всiх k<а значення g (d визначене та Якщо таке aне iснує, то f (d)p>

Це означає, що кожного d значення f (d) обчислюється так. Послiдовно обчислюємо значення g (d для k=0, 1, 2, … Перше таке, а що g (d0, буде шуканим значенням f (d). При цьому для всiх k<а значення g (d визначені та /p>

Процес обчислення значення My (g)(d) нiколи не закiнчиться в таких випадках:

значення g (d невизначене;

для кожного kзначення g (d визначене та /p>

для всiх k<а значення g (d визначене та, а значення g (d невизначене.

Базовими функцiями для випадку V-квазиарних функцiй, заданих на множинi N, вважатимемо функцiї о, sх та функцiї розіменування 'v. Вказані функції визначаються так:

о (d)=0 для всіх d;

'v (d)=d (v)= $$\{\begin{array}{c}а\text{таке, що}vad,\text{якщо}v\text{im}(d),\\ \text{невизначене інакше-}\end{array}$$.

sх (d)= d (х)+1 = $$\{\begin{array}{c}а+1\text{таке, що}хad,\text{якщо}х\text{im}(d),\\ \text{невизначене інакше}\text{.}\end{array}$$.

Функцiю, яку можна отримати iз базових функцiй о, sх 'v за допомогою скiнченної кiлькостi застосувань операцiй S $${}^{v_1,\text{.}\text{.}\text{.}{v}_n}$$, Ry, z та My, назвемо V-квазиарною частково рекурсивною функцiєю (скорочено V-КЧРФ).

Функцiю, яку можна отримати iз фінарних функцiй о, sх 'v за допомогою скiнченної кiлькостi застосувань операцiй S $${}^{v_1,\text{.}\text{.}\text{.}{v}_n}$$, Ry, z та My, назвемо V-фінарною частково рекурсивною функцiєю (скорочено V-ФЧРФ).

Із наведених визначень випливають наступні твердження:

1. Функцiя Ry, z (g, h) алгоритмiчно обчислювана відносно функцій g, h та відносно скінченноіменних операцій врізки на VN і відносно V-ІМ над N як функцій .

2. Функцiя Ry, z (g, h) алгоритмiчно обчислювана відносно V-фінарних функцій g та h.

3. Функцiя Мy (g) алгоритмiчно обчислювана відносно функції g та відносно скінченноіменних операцій врізки на VN і відносно V-ІМ над N як функцій .

4. Функцiя Мy (g) алгоритмiчно обчислювана відносно V-фінарної функції g.

5. Операції Ry, z та My зберігають еквітонність V-квазиарних функцій, завданих на множинi N.

6. Кожна V-КЧРФ алгоритмiчно обчислювана відносно скінченно-іменних операцій врізки на VN та відносно V-ІМ над N як функцій.

7. Кожна V-ФЧРФ алгоритмiчно обчислювана.

8. Кожна V-КЧРФ еквітонна.

Алгебру (Ry, z, My, S $${}^{v_1,\text{.}\text{.}\text{.}{v}_n}$$), носiєм якої є клас всiх V-КЧРФ, а операцiями перацiї S $${}^{v_1,\text{.}\text{.}\text{.}{v}_n}$$, Ry, z та My, назвемо алгеброю V-КЧРФ.

Алгебру (Ry, z, My, S $${}^{v_1,\text{.}\text{.}\text{.}{v}_n}$$), носiєм якої є клас всiх V-ФЧРФ, а операцiями перацiї S $${}^{v_1,\text{.}\text{.}\text{.}{v}_n}$$, Ry, z та My, назвемо алгеброю V-ФЧРФ.

Введемо поняття операторного терма (скорочено ОТ) алгебри V-КЧРФ. Алфавiт складатиметься iз символiв базових функцiй о, sх та 'v, символiв операцiй Ry, z My та S $${}^{v_1,\text{.}\text{.}\text{.}{v}_n}$$, а також допомiжних символiв (,) та,. Дамо iндуктивне визначення ОТ алгебри V-КЧРФ:

1) кожен символ базової функцiї є ОТтакі ОТ назвемо атомарними;

2) якщо t0, t1, …, tn ОТ, то S $${}^{v_1,\text{.}\text{.}\text{.}{v}_n}$$ (t0, t1, …, tn) Т;

3) якщо t0 та t1 Т, то Ry, z (t0, t1) Т;

4) якщо t ОТ, то My (t) Т.

Інтерпретуючи символи на множині природним чином, маємо: кожна V-КЧРФ є значенням деякого ОТ алгебри V-КЧРФ.

При інтерпретації символів на множині дістаємо, що кожна V-ФЧРФ є значенням деякого ОТ алгебри V-КЧРФ.

Якщо функцiя f є значенням ОТ то кажуть, що пера-торний терм функцiї f, або що f задана операторним термом p>

Зауважимо, що завдання V-КЧРФ та V-ФЧРФ операторними тер-мами не є однозначним. Наприклад, операторнi терми о, Sх (о, sх), Sх (о, о) та Sх, у (о, о, s) задають одну i ту ж функцiю о.

Розглянемо приклади V-КЧРФ. Зрозуміло, що при обмеженні на клас V-ФЧРФ це будуть приклади V-ФЧРФ.

Приклад 1. Функцiї-константи КЧРФ.

Справдi, константи 0, 1, 2, … задаються відповідно операторними термами о, Sх (sх, о), Sх (sх, Sх (sх, о)), … Операторні терми для констант 1, 2, …, k, … позначатимемо відповідно 1, 2, …, k, …

Приклад 2. Функція додавання +xy є V-КЧРФ.

Функцiя +xy визначається так: +xy (d)='x (d)+'y (d). Зрозуміло, що значення +xy (d) визначене т (d) та yт (d).

Нехай xт (d) та yт (d). Тоді маємо.

+xy (d'x (d'x (d);

+xy (d)=sz (d (d.

Отже, функція +xy утворена із базових функцій 'x та sz за допомогою операції Ry, z .

Операторний терм для функції +xy має вигляд Ry, z ('x, sz). Такий терм позначимо .

Приклад 3. Функція множення є V-КЧРФ.

Функцiя визначається так: (d)='x (d)d). Зрозуміло, що значення (d) визначене т (d) та yт (d).

Нехай xт (d) та yт (d). Тоді маємо.

dо (dо (d)=0;

d)='x (d)1)='x (d)x (d)=.

=+xz (dxy (d.

Отже, функція утворена із функцій о та +xz за допомогою операції Ry, z. ОТ для функції має вигляд Ry, z (о,. Такий терм позначимо /p>

Приклад 4. Функцiя sgx (d)= $$\{\begin{array}{c}\text{0, якщо}\text{'}x(d)=\text{0,}\\ \text{1, якщо}\text{'}x(d)>0\text{,}\\ \text{невизначене, якщо}х\text{іт}(d),\end{array}$$ є V-КЧРФ.

Справдi, маємо sgx (d= о (dо (d)=0;

sgx (d) = 1.

Отже, функція sgx утворена із функцій о та 1 за допомогою операції Rx, y. ОТ для функції sgx має вигляд Rx, y (о, 1). Такий терм позначимо sgx .

Приклад 5. Функцiя nsgx (d)= $$\{\begin{array}{c}\text{1, якщо}\text{'}x(d)=\text{0,}\\ \text{0, якщо}\text{'}x(d)>0\text{,}\\ \text{невизначене, якщо}х\text{іт}(d),\end{array}$$ є V-КЧРФ.

Справдi, маємо nsgx (d= 1;

nsgx (d) = 0.

Отже, функція nsgx утворена із функцій 1 та о за допомогою операції Rx, y. ОТ для функції sgx має вигляд Rx, y (1, о). Такий терм позначимо nsgx .

Приклад 6. Функцiя $$\begin{array}{c}\stackrel{}{{-}_{\text{ху}}}\\ \end{array}$$ (d)= $$\{\begin{array}{c}\text{'}x(d)-\text{'}y(d)\text{, якщо}\text{'}x(d)>=\text{'}y(d)\text{,}\\ \text{0, якщо}\text{'}x(d)<=\text{'}y(d)\text{,}\\ \text{невизначене, якщо}х,y\text{іт}(d),\end{array}$$.

є V-КЧРФ.

Функцiя $$\begin{array}{c}\stackrel{}{{-}_{х1}}\\ \end{array}$$ (d)= $$\{\begin{array}{c}\text{'}x(d)-1\text{, якщо}\text{'}x(d)>=1\text{,}\\ \text{0, якщо}\text{'}x(d)=0\text{,}\\ \text{невизначене, якщо}х\text{іт}(d),\end{array}$$ є V-КЧРФ.

Справдi, $$\begin{array}{c}\stackrel{}{{-}_{х1}}\\ \end{array}$$ (d= 0;

$$\begin{array}{c}\stackrel{}{{-}_{х1}}\\ \end{array}$$ (d) = b ='x (dath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >-х1 (d.

Операторний терм функцiї $$\begin{array}{c}\stackrel{}{{-}_{х1}}\\ \end{array}$$ має вигляд Rx, y (о,'x).

Тепер маємо $$\begin{array}{c}\stackrel{}{{-}_{\text{ху}}}\\ \end{array}$$ (d='x (d);

$$\begin{array}{c}\stackrel{}{{-}_{\text{ху}}}\\ \end{array}$$ (d)= $$\begin{array}{c}\stackrel{}{{-}_{z1}}\\ \end{array}$$ (dath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >-ху (d.

Отже, функція $$\begin{array}{c}\stackrel{}{{-}_{\text{ху}}}\\ \end{array}$$ утворена із функцій 'x та $$\begin{array}{c}\stackrel{}{{-}_{z1}}\\ \end{array}$$ за допомогою операції Ry, z. Операторний терм функцiї $$\begin{array}{c}\stackrel{}{{-}_{\text{ху}}}\\ \end{array}$$ має вигляд Ry, z ('x, Rz, y (о,'z)). Такий терм будемо позначати $$\begin{array}{c}\stackrel{}{{-}_{\text{ху}}}\\ \end{array}$$ .

Приклад 7. Функцiя |-|ху (d) = |'x (d)-'y (d)| є V-КЧРФ.

Справдi, маємо |a-b|=($$\begin{array}{c}а\stackrel{}{-}b\\ \end{array}$$)+($$\begin{array}{c}b\stackrel{}{-}a\\ \end{array}$$). Звідси OT функцiї |-|ху має вигляд Sх, у ($$\begin{array}{c}\stackrel{}{{-}_{\text{ху}}}\\ \end{array}$$, $$\begin{array}{c}\stackrel{}{{-}_{\text{ух}}}\\ \end{array}$$). Такий терм будемо позначати |-|ху .

Приклад 8. Функцiяху (d) = 'x (d)-'y (d) є V-КЧРФ.

Cправді, якщо а=т-п, то, а знаходиться як перше, починаючи з 0, таке число, що т=п+а, тобто |(п+a)-т|=0. Тому операторний терм функцiїху має вигляд Mz (Sv (|-|vx,).

Приклад 9. Функцiя [x/у] є V-КЧРФ.

Cправді, [x/y] = 1)>x). Тому ОТ функцiї [x/у] має вигляд Mz (Su, v ($$\begin{array}{c}\stackrel{}{{-}_{\text{uv}}}\\ \end{array}$$, sx, Sv (sz)).

Приклад 10. Функцiя [ $$\sqrt{х}$$ ] є V-КЧРФ.

Маємо [ $$\sqrt{х}$$ ] = 1)>x). Тому ОТ функцiї [ $$\sqrt{х}$$ ] має вигляд My (Su, v ($$\begin{array}{c}\stackrel{}{{-}_{\text{uv}}}\\ \end{array}$$, sx, Su, v (sy, sy)).

6. ОБЧИСЛЮВАНІСТЬ п-АРНИХ ФУНКЦІЙ НА N.

Основними обчислюваними операцiями для п-арних функцiй на множині N є наступні операції: операція суперпозицiї Sn+1, операція примiтивної рекурсiї R, операція мiнiмiзацiї M.

Операцiя Sn+1 n-арнiй функцiї g (x1,…, xn) та n функцiям g1(x1,…, xт), …, gn (x1,…, xm) одної i тої ж арностi ставить у вiдповiднiсть функцiю f (x1,…, xm) = g (g1(x1,…, xт), …, gn (x1,…, xm)).

Таку функцiю позначають Sn+1 (g, g1, …, gn), її арність співпадає з арнiстю функцiй g1, …, gn.

Операцiя примiтивної рекурсiї R n-арнiй функцiї g та (n+2)-арнiй функцiї h ставить у вiдповiднiсть (n+1)-арну функцiю f, яку позначають R (g, h), що задається рекурсивним визначенням.

f (x1,…, xn, 0) = g (x1,…, xn).

f (x1,…, xn, y+1) = h (x1,…, xn, y, f (x1,…, xn, y)).

Це означає, що для всiх значень a1,…, an, b значення f (a1,…, bn, b) обчислюється так:

f (a1,…, an, 0) = g (a1,…, an).

f (a1,…, an, 1) = h (a1,…, an, 0, f (a1,…, an, 0)).

… … … … … … … … … … …

f (a1,…, an, b) = h (a1,…, an, b-1, f (a1,…, an, b-1)).

При n=0 вважаємо, що функцiя g арна константа.

Операцiя мiнiмiзацiї M кожній (n+1)-арнiй функцiї g ставить у вiдповiднiсть n-арну функцiю f, яку позначають M (g), що задається спiввiдношенням.

f (x1,…, xn) = (x1,…, xn, y)=0).

Це означає, що для всiх значень x1, …, xn значення функцiї f (x1,…, xn) обчислюється так. Послiдовно обчислюємо значення g (x1,…, xn, y) для y=0, 1, 2, … Перше таке значення y, що g (x1,…, xn, y)=0, буде шуканим значенням f (x1,…, xn). При цьому для всiх t<y значення g (x1,…, xn, y) мусять бути визначені та /p>

Із визначення випливає, що процес обчислення значення (x1,…, xn, y)=0) нiколи не закiнчиться в таких випадках:

значення g (x1,…, xn, 0) невизначене;

для всiх значень у значення g (x1,…, xn, y) визначене та /p>

для всiх t<y значення g (x1,…, xn, t) визначене та, а значення g (x1,…, xn, y) невизначене.

Зрозуміло, що функцiя g може бути тотальною, а функцiя f=M (g) авiть всюди невизначеною. Наприклад, f (x)=+y+1=0).

Базовими функцiями називаються найпростiшi функцiї о (x)=0, s (x)=x+1 та функцiї-селектори I $${}_{т}^{п}$$ (x1,…, xn)=xm, де n.

Всi базовi функцiї тотальнi та алгоритмiчно обчислюванi.

Функцiю, яку можна отримати iз базових функцiй за допомогою скiнченної кiлькостi застосувань операцiй суперпозицiї та примiтивної рекурсiї, називають примiтивно рекурсивною функцiєю (скорочено ПРФ).

Функцiю, яку можна отримати iз базових функцiй за допомогою скiнченної кiлькостi застосувань операцiй суперпозицiї, примiтивної рекурсiї та мiнiмiзацiї, називають частково рекурсивною функцiєю (скорочено ЧРФ).

Тотальну ЧРФ називають рекурсивною функцiєю (скорочено РФ).

Iз наведених визначень випливають наступні твердження:

1. Якщо функцiї g, g1, …, gn тотальнi та алгоритмiчно обчислюванi, то функцiя Sn+1 (g, g1, …, gn) теж тотальна та алгоритмiчно обчислювана.

2. Якщо функцiї g та h тотальнi та алгоритмiчно обчислюванi, то функцiя R (g, h) теж тотальна та алгоритмiчно обчислювана.

3. Якщо функцiя g алгоритмiчно обчислювана, то функцiя M (g) теж алгоритмiчно обчислювана.

4. Кожна ПРФ — тотальна алгоритмiчно обчислювана функцiя.

5. Кожна ЧРФ — алгоритмiчно обчислювана функцiя.

6. Кожна РФ — тотальна алгоритмiчно обчислювана функцiя.

7. Для відповідних класів функцій мають місце спiввiдношення ПРФФРФ.

Алгебра (, M, S1, S2, …), носiєм якої є клас всiх ЧРФ, а операцiями — операцiї R, M та Sn+1, де n називається алгеброю ЧРФ, або алгеброю Чoрча.

Алгебра (, S1, S2, …), носiєм якої є клас всiх ПРФ, а операцiями перацiї R та Sn+1, де nназивається алгеброю ПРФ.

Введемо поняття операторного терма алгебри ЧРФ та операторного терма алгебри ПРФ. Алфавiт складатиметься iз символiв базових функцiй о, s та I $${}_{т}^{п}$$, де n символiв операцiй R, M та Sn+1, де n, а також допомiжних символiв (,) та, .

Дамо iндуктивне визначення ОТ алгебри ЧРФ.

1) кожен символ базової функцiї є ОТтакі ОТ назвемо атомарними;

2) якщо t0, t1, …, tn ОТ, то Sn+1(t0, t1, …, tn) Т;

3) якщо t1 та t2 Т, то R (t1, t2) Т;

4) якщо t ОТ, то M (t) Т.

Аналогiчно дається індуктивне визначення ОТ алгебри ПРФ.

Кожна ЧРФ є значенням деякого ОТ алгебри ЧРФ. Проте не кожен ОТ алгебри ЧРФ має певне значення. Наприклад, операторнi терми R (о, I $${}_2^4$$) та S3(I $${}_1^2$$, I $${}_2^3$$, I $${}_2^2$$) не мають значення.

Зауважимо, що завдання ЧРФ операторними термами не є однозначним. Наприклад, операторнi терми о, S2(о, s), S2(о, о) та S3(о, S2(о, s)) задають одну i ту ж функцiю о (x).

Розглянемо приклади ПРФ, ЧРФ та РФ.

Приклад 1. Функцiї-константи РФ.

Справді, n-арна нуль-функцiя оn (x1,…, xn)=0 задається ОТ S2(о, I $${}_1^{п}$$);

n-арна константа kn (x1,…, xn)=k задається ОТ S2(s, S2(s,…, S2(о, I $${}_1^{п}$$)…).

Приклад 2. Функцiя f (x1, x2)=x1+x2 РФ. Справдi, маємо.

f (x1, 0) = x1 = I $${}_1^1$$ (x1);

f (x1, x2+1) = x1+(x2+1) = (x1+x2)+1 = s (x1+x2) = s (f (x1, x2)).

Отже, функцiя f (x1, x2)=x1+x2 виникає примiтивною рекурсiєю iз функцiй g (x1)=I $${}_1^1$$ (x1) та h (x1, x2, x3)=x3+1=s (x3)=S2(s, I $${}_3^3$$)(x1, x2, x3).

Операторний терм функцiї x1+x2 має вигляд R (I $${}_1^1$$, S2(s, I $${}_3^3$$)).

Приклад 3. Функцiя f (x1, x2)=x1РФ. Справдi, маємо.

f (x1, 0) = 0 = о (x1);

f (x1, x2+1) = x1+1) = x1x1 = f (x1, x2)+х1.

Отже, функцiя f (x1, x2)=x1 виникає примiтивною рекурсiєю iз функцiй g (x1)=о (x1) та h (x1, x2, x3) = x3+x1. За прикладом 2 функцiя h є ПРФ, тому f РФ. Операторний терм функцiї x1 має вигляд R (о, S3($${}_3^3$$, I $${}_1^3$$)), де ператорний терм функцiї x1+x2 .

Приклад 4. Функцiя f (x1, x2) = $$(x_1{)}^{x_2}$$ РФ. Справдi, маємо.

f (x1, 0) = (x1)0 = 1;

f (x1, x2+1) = $$(x_1{)}^{x_2+1}$$ =ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >(x1)x2 = f (x1, x2).

Отже, функцiя f (x1, x2)= $$(x_1{)}^{x_2}$$ виникає примiтивною рекурсiєю iз функцiй g (x1) = 11(x1) та h (x1, x2, x3) = x3 За прикладом 3 функцiя h є ПРФ, тому f РФ. Операторний терм функцiї $$(x_1{)}^{x_2}$$ має вигляд R (S2(s, о), S3($${}_3^3$$, I $${}_1^3$$)), де Т функцiї x1.

Приклад 5. Функцiя sg (x1)= $$\{\begin{array}{c}\mathrm{0,}\text{якщо}{х}_1=\mathrm{0,}\\ \text{1, якщо}{х}_1>=\text{1,}\end{array}$$ РФ.

Справдi, маємо sg (0) = 0 = о (x1);

sg (x1+1) = 1.

Операторний терм функцiї sg (x1) має вигляд R (о, S2(s, S2(о, I $${}_1^2$$))).

Приклад 6. Функцiя пsg (x1) = $$\{\begin{array}{c}\mathrm{1,}\text{якщо}{х}_1=\mathrm{0,}\\ \text{0, якщо}{х}_1>=\text{1,}\end{array}$$ РФ.

Справдi, маємо пsg (0) = 1 = s (о (x1));

пsg (x1+1) = 0.

Операторний терм функцiї пsg (x1) має вигляд R (S2(s, о), S2(о, I $${}_1^2$$)).

Приклад 7. Функцiя f (x1, x2) = $$\begin{array}{c}{x}_1\stackrel{}{-}{х}_2\\ \end{array}$$ = $$\{\begin{array}{c}{х}_1-{х}_2,\text{якщо}{х}_1>={х}_2,\\ \text{0, якщо}{х}_1<={х}_2,\end{array}$$ є ПРФ.

Спочатку покажемо що функцiя $$\begin{array}{c}{x}_1\stackrel{}{-}1\\ \end{array}$$ РФ. Справдi, маємо.

$$\begin{array}{c}0\stackrel{}{-}1\\ \end{array}$$ = 0 = о (x1);

$$\begin{array}{c}(x_1+1)\stackrel{}{-}1\\ \end{array}$$ = x1 = I $${}_1^2$$ (x1, x2).

Операторний терм функцiї $$\begin{array}{c}{x}_1\stackrel{}{-}1\\ \end{array}$$ має вигляд R (о, I $${}_1^2$$).

Тепер покажемо що функцiя f (x1, x2)= $$\begin{array}{c}{x}_1\stackrel{}{-}{х}_2\\ \end{array}$$ РФ. Маємо.

f (x1, 0) = $$\begin{array}{c}{x}_1\stackrel{}{-}0\\ \end{array}$$ = I $${}_1^1$$ (x1);

f (x1, x2+1) = $$\begin{array}{c}{x}_1\stackrel{}{-}({х}_2+1)\\ \end{array}$$ = $$\begin{array}{c}(x_1\stackrel{}{-}{х}_2)\\ \end{array}$$ $$\begin{array}{c}\stackrel{}{-}1\\ \end{array}$$ = $$\begin{array}{c}f(x_1,{х}_2)\stackrel{}{-}1\\ \end{array}$$ .

Отже, функцiя f (x1, x2) = $$\begin{array}{c}{x}_1\stackrel{}{-}{х}_2\\ \end{array}$$ виникає примiтивною рекурсiєю iз функцiй g (x1)=I $${}_1^1$$ (x1) та h (x1, x2, x3)= $$\begin{array}{c}{x}_3\stackrel{}{-}1\\ \end{array}$$. Звідси операторний терм функцiї $$\begin{array}{c}{x}_1\stackrel{}{-}{х}_2\\ \end{array}$$ має вигляд R (I $${}_1^1$$, S2(R (о, I $${}_1^2$$), I $${}_1^3$$)).

Приклад 8. Функцiя f (x1, x2) = |x1-x2| = ($$\begin{array}{c}{x}_1\stackrel{}{-}{х}_2\\ \end{array}$$)+($$\begin{array}{c}{x}_2\stackrel{}{-}{х}_1\\ \end{array}$$) РФ.

Приклад 9. Функцiя f (x1, x2) = x1-x2 = $${}_{{х}_3}$$ (|x1-(x2+x3)|=0) РФ.

Приклад 10. Всюди невизначена функцiя fРФ. >

Cправді, f)= $${}_{{х}_1}$$ (x1+1=0), тому fє значенням ОТ М (s).

Приклад 11. Функцiя f (x1, x2) = [x1/x2] РФ. >

Cправді, [x1/x2] = $${}_{{х}_3}$$ (x2 +1)>x1) = $${}_{{х}_3}$$ (nsg (x2 +1) $$\begin{array}{c}\stackrel{}{-}{х}_1\\ \end{array}$$)=0).

Функцiя [x1/x2] невизначена при x2=0, тому вона не РФ і не ПРФ.

Приклад 12. Функцiя f (x1) = [ $$\sqrt{{х}_1}$$ ] Ф. Справді, [ $$\sqrt{{х}_1}$$ ] тотальна та [ $$\sqrt{{х}_1}$$ ]= $${}_{{х}_2}$$ ((x2+1)+1)>x1)= $${}_{{х}_2}$$ (nsg ((x2+1)+1) $$\begin{array}{c}\stackrel{}{-}{х}_1\\ \end{array}$$)=0).

Розглянемо деякi елементарнi властивостi ПРФ i РФ. Для спро-щення звичайно позначатимемо xn+1 та xn+2 як у та z відповідно.

Теорема 6.1. Нехай (n+1)-арна функцiя g РФ. Тодi (n+1)-арна функцiя f, задана умовою f (x1,…, xn, у) = $$\underset{k=0}{\overset{y}{}}g(x_1,\text{.}\text{.}\text{.},x_n,k)$$, теж ПРФ.

Домовимося надалi вважати, що при z<y $$\underset{k=у}{\overset{z}{}}{a}_k$$ = 0.

Тeорeма 6.2. Нехай (n+1)-арна функцiя g РФ. Тодi (n+2)-арна функцiя f, задана умовою f (x1,…, xn, у, z) = $$\underset{k=y}{\overset{z}{}}g(x_1,\text{.}\text{.}\text{.},x_n,k)$$, теж ПРФ.

Тeорeма 6.3. Нехай (n+1)-арна функцiя g та n-арнi функцiї РФ. Тодi n-арна функцiя h, задана умовою.

h (x1,…, xn)= $$\underset{k=(x_1,\text{.}\text{.}\text{.},x_n)}{\overset{(x_1,\text{.}\text{.}\text{.},x_n)}{}}g(x_1,\text{.}\text{.}\text{.},x_n,k)$$ еж ПРФ.

Теореми 6.6.1−6.6.3 називають теоремами сумування. Замiнивши в цих теоремах символ суми на символ добутку одержимо теореми мультиплiкацiї.

Кажуть, що (п+1)-арна функцiя f отримується iз (n+1)-арної функцiї g за допомогою операцiї обмеженої мiнiмiзацiї, якщо вона задається таким спiввiдношенням:

f (x1,…, xn, у)= $$\{\begin{array}{c}\text{перше, починаючи з 0, значення}z\text{таке, що}z<=y\\ \text{та}g(x_1,\text{.}\text{.}\text{.},x_n)=\text{0, якщо таке значення}z\text{існує,}\\ \text{значення}у,\text{якщо такого значення}z\text{не існує}\text{.}\end{array}$$.

Цей факт позначаємо так: f (x1, …, xn, у) = $${}_{z<=y}$$ ((g (x1, …, xn, z)=0).

Тeорeма 6.4 (про обмeжeну мiнiмiзацiю). Нехай (n+1)-арна функцiя g є ПРФ. Тодi (n+1)-арна функцiя f, задана умовою.

f (x1,…, xn, у) = $${}_{z<=y}$$ ((g (x1, …, xn, z)=0) еж ПРФ .

Наслідок. Нехай функцiї g (x1, …, xn, у) та, …, xn) є ПРФ. Тодi функцiя f (x1, …, xn) = $${}_{у<=({х}_1,\text{.}\text{.}\text{.},x_n)}$$ ((g (x1,…, xn, у)=0) теж є ПРФ .

Приклад 13. Довизначимо функцiю f (x1, x2) = [x1/x2] таким чином: [x1/0]=x1. Тоді функцiя [x1/x2] є ПРФ. Справдi, значення [a/b] рiвне кiлькостi нулiв в послiдовностi 1ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >b-a, 2ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >b-a, …, aath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >b-a. Тому [x1/x2] = $$\begin{array}{c}\underset{k=1}{\overset{{х}_1}{}}\text{nsg}(k{х}_2\\ \end{array}$$ $$\begin{array}{c}\stackrel{}{-}{х}_1\\ \end{array}$$), звідки [x1/x2] є ПРФ за теоремою 6.6.3.

Приклад 14. Функцiя mod (x1, x2) стача вiд дiлення x1 на x2, ЧРФ. Справдi, mod (x1, x2) = $$\begin{array}{c}{x}_1\stackrel{}{-}({х}_2\\ \end{array}$$ /x2]).

Зауважимо, що беручи тут довизначену функцію [x1/x2], дістане-мо довизначену функцію mod (x1, x2): mod (x1,0)=0. Така довизначена функція mod (x1, x2) є ПРФ.

Приклад 15. Функцiя f (x1) = [ $$\sqrt{{х}_1}$$ ] є ПРФ.

Справдi, маємо [ $$\sqrt{{х}_1}$$ ]= $${}_{{х}_2<={х}_1}$$ (nsg ((x2+1)+1) $$\begin{array}{c}\stackrel{}{-}{х}_1\\ \end{array}$$)=0), тому за теоремою 6.6.4 [ $$\sqrt{{х}_1}$$ ] є ПРФ.

Приклад 16. Функцiя пd (x) ількість дiльників числа x, ПРФ при довизначенні пd (0)=1. Справдi, пd (x) = $$\underset{k=0}{\overset{x}{}}\text{nsg}(\text{mod}(x,k))$$ .

Приклад 17. Функцiя ількість простих чисел, які не більші за число x, ПРФ. Справдi, = $$\underset{k=0}{\overset{x}{}}\text{nsg}(|\text{nd}(x)-2|)\text{.}$$.

Приклад 18. Функцiя р (x) -ве просте число, ПРФ (тут р (0)=2, р (1)=3, р (2)=5 і т.д.).

Справдi, р (x)=(|)1)|=0). Доведення того факту, що р (x) $$2^{2^x}$$, проведемо індукцією по х. Для х=0 маємо р (0)=2 $$2^{2^0}$$. Нехай для всіх хмаємо p (x) $$2^{2^x}$$. Покажемо p (k+1) $$2^{2^{k+1}}$$. Розглянемо число b=p (0)))+1. За припущенням індукції р (0) $$2^{2^0}$$, , p (k) $$2^{2^k}$$. Тому b $$2^{2^0+2^1+\text{.}\text{.}\text{.}+2^k}+1<2^{2^{k+1}}$$. Але кожний простий дільник числа b більший за p (k), тому p (k+1)math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >22k+1 .

Приклад 19. Функцiя ex (x, y) тепінь числа р (x) в числі у, ПРФ при довизначенні ех (x, 0)=0.

Справдi, ex (x, y)=sg (mod (y, p (x)z+1))y)=0).

7. ПРОГРАМОВАНI ФУНКЦIЇ НА N.

Програмна алгебра (P, K) задається парою (B, K), де множина функцій P снова алгебри, K ножина композицiй (операцiй) над функцiями із P, B множина базових функцiй [22]. Примiтивні програмні алгебри (ППА) — це програмнi алгебри функцiй з простими типами даних. До таких функцiй належать, зокрема, квазиарні, Х-арні та п-арні функцiї, завданi на неструктурованих множинах (напри-клад, на множині N, на множинi R). Kомпозицiями ППА є операцiї суперпозицiї, циклу та розгалуження.

Операцiї суперпозицiї е описані вище операцiї S $${}^{v_1,\text{.}\text{.}\text{.}{v}_n}$$ .

Кожну V-квазиарну функцiю на N можна трактувати як предикат, інтерпретуючи значення 0 як істиннісне значення «F», а довільне значення ак істинісне значення «Т». Тому для випадку V-квазиарних функцiй на N дамо наступні визначення операцій розгалуження та циклу.

Операцiя розгалуження N-квазиарним функцiям g, h та ставить у вiдповiднiсть V-квазиарну функцiю f, значення f (d) якої для кожного d визначається так:

f (d) = $$\{\begin{array}{c}g(d),\text{якщо}(d)\text{визначене та}/=0\text{,}\\ h(d)\text{, якщо}(d)=0\text{,}\\ \text{невизначене інакше}\text{.}\end{array}$$.

Операцiя циклу N V-квазиарним функціям g та ставить у вiдповiднiсть V-квазиарну функцію f, значення f (d) якої для кожного d визначається як перший елемент аm послiдовностi a0= d (v), a1=f (d, a2=f (d, …, ak=f (d1), … такий, що =0 та для всiх k<m значення визначене і якщо такий елемент am iснує. Якщо такий елемент am не iснує, значення f (d) невизначене.

Для випадку еквітонних V-квазиарних функцій на N базовими функцiями вважаємо функцiї о, sх, 'v, +xy, $$\text{та {}\stackrel{}{{-}_{\text{xy}}}$$ .

V-квазиарну функцiю називають програмованою на N, якщо її можна отримати iз вказаних вище базових функцiй за допомогою скiнченної кiлькостi застосувань операцiй суперпозицiї S $${}^{v_1,\text{.}\text{.}\text{.}{v}_n}$$, розгалуження Nта циклу N.

Із наведених визначень випливають наступні твердження:

1. Функцiя N, h) алгоритмiчно обчислювана відносно функцій g та h.

2. Функцiя N) алгоритмiчно обчислювана відносно функцій g та відносно скінченноіменних операцій врізки на VA і відносно V-ІМ над A як функцій .

3. Функцiя N) алгоритмiчно обчислювана відносно V-фінар-них функцій та g.

4. Кожна програмована на N еквітонна V-квазиарна функцiя алгоритмiчно обчислювана відносно скінченно-іменних операцій врізки на VN та відносно V-ІМ над N як функцій .

5. Кожна програмована на N еквітонна V-фінарна функцiя алгоритмiчно обчислювана .

Алгебра (NeqN S $${}^{v_1,\text{.}\text{.}\text{.}{v}_n}$$), носiєм Neq якої є клас всiх програмованих на N V-квазиарних функцiй, а операцiями перацiї NNта S $${}^{v_1,\text{.}\text{.}\text{.}{v}_n}$$, називається примiтивною програмною алгеброю програмованих на N еквітонних V-квазиарних функцiй (ППА-EQ-N).

Алгебра (NefN S $${}^{v_1,\text{.}\text{.}\text{.}{v}_n}$$), носiєм Nef якої є клас всiх програмованих на N V-фінарних функцiй, а операцiями перацiї NNта S $${}^{v_1,\text{.}\text{.}\text{.}{v}_n}$$, називається примiтивною програмною алгеброю програмованих на N еквітонних V-фінарних функцій (ППА-EФ-N).

Дамо iндуктивне визначення операторного терма ППА-EQ-N (скорочено ОТ ППА-EQ-N). Алфавiт складатиметься iз символiв базових функцiй о, sх, 'v, +xy, $$\text{та {}\stackrel{}{{-}_{\text{xy}}}$$, символiв операцiй NNта S $${}^{v_1,\text{.}\text{.}\text{.}{v}_n}$$, а також допомiжних символiв (,) та, .

1) кожен символ базової функцiї є ОТтакі ОТ назвемо атомарними;

2) якщо t0, t1, …, tn ОТ, то S $${}^{v_1,\text{.}\text{.}\text{.}{v}_n}$$ (t0, t1, …, tn) Т;

3) якщо t0, t1 та t2 Т, то N, t1, t2) Т;

4) якщо t0 та t1 ОТ, то N0, t1) Т.

Кожна програмована на N еквітонна V-квазиарна функція є значенням деякого ОТ ППА-EQ-N. При інтерпретації символів на множині Nef дістаємо, що кожна програмована на N еквітонна V-фінарна функція є значенням деякого ОТ алгебри ППА-EQ-N.

Зрозуміло, що подання програмованих на N еквітонних V-квази-арних функцій операторними термами ППА-EQ-N неоднозначне.

Логiчнi операцiї над предикатами засобами ППА-EQ-N можна промоделювати таким чином:

Нехай функції трактуються як предикати. В цьому випадку функції Sx, y ($$\begin{array}{c}\stackrel{}{{-}_{\text{xy}}}\\ \end{array}$$, 1, Sx, y (та Sx, y (+xy, можна відповідно трактувати як предикати, та /div>

Враховуючи, що можна подати як, можна подати як (легко отримати функції, які моделюють вказані предикати.

Вкажемо приклади програмованих на N еквітонних V-квазиарних функцій. Зрозуміло, що при обмеженні на клас V-фінарних функцій вони будуть прикладами програмованих на N V-фінарних функцій.

Приклад 1. Функції-константи програмовані.

Справді, такі функції можна отримати із базових функцій за допомогою операцій суперпозиції. Наприклад, константа 1 подається операторним термом Sx (sх, о), який позначаємо 1.

Приклад 2. Функції пsgх та sgх програмовані.

Функція пsgх подається операторним термом Su ($$\begin{array}{c}\stackrel{}{{-}_{\text{ux}}}\\ \end{array}$$, 1), який позначимо пsgх, функція sgх подається операторним термом Su, v ($$\begin{array}{c}\stackrel{}{{-}_{\text{uv}}}\\ \end{array}$$, 1, пsgх), який позначимо sgх .

Приклад 3. Функцiя |x-у| програмована.

Функція |x-у| подається операторним термом Su, v (+uv, $$\begin{array}{c}\stackrel{}{{-}_{\text{xy}}}\\ \end{array}$$, $$\begin{array}{c}\stackrel{}{{-}_{\text{yx}}}\\ \end{array}$$).

Приклад 4. Предикат x>y програмований.

Справдi, такий предикат моделюється функцiєю $$\begin{array}{c}\stackrel{}{{-}_{\text{xy}}}\\ \end{array}$$ .

Приклад 5. Предикати x x=y та xпрограмовані.

Предикат xмоделюється функцiєю $$\begin{array}{c}(x+1)\stackrel{}{-}у\\ \end{array}$$ — предикат x=y моделюється функцiєю 1-|x-у|, його ж можна подати у вигляді (x (y предикат x можна подати у вигляді у) або у вигляді (x>y)у>х).

Приклад 6. Функцію +xy можна отримати із базових функцій о, sх, 'v, $$\text{та {}\stackrel{}{{-}_{\text{xy}}}$$ за допомогою операцій Nта S $${}^{v_1,\text{.}\text{.}\text{.}{v}_n}$$ .

Маємо z<x+y math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >1- (((z+1) $$\begin{array}{c}\stackrel{}{-}у\\ \end{array}$$) $$\begin{array}{c}\stackrel{}{-}х\\ \end{array}$$)=1, тому предикат z<x+y моделюється функцією $$\begin{array}{c}1\stackrel{}{-}\\ \end{array}$$ (((z+1) $$\begin{array}{c}\stackrel{}{-}у\\ \end{array}$$) $$\begin{array}{c}\stackrel{}{-}х\\ \end{array}$$). Отже, функцію +xy можна подати OT Sz (NSu, v ($$\begin{array}{c}\stackrel{}{{-}_{\text{uv}}}\\ \end{array}$$, 1, Su ($$\begin{array}{c}\stackrel{}{{-}_{\text{ux}}}\\ \end{array}$$, Su ($$\begin{array}{c}\stackrel{}{{-}_{\text{uу}}}\\ \end{array}$$, sz))), sz), о).

Приклад 7. Операцiю розгалуження Nможна промоделювати, використовуючи базові функції ППА-EQ-N і операції суперпозицiї та циклу. Справдi, нехай f =N, h). Тодi f=g (.

Отже, функцiю +xy можна не включати до базових програмованих на N V-квазиарних функцiйфункцію N, h) можна отримати iз базових функцiй о, sх, 'v,, $$\begin{array}{c}\stackrel{}{{-}_{\text{xy}}}\\ \end{array}$$ та функцiй g i h за допомогою операцiй Nта S $${}^{v_1,\text{.}\text{.}\text{.}{v}_n}$$ .

Приклад 8. Функції min (x, y) та max (x, y) програмовані.

Справді, функції min (x, y) та max (x, y) можна подати відповідно операторними термами Nmath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >-xy, 'у, 'х) та Nmath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >-xy, 'х, 'у). Такі терми відповідно позначатимемо mіпxy та mахxy .

Приклад 9. Функція mod (x, y) програмована.

Справді, функцію mod (x, y) можна подати операторним термом NSх ($$\begin{array}{c}\stackrel{}{{-}_{\text{xy}}}\\ \end{array}$$, sх), $$\begin{array}{c}\stackrel{}{{-}_{\text{xy}}}\\ \end{array}$$). Такий терм позначимо modxy .

Приклад 10. Функція $$[\sqrt{х}]$$ програмована.

Справді, функцію $$[\sqrt{х}]$$ можна подати операторним термом Sу (NSu, v ($$\begin{array}{c}\stackrel{}{{-}_{\text{uv}}}\\ \end{array}$$, sх, Su, v (sy, sy), sy), 0).

Приклад 11. Функція [x, y] програмована.

Справді, функцію [x, y] можна подати операторним термом Sz (Nu, v ($$\begin{array}{c}\stackrel{}{{-}_{\text{uv}}}\\ \end{array}$$, sх, Su (sz), sz), 0).

Приклад 12. Функція HCK (x, y) програмована.

Справді, функцію HCK (x, y) можна подати операторним термом Sz (Nu, v (+uv, modzx, modzy), sz), maxxy).

Приклад 13. Функція HCD (x, y) програмована.

Справді, функцію HCD (x, y) можна подати операторним термом Sz (Nu, v (+uv, modxz, modyz), Su ($$\begin{array}{c}\stackrel{}{{-}_{\text{zu}}}\\ \end{array}$$, 1), minxy).

Для випадку п-арних функцій N операцiї суперпозицiї, циклу та розгалуження уточнимо наступним чином.

Операцiя N-арним функціям g та ставить у вiдповiднiсть n-арну функцiю f, значення f (x1, …, xn) якої для кожного набору значень x1, …, xn визначається як перший елемент аm послiдовностi a0=x1, a1=f (a0, x2, …, xn), a2=f (a1, x2, …, xn), …, ak=f (ak-1, x2, …, xn), … такий, що, x2,…, xn)=0 та для всiх k<m значення, x2, …, xn) визначене і якщо такий елемент am iснує. Якщо такий елемент am не iснує, значення f (x1, …, xn) невизначене.

Операцiя N-арним функцiям g, h та ставить у вiдповiднiсть n-арну функцiю f, значення f (x1, …, xn) якої для кожного набору значень x1, …, xn визначається так:

f (x1, …, xn) = $$\{\begin{array}{c}g(x_1,\text{.}\text{.}\text{.},x_n),\text{якщо}(x_1,\text{.}\text{.}\text{.},x_n)\text{визначене та}/=\text{0,}\\ h(x_1,\text{.}\text{.}\text{.},x_n)\text{, якщо}(x_1,\text{.}\text{.}\text{.},x_n)=0\text{,}\\ \text{невизначене інакше}\text{.}\end{array}$$.

Базовими функцiями для випадку n-арних функцiй, завданих на множинi N, будемо вважати функцiї о, s та I $${}_{т}^{п}$$, де n, а також бінарні функції +, $$\text{та {}\stackrel{}{-}$$ .

Функцiю назвемо програмованою на N, якщо її можна отримати iз вказаних вище базових функцiй за допомогою скiнченної кiлькостi застосувань операцiй суперпозицiї Sn+1, розгалуження Nциклу Np>

Із наведених визначень випливають наступні твердження:

1. Якщо функцiї, h алгоритмiчно обчислюванi, то функцiя N, h) теж алгоритмiчно обчислювана.

2. Якщо функцiї та g алгоритмiчно обчислюванi, то функцiя N) теж алгоритмiчно обчислювана.

3. Кожна програмована на N n-арна функцiя є алгоритмiчно обчислюваною.

Алгебра (NarN2, S3, …), носiєм Nar якої є клас всiх програмованих на N n-арних функцiй, а операцiями перацiї Nта Sn+1, де nназивається примiтивною програмною алгеброю програмованих на N n-арних функцiй (ППА-Ar-N).

Дамо iндуктивне визначення операторного терма ППА-Ar-N (скорочено ОТ ППА-Ar-N). Алфавiт складатиметься iз символiв базових функцiй о, s +, ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >, {- та I $${}_{т}^{п}$$, де n символiв операцiй NNта Sn+1, де n, а також допомiжних символiв (,) та, .

1) кожен символ базової функцiї є ОТтакі ОТ назвемо атомарними;

2) якщо t0, t1, …, tn ОТ, то Sn+1(t0, t1, …, tn) Т;

3) якщо t0, t1 та t2 Т, то N, t1, t2) Т;

4) якщо t0 та t1 ОТ, то N, t1) Т.

Кожна програмована на N п-арна функція є значенням деякого ОТ ППА-Ar-N. Проте, як і у випадку ОТ алгебри п-арних ЧРФ, з-за порушень умов арності не кожен ОТ ППА-Ar-N має певне значення.

Зрозуміло, що подання програмованих на N п-арних функцій операторними термами ППА-Ar-N неоднозначне.

Нехай функції та трактуються як предикати. Тоді функції nsg (та можна трактувати як предикати, та відповідно. Враховуючи, що можна подати як, можна подати як (легко отримати функції, які моделюють вказані предикати.

Приклад 14. Функції-константи програмовані.

Справді, такі функції отримуються із базових функцій о, s та I $${}_{т}^{п}$$ за допомогою операцій суперпозиції Sn+1.

Приклад 15. Функції пsg (x1) та sg (x1) програмовані.

Справді, пsg (x1)= $$\begin{array}{c}1\stackrel{}{-}{х}_1\\ \end{array}$$, sg (x1)= $$\begin{array}{c}1\stackrel{}{-}\\ \end{array}$$ ($$\begin{array}{c}1\stackrel{}{-}{х}_1)\\ \end{array}$$ .

Приклад 16. Функцiя |x1-x2| програмована.

Справдi, |x1-x2| = ($$\begin{array}{c}{x}_1\stackrel{}{-}{х}_2\\ \end{array}$$)+($$\begin{array}{c}{x}_2\stackrel{}{-}{х}_1\\ \end{array}$$).

Приклад 17. Предикати x1>x2, x1 x1=x2 та x1 програмовані.

Предикат x1>x2 моделюється функцiєю $$\begin{array}{c}{x}_1\stackrel{}{-}{х}_2\\ \end{array}$$. Предикат x1 моделюється функцiєю $$\begin{array}{c}(x_1+1)\stackrel{}{-}{х}_2\\ \end{array}$$, предикат x1=x2 можна подати у вигляді (x1&(x2, предикат x1 можна подати у вигляді =x2).

Приклад 18. Функція mod (x1, x2) програмована.

Справді, функцію mod (x1, x2) можна подати операторним термом N ($$\begin{array}{c}\stackrel{}{-}\\ \end{array}$$, S2(s, I $${}_1^2$$), I $${}_2^2$$), $$\begin{array}{c}\stackrel{}{-}\\ \end{array}$$).

Приклад 19. Функцiю x1+x2 можна отримати із базових функцій о, s, I $${}_{т}^{п}$$, $$\text{та {}\stackrel{}{-}$$ за допомогою операцій Nта Sn+1.

Позаяк x1<x2+x3 g (((x1+1) $$\begin{array}{c}\stackrel{}{-}{х}_2\\ \end{array}$$) $$\begin{array}{c}\stackrel{}{-}{х}_3\\ \end{array}$$)=1, предикат x1<x2+x3 моделюється функцією nsg (((x1+1) $$\begin{array}{c}\stackrel{}{-}{х}_2\\ \end{array}$$) $$\begin{array}{c}\stackrel{}{-}{х}_3\\ \end{array}$$), ОТ якої має вигляд S3($$\begin{array}{c}\stackrel{}{-}\\ \end{array}$$, 13, S3($$\begin{array}{c}\stackrel{}{-}\\ \end{array}$$, S3($$\begin{array}{c}\stackrel{}{-}\\ \end{array}$$, S2(s, I $${}_1^3$$), I $${}_2^3$$), I $${}_3^3$$). Тому x1+x2 можна подати OT S4(N2(s, I $${}_1^3$$), о2, I $${}_2^2$$, I $${}_1^2$$). Отже, функцію + можна не включати до базових програмованих на N п-арних функцiй.

Приклад 20. Аналогічно випадку V-квазиарних функцій, функцію f=N, h) можна подати у вигляді f=g (Отже, операцiю розгалуження Nможна промоделювати, використовуючи базові функції о, s, I $${}_{т}^{п}$$, $$\text{та {}\stackrel{}{-}$$ і операції суперпозицiї та циклу.

8. ТЕЗА ЧОРЧА Розглянемо співвідношення між різними формальними моделями поняття алгоритмічно обчислюваної функції. Обмежимося розглядом п-арних функцiй на множині N.

Теорема 8.1. Наступнi класи функцiй спiвпадають:

1) клас ЧРФ;

2) клас програмованих на N п-арних функцiй;

3) клас МНР-обчислюваних функцiй;

4) клас функцiй, обчислюваних за Тьюрiнгом;

5) клас функцiй, обчислюваних за Марковим;

6) клас функцiй, обчислюваних за Постом Отже, розглянутi нами формалiзми задають один i той же клас п-арних функцiй на N. При цьому самi визначення формалiзмiв гарантують ефективну обчислюванiсть описуваних ними функцiй. Тому є всi пiдстави вважати, що такi формалiзми є рiзними математичними уточненнями iнтуїтивного поняття алгоритмiчно обчислюваної функцiї (АОФ). Вперше таке твердження стосовно рекурсивних функцiй було висунуте в 1936 роцi А. Чорчом, тому дiстало назву «теза Чорча». Узагальнення тези Чорча на випадок часткових функцiй в цьому ж роцi запропонував С. Клiнi. В такому розширеному виглядi теза Чорча формулюється наступним чином:

Tеза Чорча. Клас ЧРФ співпадає з класом п-арних АОФ, заданих на множині натуральних чисел.

Поняття АОФ не є строго визначеним математичним поняттям, тому теза Чорча математичному доведенню не пiдлягає. Теза Чорча є природно-науковим фактом, який засвідчує адекватність формальних моделей інтуїтивного поняття АОФ.

Із тези Чорча як наслiдок випливає:

клас РФ спiвпадає з класом тотальних АОФ, заданих на множинi натуральних чисел.

Значення тези Чорча (скорочено ТЧ) полягає в наступному.

1) Прийняття тези Чорча перетворює iнтуїтивнi поняття алгоритму, обчислюваностi, розв’язностi в об'єкти математичного вивчення.

2) Використання тези Чорча як своєрiдної аксiоми дозволяє в багатьох випадках замiнити формальнi завдання алгоритмiв на неформальнi їх описи. Це дає iстотне спрощення доведень, звiльняючи його вiд зайвих деталей. Проте доведення на основi тези Чорча має бути ретельно аргументованим! При виникненнi сумнiвiв треба вміти провести чисто формальне доведення.

Розглянемо приклад використання тези Чорча. Нехай функція f є ЧРФ. Доведемо, що функція h (x)= $$\{\begin{array}{c}\mathrm{1,}\text{якщо}x{E}_f,\\ \text{невизначене в інших випадках,}\end{array}$$ теж є ЧРФ. Для цього розглянемо процес глобального обчислення всіх значень функції f. Такий процес розіб'ємо на етапи. На кожному етапі починаємо обчислення для наступного значення аргументу. На етапі 0 робимо 1-й крок обчислення f (0). На етапі 1 робимо 1-й крок обчислення f (1) та 2-й крок обчислення f (0) і т.д. На етапі п робимо 1-й крок обчислення f (п), 2-й крок обчислення f (п-1), …, (п+1)-й крок обчислення f (0). Якщо на якомусь етапі обчислення певного f (т) завершується, порівнюємо f (т) та х. При умові f (т)=х процес глобальних обчислень завершується, адже тоді х, тому результатом нашої роботи буде число 1. При умові f (т) продовжуємо процес глобальних обчислень. Таким чином, описано алгоритм для обчислення функції h (x), звідки за тезою Чорча функція h (x) є ЧРФ.

.