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

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

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

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

стрiчцi символ b та змiщує голiвку на 1 клiтку направо (відповідно на 1 клiтку налiво, залишає голiвку на мiсцi).
Конфiгурацiя, або повний стан МТ це слово вигляду xqy, де x,y T*, q Q. Неформально це означає, що на стрiчцi записане слово xy, тобто злiва i справа вiд xy можуть стояти тiльки символи , МТ знаходиться в станi q, голiвка читає 1-й символ пiдслова y.
Конфiгурацiю вигляду q0x, де 1-й та останнiй символи слова x вiдмiннi вiд , називають початковою. Конфiгурацiю вигляду xq*y називають фiнальною. Пiсля переходу до фiнального стану, отже, до фiнальної конфiгурацiї, МТ зупиняється.
Нехай МТ знаходиться в конфiгурацiї xcqay, де x,y T*, a, c T, q Q. Пiсля виконання команди qa pbR (команди qa pbL, команди qa pb) МТ перейде до конфiгурацiї xcbpy (вiдповiдно до конфiгурацiї xpcby, конфiгурацiї xcpby).
Кожна МТ задає вербальне вiдображення T* ?T* таким чином.
МТ М переводить слово u T в слово v T*, якщо вона з почат-кової конфiгурацiї q0u переходить до фiнальної конфiгурацiї xqy, де q F*, xy= v , , { }* . При цьому перший та останнiй символи слова v вiдмiннi вiд , або v= . Цей факт записуємо так: v=M(u).
Якщо МТ M, починаючи роботу з початкової конфiгурацiї q0u, нiколи не зупиниться, кажуть, що M зациклюється при роботi над словом u. Тодi M(u) не визначене.
МТ M1 та M2 еквiвалентнi, якщо вони задають одне і те ж вербальне вiдображення.
МТ M обчислює часткову функцiю f:Nk?N, якщо вона кожне слово вигляду переводить в слово у випадку (x1,...,xk) Df , та M( ) невизначене при (x1,...,xk) Df .
Функцiя називається обчислюваною за Тьюрiнгом, або МТ-обчислюваною, якщо iснує МТ, яка її обчислює.
Зауважимо, що кожна МТ обчислює безліч функцій натуральних аргументів та значень, але зафіксовуючи наперед арність функцій, дістаємо, що кожна МТ обчислює єдину функцію заданої арності.
Розглянемо приклади МT.
Приклад 1. МТ, яка обчислює функцiю x+y:
q0| q0|R
q0# q0|R
q0 q1 L
q1| q*
Приклад 2. МТ, яка обчислює функцiю f(x, y) =x-y:
q0| q1 R
q1| q1|R
q1# q1#R
q1 q2 L
q2| q3 L
q3| q3|L
q3# q3#L
q3 q0 R
q2# q*|
q0# q4 R
q4 q*
Приклад 3. МТ, яка обчислює функцiю f(x, y)=
q0| q1 R
q1| q1|R
q1# q1#R
q1 q2 L
q2| q3 L
q3| q3|L
q3# q3#L
q3 q0 R
q2# q*|
q0# q4 R
q4| q4 R (єдина відмінність від МТ для f(x, y) =x-y )
q4 q*
Приклад 4. МТ, яка обчислює функцiю f(x)=sg(x):
q0 q*
q0| q1|R
q1| q1 R
q1 q*
Приклад 5. МТ, яка обчислює предикат "x парне":
q0| q1 R
q1| q0 R
q0 q*|
q1 q*
Приклад 6. МТ, яка обчислює функцiю f(x, y)=x+2y:
q0| q0|R
q0# q0#R
q0 q1 L
q1| q2 R
q2| q2|R
q2 q3|L
q3| q3|L
q3 q1|L
q1# q4|L
q4| q4|L
q4 q5 R
q5| q*
Приклад 7. МТ, яка обчислює функцiю f(x)=2x
q0| q0|R
q0 q1aL
q1| q1|L
q1 q2 R
q2| q3 R
q3| q3|R
q3a q3 aR
q3 q4 L
q4a q5 R
q5a q5 aR
q5 q6 aL
q6a q6 aL
q6 q4aL
q4| q4|L
q4 q2 R
q2a q2|R
q2 q*
Приклад 8. МТ, яка обчислює функцiю f(x, y)=x y
q0# q1 R
q1| q1 R
q1 q*
q1a q1|R
q0| q2 R
q2| q2|R
q2# q3#R
q3| q4 R
q4| q4|R
q4a q4 aR
q4 q5 aL
q5| q5|L
q5a q5 aL
q5 q3|R
q3a q6 aL
q6| q6|L
q6# q6 #L
q6 q0 R
q3 q7 L
q7# q7 L
q7| q7 L
q7 q*
Приклад 9. МТ, яка обчислює функцiю f(x)=[x/3]:
q0 q*
q0| q1 L
q1| q2 L
q2| q2|R
q2 q3 L
q3 a q3 aL
q3| q4aL
q4| q4|L
q4 q0 R
q1 a q0 a
q2 a q0 a
q0a q0|R
Приклад 10. МТ, яка кожне слово х Т* переводить в слово х#х
(тут # T).
q0 t q0 tR для всіх t T
q0 q1#L
q1 t q1 tL для всіх t T
q1 q2 R
q2 t qt R для всіх t T
qt p qt pR для всіх t T, p T {#}
qt q't tL для всіх t T
q't p q't pL для всіх t T, p T {#}
q't q2tR для всіх t T
q2# q*#
3. НОРМАЛЬНІ АЛГОРИТМИ МАРКОВА
Пiд нормальним алгоритмом (скорочено НА) в алфавiтi T розумiють впорядковану послiдовнiсть продукцiй (правил) вигляду або , де , T* та , T. Продукцiї вигляду називають фiнальними.
Кожен НА в алфавiтi T задає деяке вербальне вiдображення T*?T*. Слово, яке є результатом обробки слова x нормальним алгоритмом A, позначимо A(x). Обробка слова x нормальним алгоритмом A проводиться поетапно таким чином.
Покладемо x0=x i скажемо, що x0 отримане iз x пiсля 0 етапiв. Нехай слово xn отримане iз слова x пiсля n етапiв. Тодi (n+1)-й етап виконується так.
Шукаємо першу за о порядком продукцiю або таку, що пiдслово xn. Застосуємо цю продукцiю до xn , тобто замiнимо в xn найлiвiше входження на . Отримане слово позначимо xn+1. Якщо застосована на (n+1)-му етапi продукцiя нефiнальна, тобто , то переходимо до (n+2)-го етапу. Якщо ця продукцiя фiнальна, тобто , то пiсля її застосування A зупиняється i A(x)=xn+1. Якщо ж на (n+1)-му етапi жодна продукцiя A не застосовна до xn+1, тобто в A немає продукцiї, лiва частина якої - пiдслово слова xn+1, то A зупиняється i A(x)=xn.
Якщо в процесi обробки слова x НА A не зупиняється нi на якому етапi, то вважаємо, що A(x) невизначене.
Нормальний алгоритм називають нормальним алгоритмом над алфавiтом T, якщо вiн є нормальним алгоритмом в деякому розширеннi T' T. НА над T задає певне вiдображення T*?T*, використовуючи в процесi обробки слiв допомiжнi символи поза алфавiтом T. Зупинка НА A над T при роботі над словом х T*, результативна, коли вона вiдбулась на словi y T*, iнакше вважаємо, що результат роботи A над х невизначений.
НА A i B еквiвалентнi вiдносно алфавiту T, якщо для всiх x T* A(x) та B(x) одночасно визначенi або невизначенi, та у випадку визначеностi A(x)=B(x).
Відомо [7], що для кожного НА над алфавітом Т існує еквiвалентний йому вiдносно T НА в алфавіті Т {s} з єдиним допоміжним символом s Т. Відомо також [7], що вербальне відображення, яке кожне слово x T* переводить в слово хх, не може бути заданим жодним НА в алфавіті Т. В той же час маємо
Приклад 1. НА, який кожне x T* переводить в слово xх (тут # Т):
##a a#а## для всіх a Т
#ab b#a для всіх a, b Т
#а а для всіх a Т
##
##
НА A обчислює часткову функцiю f:Nk?N, якщо він кожне слово вигляду переводить в слово у випадку (x1,...,xk) Df , та A( ) невизначене при (x1 ,...,xk) Df .
Функцiя називається обчислюваною за
Loading...

 
 

Цікаве