WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій - Реферат

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

Марковим, або НА-обчислюваною, якщо iснує НА, який її обчислює.
Зауважимо, що кожний НА обчислює безліч функцій натуральних аргументів та значень, але зафіксовуючи наперед арність функцій, дістаємо, що кожний НА обчислює єдину функцію заданої арності.
Приклад 2. НА для функцiї f(x, y)=x+y:
#
Приклад 3. НА для функцiї f(x, y)=x-y:
|#| #
#| #|
#
Приклад 4. НА для функцiї f(x)=x/2:
#|| |#
#| #|
#
#
Приклад 5. НА, який кожне слово виду ax переводить в слово :
da add
ad d
d d
d
Приклад 6. НА для функцiї f(x)=2х:
| |
|
# |#
#
#
Приклад 7. НА, який кожне слово виду axby переводить в слово dxy :
ab bad
db bd
a
b d
Приклад 8. НА для функцiї f(x, y)=x y:
#
| а
| b
аb ba|
|b b|
a
b
Приклад 9. НА, який переводить натуральні числа із 1-ї в 10-ву систему числення:
# |10 |#
# |9 9
# |8 8
… …
#| 1
# 0
| #|
9 9
8 8
… …
1 1
0
Приклад 10. НА, який кожне слово x T* переводить в його дзер-кальне відображення слово xR T* (тут # Т):
#ab b#a для всіх a, b Т
##a# a## для всіх a Т
##
#
4. СИСТЕМИ ПОСТА
Канонiчною системою Поста над алфавiтом T називають формальну систему (T*, A, P), в якої множина аксiом A є скiнчен-ною підмножиною множини T*, а множина правил виведення P складається з слiв вигляду 0S1 1... m-1Sm m . Тут T, всі k та і фiксованi слова iз T* , всі символи Sk T, причому всi ji {1,...,m}.
Символи Sk призначенi для позначення довiльних слiв iз T*.
Системи Поста звичайно позначають у вигляді P =(T, A,P).
Множина правил P визначає на словах iз T* вiдношення безпосереднього виведення таким чином: ==>Р , якщо iснує правило 0S1 1... m-1Sm m P таке, що для деяких слiв 1, ..., m T* маємо = 0 1 1... m m , = .
Рефлексивно-транзитивне замикання в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={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 : Nk?N обчислювана за Постом, якщо породжуваною за Постом є множина { (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 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. Cистема Поста для функцiї ;
A ={##};
P ={X#Y#R X|#Y|#R,
X##R X|##R|,
#Y# #Y|# }.
Приклад 6. Cистема Поста для функцiї f(x, y)=|x y| :
A ={##};
P ={X#Y#R X|#Y|#R,
X##R X|##R|,
X#Y#R Y#X#R }.
Приклад 7. Система Поста для функцiї f(x, y)=x y :
A ={##};
P ={X#Y#R X|#Y#RY,
X#Y#R X#Y|#RX }.
Приклад 8. Система Поста для функцiї f(xy)=x2 :
A ={#};
P ={X#R X|#RХХ| }.
Приклад 9. Система Поста для функцiї f(x)=2x :
A ={#};
P ={X#R X|#RR }.
Приклад 10. Cистема Поста для функцiї f(x, y)=max(x, y):
A ={##};
P ={X#X#X X|#X|#X|,
X#XS#XS X#XS|#XS|,
XS#X#XS XS|#X#XS| }.
Приклад 11. Система Поста для функцiї f(x, y)=x+2y :
A ={## |};
P ={X#Y#XS X|#Y#XS|,
X#Y#XS X#Y|#XSS }.
Приклад 12. Система Поста для функцiї f(x, y)=x y2:
A ={##};
P ={X##R X|##R|,
X#Y#RYY| X#Y|#R }.
Приклад 13. Система Поста для функцiї f(x)=x2 2x:
A ={#, ||#};
P ={X|#R X||#RXX| }.
В цьому прикладі треба врахувати, що f(1) .
Приклад 14. Система Поста для функцiї f(x)=x3 :
A ={ };
P ={X Q R X| QХХ| RQQQXXX|,
X Q R X#R }.
Для обчислення значення f(x+1)=(x+1)3=f(x)+3x2+3х+1 потрібне x2, тому теоремами СП мусять також бути коди трійок (х, x2, x3). Але теоремами в алфавіті {|, #} можуть бути тільки коди елементів графіка f(x), тому для кодування трійок (х, x2, x3) використано .
Приклад 15. Система Поста для функцiї f(x)=x! :
A={#|};
P ={X#F X| F ,
S F A B M S F A| B MB,
S F A B M S F A B| MA,
S F S F M S#M }.
До теорем СП належать коди 5-рок (х+1, x!, a, b, ab), для їх коду-вання використано . Із кодів 5-рок (х+1, x!, х+1, x!, (х+1) x!) можна вивести закодовані в алфавіті {|, #} коди пар (х+1, (х+1)!).
Приклад 16. Система Поста для функцiї f(x)= :
A={ };
P ={X X| ,
QS| Q R QS| QRR| R|,
X X R X#R,
X XS| R| X#R }.
До теорем СП належать коди трійок (х, r2, r), для їх кодування використано . Із кодів трійок (х, x, r) та (х, (r+1)2, r+1) при умові r2 х<(r+1)2 можна вивести закодовані в алфавіті {|, #} коди пар (х, r).
Приклад 17. Система Поста для предикату "x=y":
A ={## |};
P ={X#Y#R X|#Y|#R|,
X##R X|##,
#Y#R #Y|# }.
5. ОБЧИСЛЮВАНІСТЬ КВАЗИАРНИХ ФУНКЦІЙ НА N
Основними обчислюваними операцiями для випадку еквітонних V-квазиарних функцій на множині N є параметричні операцiї суперпозицiї S , примiтивної рекурсiї Ry,z та мiнiмiзацiї My .
Операцiя примiтивної рекурсiї Ry,z з параметрами у, z двом V-квазиарним функцiям g та h ставить у вiдповiднiсть V-квазиарну функцiю f, яку позначають Ry,z (g, h).
Для кожного d VN значення f(d) визначається таким чином:
при у іт(d) значення f(d) невизначене;
при у іт(d) значення f(d) визначається рекурсивною схемою
f(d уa0) = g(d уa0 za0);
f(dуaа+1) = h(d уaа zaf(d уaа)) для всіх aЦе означає, що для всiх d VN таких, що у іт(d) та d(y)=b, значення f(d) обчислюється так:
f(d уa0) = g(d уa0 za0);
f(d уa1) = h(d уa0 zaf(d уa0))
... ... ... ... ... ... ... ... ... ... ...
f(d) = f(d уab) = h(d уab-1 zaf(d уab-1)).
Операцiя мiнiмiзацiї My з параметром у V-квазиарній функцiї g ставить у вiдповiднiсть V-квазиарну функцiю f, яку позначають My(g). Для кожного d VN значення f(d) визначається як перше а N
Loading...

 
 

Цікаве