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

(((0

Приклад 10. НА, який кожне слово x(T* переводить в його дзер-кальне відображення \xF02D слово xR(T* (тут #(Т):

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

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

##(((

((#

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

. Тут ((T, всі (k та (і \xF02D фiксованi слова iз T* , всі символи Sk(T, причому всi ji({1,...,m}.

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

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

.

( означає, що слово ( отримане iз слова ( за допомогою скiнченної кiлькостi застосувань правил iз P.

( для деякої ((A. Цей факт записуємо P |\xF02D( i називаємо таке слово ( теоремою системи Поста P.

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

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

Приклад 1. Система Поста iз A={a,b,(} та 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й за Постом \xF02D це породжуванiсть за Постом графiкiв таких функцiй.

( (x1,...,xk)(Df }.

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

Приклад 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\xF02Dy :

A ={##};

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

X#Y#R|(X#Y|#R }.

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

A ={##};