Операція примітивної рекурсії
На цьому етапі ми розглянемоосновні властивості операції підстановки.
Властивість 1. Операція підстановки зберігає якість всюди визначеності функцій, тобто. якщо функціяg(y1, . ym)та функціїh1(x1, . xn), h2(x1, . xn), . hm(x1, . xn)всюди певні функції і функціяfвиходить з них за допомогою операції підстановки, тоfтакож є всюди певної функції.Доказ. Нехай h1, h2, . hm довільні функції відnзмінних. Розглянемо довільний набір. Тоді h1, h2, . hm будуть визначені в цьому наборі через властивість всюди визначеності. Функціяgбуде визначена на наборі(h1(x1, . xn), h2(x1, . xn), .hm(x1, . xn))через властивість всюди визначеності, а щодо визначення підстановки це і є функціяf.
Таким чином ми довели, що функціяfвизначена на наборі(x1, . xn). Так як ми взяли довільний набір з множини натуральних чисел, то властивість доведена.Властивість 2. Операція підстановки зберігає властивість алгоритмічної обчислюваності функцій, тобто. якщо функціїg(y1, . ym)іh1, h2, . hmалгоритмічно обчислювані, іf = S(q, h1, h2, . hm), існує алгоритмAf, що обчислює функціюf.Доказ. Нехай заданий довільний набір. Це означає, що цей набір , де i=1, 2, . m . Далі чинимо так:
- 1-й крок: застосовуємо до набору(x1, . xn)алгоритмA1, що обчислює функціюh1. Оскільки функціяh1за умовою алгоритмічно обчислювана функція, то кінцеве число кроків алгоритмA1дає кінцевий результат функціїh1.
- 2-й крок: застосовуємо до набору(x1, . xn)алгоритмA2, що обчислює функціюh2. Оскільки функціяh2за умовою алгоритмічно обчислювана функція, через кінцеве число кроків робота алгоритмуФ2завершується результативно, тобто. буде обчислено значення функціїh2на наборі(x1, . xn)і т.д. Якщо робота всіх алгоритмів A1, A2, . Am на наборі(x1, . xn)завершилася результативно, тобто. обчислені відповідні значення(h1(x1, . xn), h2(x1, . xn), .hm(x1, . xn)), то переходимо наступний крок, тобто.
- m+1-й крок: застосовуємо алгоритмAg, що обчислює функціюg, до набору(h1(x1, . xn), h2(x1, .xn), .hm(x1, .xn)). Через властивість алгоритмічно обчислюваності функціїg, через кінцеве число кроків алгоритмAgзавершує роботу на наборі(h1(x1, . xn), h2(x1, . xn), hm(x1, . xn))результативно, і цей результат будемо вважати значенням функціїf, так як за визначенням операції підстановкиf(x1, . xn) = g(h1( x1, .xn), h2(x1, .xn), .hm(x1, .xn)).
Якщо алгоритмAi, деi=1, 2, . mне зупиняється чи завершує роботу нерезультативно, вважатимемо, що шуканий алгоритм обчислення цієї функції, тобто. функціїf(x1, . xn), немає.
Операція примітивної рекурсії
Визначення. Говорять, що функціяf(x1, . xn, y)отримана з функційg(x1, . xn)іh(x1, . xn, y, z)за допомогою операції примітивної рекурсії, якщо виконуються такі рівності:
Це визначення має сенс, колиn<>0, при цьому записується
або скороченоf = R(g,h), деRозначає операції примітивної рекурсії.
У випадку, колиn=0, то операція примітивної рекурсії набуде вигляду:
На наступному кроці ми розглянемо основні властивості операції примітивної рекурсії.