Частково-рекурсивні функції
Означення 7. Розглянемо n-місну частково числову функцію f(x1, …, xn). Зафіксуємо деякі значення x1, …, xn – 1 її перших (n – 1) аргументів та розглянемо рівняння f(x1, …, xn – 1, y) = xn. Будемо обчислювати послідовно значення f(x1, …, xn – 1, y) для y = 0, 1, 2, … Найменше a, для якого f(x1, …, xn – 1, а) = xn, позначимо так:
y(f(x1, …, xn – 1, a)) = xn. (2)
Зазначений процес є нескінченним у таких випадках:
Значення f(x1, …, xn – 1, 0) не визначено.
Значення f(x1, …, xn – 1, y) для y = 0, 1, 2, …, a – 1 визначені, але вони відмінні від xn, а значення f(x1, …, xn – 1, a) не визначено.
Значення f(x1, …, xn – 1, y) визначено для всіх y = 0, 1, 2, …, причому вони відмінні від xn.
Значення виразу (2) для заданої функції f залежить від значень параметрів x1, …, xn – 1, xn; тому вираз (2) задає часткову функцію змінних x1, …, xn, що визначає оператор мінімізації (-оператор).
Означення 8. Функція f(x1, …, xn) називається частково-рекурсивною, якщо вона може бути утворена з найпростіших функцій за допомогою скінченої кількості застосувань операторів суперпозиції, примітивної рекурсії та мінімізації. Всюди визначені частково-рекурсивні функції називаються загальнорекурсивними.
Значення частково-рекурсивної функції є таким. З одного боку, кожна стандартно задана частково-рекурсивна функція є обчислювальною за певною процедурою, яка відповідає інтуїтивному уявленню алгоритму, а з іншого – які б досі не будувалися класи точно визначених алгоритмів, завжди з’ясовувалося, що числові функції, які обчислювались за алгоритмами цих класів, були частково-рекурсивними.
Тому загальноприйнятою є така наукова гіпотеза.
Теза Черча. Клас алгоритмічно обчислювальних часткових числових функцій збігається з класом усіх частково-рекурсивних функцій.
Тема „Скінченні автомати. Машина Тьюринга”
Означення 1. Скінченним автоматом M називають набір M = {A, Z, S, , }, де
A = {a0, a1, …, an} – скінченна множина вхідних символів (вхідний алфавіт);
Z = {z0, z1, …, zm} – скінченна множина вихідних символів (вихідний алфавіт);
S = {s0, s1, …, sr} – множина внутрішніх станів;
: S A S – функція переходу (в наступний стан);
: S A Z – функція виходу.
Отже, скінченний автомат складається з трьох множин A, S, Z та двох відображень і .
Якщо розглядати скінченний автомат як математичну модель комп’ютера, то на послідовність символів множини А можна дивитися як на програму для комп’ютера. Ця програма за допомогою функції відповідним способом послідовно змінює стани для того, щоб за допомогою функції одержати вихідну послідовність символів, яку можна трактувати як бажаний результат (наприклад, результат певних обмежень).
Якщо ми маємо скінченний автомат М, то на його вхід подаються скінченні впорядковані послідовності a0, a1, …, an – 1 символів вхідного алфавіту. Такі послідовності називатимемо словами або рядками довжини n.
Нехай
на вхід подається рядок
= a0,
a1,
…, an
– 1.
Тоді на виході одержуємо рядок
= z0,
z1,
…, zn
– 1.
Корисно також розглядати і рядок
відповідних внутрішніх станів
= s0,
s1,
…, sn
– 1.
Зрозуміло, що рядки
і
однозначно визначаються рядком
та початковим станом s0.
Отже, маємо два відображення
n: S An Sn, n: S An Zn,
для яких i(s0, ) = (si – 1, ai – 1), i(s0, ) = (si – 1, ai – 1).
Це означає, що відображення n і n „рекурсивно” одержуються з відображень і , тобто знаючи і і і для i n, можемо однозначно визначити n і n.
Якщо скінченний автомат має багато внутрішніх станів, то відповідний йому реальний пристрій конструюється з багатьох електронних схем, які реалізують ці стани. Отже, важливим є пошук автоматів з якомога меншою кількістю внутрішніх станів. Нехай задано скінченний автомат M = {A, S, Z, , }. Потрібно замінити автомат М автоматом M = {A, S, Z, , } з меншою кількістю внутрішніх станів, але так, щоб М переробляв вхідні послідовності у вихідні так само, як це робить М.
Означення 2. Автомат М покриває автомат М, якщо вони обидва мають однакові вхідні та вихідні алфавіти, й існує таке відображення : S S, що
r(s,
)
=
((s),
)
A.
Автомат, який не можна покрити автоматом з меншою кількістю внутрішніх станів, називають мінімальним.
Означення 3. Автомати М і М називають еквівалентними, якщо М М і М М.
З означень випливає, що відношення еквівалентності автоматів є рефлексивним, симетричним і транзитивним.
Означення 4. Стани si та sj автомата М називають r-еквівалентними і пишуть si ~r sj, якщо для кожного вхідного слова Ar
r(si, ) = r(sj, ).
Якщо si ~r sj для всіх r, то стани si та sj називають еквівалентними.
Задача мінімізації заданого автомати зводиться до відшукання еквівалентних станів, а тоді до їх ототожнення.
Наведемо один важливий приклад скінченного автомата, який реалізує додавання x + y натуральних чисел x + y, записаних у двійковій системі числення
x = xnxn – 1…x1 і y = ynyn – 1…y1,
де xi, yi {0, 1}.
Розглянемо відомий алгоритм додавання чисел x і y „стовпчиком”
де qn + 1, qn, …, q1 – результат перенесень з попередніх розрядів:
q1 = 0,
qi
+ 1
=
(1)
Маємо
zi = xi + yi + qi (mod 2). (2)
З іншого боку, легко перевірити, наприклад, складаючи таблиці значень для булевих функцій, заданих формулами (1), (2), що
qi + 1 = xiyi xiqi yiqi.
Так само, складаючи таблиці значень для булевих функцій, перевіряємо тотожність
xi
+ yi
+
qi
(mod
2) =
(
xi
qi
yi)
(xiyiq). (3)
Використовуючи рівність (3), можна одержати схему (яка полягає в знаходженні для заданої булевої функції такого виразу, який мав би „простий вигляд”), що перетворює трійку чисел xi, yi, zi у двійку чисел zi, qi + 1. Позначимо цю схему через si. Тоді суматор – пристрій, що реалізує додавання чисел, можна зобразити у вигляді такої діаграми:
zn
+ 1
Sn
xn
yn
zn
qn
+ 1
…
q3
S2
x2
y2
z2
q2
S1
x1
y1
z1
q1
