Система Поста. Обчислюваність за Постом

Канонiчною системою Поста над алфавiтом T назвемо формальну систему (T*, A, P), у якій множина аксiом A є скiнченною підмножиною множини T*, а множина правил виведення P складається зі слiв вигляду a₀S₁a₁...a_m-1S_ma_m® . Тут ®ÏT, усі a_k та b_і - фiксованi слова iз T* , усі символи S_kÏT, причому всi j_iÎ{1,...,m}.

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

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

Множина правил P визначає на словах iз T* вiдношення безпосереднього виведення таким чином: sÞ_Р t, якщо iснує правило

a₀S₁a₁...a_m-1S_ma_m® ÎP,

таке, що для деяких слiв j₁, ..., j_mÎT* маємо

s=a₀j₁a₁...j_ma_m ,t= .

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

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

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

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

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

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

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

Часткова функцiя f : N^k→N обчислювана за Постом, якщо породжуваною за Постом є множина { ½(x₁,...,x_k)ÎD_f }.

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

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

A ={##};

P ={X#Y#R®X|#Y#R|,

X#Y#R®X#Y|#R| }.

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

A ={##};

P ={X#Y#R®X|#Y#R|,

X#Y#R|®X#Y|#R }.

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

A ={##};

P ={X#Y#R®X|#Y|#R,

X##R®X|##R| }.

Приклад 5. Система Поста для предиката "x=y":

A ={## |};

P ={X#Y#R®X|#Y|#R|,

X##R®X|##,

#Y#R®#Y|#}.

.