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

Канонiчною системою Поста над алфавiтом T назвемо формальну систему (T*, A, P), у якій множина аксiом A є скiнченною підмножиною множини T*, а множина правил виведення P складається зі слiв вигляду a₀ S ₁a₁ ... a _{m- 1} S_m a _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 -1} S_m a _m® Î P,

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

s=a₀j₁a₁...j _m a _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 |#}.

.

Дата добавления: 2014-11-08