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

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

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

Приклад 1. НА, який кожне xT* переводить в слово xх (тут #Т):

##aa#а## для всіх aТ

#abb#a для всіх a, bТ

#аа для всіх aТ

##

##

НА A обчислює часткову функцiю f:Nk→N, якщо він кожне слово вигляду переводить в слово у випадку (x1,...,xk)Df , та A( ) невизначене при (x1 ,...,xk)Df .

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

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

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

Канонiчною системою Поста над алфавiтом T називають формальну систему (T*, A, P), в якої множина аксiом A є скiнчен-ною підмножиною множини T*, а множина правил виведення P складається з слiв вигляду 0S11...m-1Smm Тут T, всі k та і фiксованi слова iз T* , всі символи SkT, причому всi ji{1,...,m}.

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

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

Множина правил P визначає на словах iз T* вiдношення безпосереднього виведення таким чином: Р , якщо iснує правило 0S11...m-1SmmP таке, що для деяких слiв 1, mT* маємо 011...mm

Рефлексивно-транзитивне замикання вiдношення Р позначаємо . Інакше кажучи, означає, що слово отримане iз слова за допомогою скiнченної кiлькостi застосувань правил iз P.

Слово породжується системою Поста P, якщо для деякої A. Цей факт записуємо P | i називаємо таке слово теоремою системи Поста P.

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

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

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