PMI_Nazarova_Diskretnye_struktury
.pdf11
Приклад 9. Функція знак sg( x ) – аналог функції sign( x ) для
натуральних чисел.
0, x = 0,
sg( x ) =
1, x ≠ 0.
Функція sg( x ) примітивно-рекурсивна:
sg( 0 ) = 0,
sg( x + 1 ) = 1.
При доведенніпримітивної |
|
|
|
|
|
рекурсивностіфункційнеобов |
'язковоявним |
||||||||||||||||||||
чиномвикористовувати |
|
операторприм |
ітивної рекурсії. |
|
|||||||||||||||||||||||
Приклад 10. Функція |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
sg( x ) ітакожє |
|||
sg( x ) – антизнак, функціязворотнадо |
|||||||||||||||||||||||||||
примітивно-рекурсивною: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
1, |
x = 0 |
|
|
|
• |
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
sg( x ) = |
x > 0 |
= 1 |
sg( x ). |
|
||||||||||||||||||||
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
0, |
|
|
|
|
|
|
|
|
|
|
|||||||||
Приклад 11. Примітиврекурсивністьфункційа |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
max( x, y ), min( x, y ) і |
||||||||||||
модуль різниці двох чиселдоводитьсяза |
|
|
|
|
|
|
|
|
|
|
допомогоюарифметичного |
||||||||||||||||
віднімання: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
max( x, y ) = y + ( x |
• |
|
y ) = x + ( y |
• |
x ), |
|
|||||||||||||||||||
|
|
|
|
|
|||||||||||||||||||||||
|
|
min( x, y ) = x |
• |
( x |
• |
y ) = y |
• |
( y |
• |
x ), |
|
||||||||||||||||
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
x − y |
|
= ( x |
• |
y ) + ( y |
• |
x ). |
|
||||||||||||||||||
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
||||||||||||||||||||||
Розглядрядуприкладівдозволяєсформ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
улюватидеярекіомендації |
||||||
відноснотого,яксліднамагвстпратновирекурсивністьсямітивнуякої |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
- |
|||||||||||
небфу. нкціїдь |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1. По-перше,сліднамагатисявирази |
|
|
|
|
|
|
тидануфункціючерезвідомі |
|
|||||||||||||||||||
примітивно-рекурсивні функціїзадопомогою |
|
|
|
|
|
|
|
оператору суперпозиції. |
|||||||||||||||||||
2Якщо. |
всежтакинеобхідноявикористовуватиоператор |
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
примітивноїрекур,слідпостакиміїтупатичином: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
– визн, якоюачитизмінноюпроводитьсяпримітивнарекурсія;
|
|
|
|
12 |
– визначитизначенняформулу( )досліджпринукціїльовомуваної |
|
|
||
значезмітим(ннсамоїі |
отримавшипершуформулусхемипримітивної |
|
||
рекурсії); |
|
|
|
|
– виявити,якзалежитьзначенданоїфувідїїжзначеннякції |
|
|
а |
|
попекрекурсіїоцідньомуз, |
|
аписатинаосновіцьогодругогоформулу |
|
|
схеми. |
|
|
|
|
Слідматинаувазі,якщофункціяневсюдивизначена( |
|
|
тобто |
|
часткова),товонанепримітивно |
-рекурсивна. |
|
||
|
Примітивнарекурсивн |
ість логічнихфункц |
ій |
Примітивно-рекурсивнимиможутьбутинел аришефункціїметичні,
алеі арифметизовані« »логічніфункції,відноше,предикати, зніня оператори.
«Арифметизована» |
логічнафункція |
– цетакачисловарифметична |
||
функція,якамножині{0,1}поводитьсятаклогічна |
|
|
|
функція. |
Операції {←, , } на множині {0,1} примітивно-рекурсивні: |
||||
|
x = 1 |
• |
x; |
|
|
|
|
||
|
x y = min( x, y ); |
|||
|
x y = max( x, y ). |
Функції {←, , } намножині |
|
{0,1} утворююбазис,отже, осітанніь |
||||||||
арифметизованілогічніфункції |
|
|
|
|
можутьбутипредставленівигляді |
|||||
суперпозиціїцихтрьохфункцій,а,отже,завизначеннямпримітивної |
|
|
|
|
|
|
|
|
|
|
рекурсвонипр вностімітивно |
|
|
-рекурсивні. |
|
|
|
|
|||
Відношення |
R( x1 ,x2 ,...,xn ) |
– |
|
примітивно-рекурсивно, якщо |
||||||
примітивно-рекурсивнайогохарактеристичнафункція |
|
|
|
|
|
|
χ R : |
|||
|
|
|
|
|
1, ( x1 ,x2 ,...,xn ) R |
|||||
|
χR( x |
|
|
= |
|
|
|
|
|
|
|
,x |
,...,x ) |
|
|
|
|
|
|
||
|
1 |
2 |
n |
|
0,( x ,x |
|
,...,x |
|
) R. |
|
|
|
|
|
|
2 |
n |
||||
|
|
|
|
|
|
1 |
|
|
||
Приклад 12. Відношення x = y , |
x > y , |
x ≥ y – примітивно-рекурсивні. |
13
Відношення x = y – |
примітивно-рекурсивно,томущопримітивно |
|||||||||||
рекурсивнайогохарактеристичнафункція,тобтозавизначенням |
|
|
|
|
|
|
|
|
|
|
|
. |
1, |
x = y |
|
|
|
|
|
|
|
|
|
|
|
= sg |
|
( x − y ) |
|
. |
|
|
|
|||||
Дійсно, χ= ( x, y ) = |
|
|
|
|
|
|
||||||
0, |
x ≠ y |
|
|
|
|
|
|
|
|
|
|
|
Відношення x > y також примітивно-рекурсивно,бо : |
||||||||||||
|
1, |
|
x > y |
|
|
|
|
|
|
|||
χ> ( x, y ) = |
|
x ≤ y |
= sg( x |
y ). |
|
|||||||
|
|
|
||||||||||
|
0, |
|
|
|
|
|
|
|
||||
Відношення x ≥ y примітивно-рекурсивно,томущо |
: |
χ≥ ( x, y ) = χ> ( x, y ) + χ= ( x, y ),
χ≥ ( x,y ) = sg( x y ) + sg ( x − y ) .
Предикат – функція,якавизначаєчиволодіютьїїаргументипевними |
|
властивостямичині,повертаєзначення: |
{0,1}, {false, true}. |
Предикат P( x1 , x2 ,...., xn ) є |
примітивно-рекурсивним, якщо |
примітивно-рекурсивнайогохарактеристичнафункція: |
|
1, P =" true"
χP ( x1 ,x2 ,...,xn ) = .
0, P =" false"
Оператор називається примітивно-рекурсивним,якщовінзберігає
примітиврекурсивністьфу,тобтоякщокційрезультатйого |
|
|
|
|
|
застосування |
|
допримітивно |
-рекурсивнихфункційдаєзнову |
|
|
|
|
|
примітивно-рекурсивну |
функцію. |
|
|
|
|
|
|
|
Приклад 12. Примітивнарекурсивність |
|
|
|
оператора умовного переходу |
|||
B( P1 ,P2 ,P ) |
|
|
|
|
|
|
|
|
B( P ,P ,P ) = |
P1( x1 ,x2 |
,...,xn |
), |
P = " true" |
||
|
|
|
|
|
|
, |
|
|
1 2 |
|
|
,...,x |
|
), |
P = " false" |
|
|
P ( x ,x |
2 |
n |
|||
|
|
2 1 |
|
|
|
||
де P1 та P2 – примітивно-рекурсивніфункції |
|
|
|
; P – примітивно-рекурсивний |
|||
предикат. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14 |
Примітивнарекурсивність |
|
оператору умовного переходу B слідкуєіз |
|||||||||
рівності: |
|
|
|
|
|
|
|
|
|
|
|
B( P1 ,P2 ,P ) = P1( x1 ,x2 ,...,xn ) χP + P2 ( x1 ,x2 ,...,xn ) χ |
|
, |
|
||||||||
P |
|
||||||||||
Більшарифметичнихілогічстьфуєпримітивнокцій |
|
|
|
|
|
|
|
|
- |
||
рекурсивними.Протекласпр |
|
имітивно-рекурсифункційнеохоплюєвнихсіх |
|
|
|
|
|||||
обчислюванихінтуїтивнсенсіфункцій.Дляп будовимуостанніхфункцій |
|
|
|
|
|
|
|
|
|
||
використовуєтьсятакзванийоператормінімізації. |
|
|
|
|
|
|
|
|
|
|
|
Оператормінімізації |
( - оператор, найменшого |
|
|
кореню) |
|||||||
утвноарвуифметичнуює |
|
|
функцію |
f ( x1 ,x2 ,...,xn ) від |
n зміннихза |
|
|||||
допомогою ранішпобудоваметичноїариф кції |
|
|
|
g( x1 ,x2 ,..., xn ; y ) |
від |
||||||
n+1 змінних. |
|
|
|
|
|
|
|
|
|
|
|
Нехайіснуєподеякиймеханізм |
|
|
|
|
обчислення функції g , причому |
||||||
значенняфункції |
f |
невизначено, якщоцей |
|
механізм працюєнескінченно |
, не |
||||||
утворюючініякоговизначеногозначення |
|
|
|
. |
Зафіксуємопевний |
набір значень |
|||||
аргументів |
x1 , x2 ,..., xn |
ірозглянемо |
|
|
рівнявідносноня |
|
|
|
y: |
||
g( x1 ,x2 ,...,xn ; y ) = 0 . |
Длятого,щотбриматиозв |
|
|
’язокцьогорівняння |
, |
||||||
будемообчислюватипослідовзначеність |
|
|
|
: |
g( x1 ,x2 ,...,xn ; y ) = 0 |
для |
|||||
y = 0,1,.. |
|
|
|
|
|
|
|
|
|
|
|
.. |
|
|
|
|
|
|
|
|
|
|
|
Найменше ціле невід’ємне |
|
значення y = a , якезадовцьомульняє |
|
||||||||
рівнянню: g( x1 ,x2 ,...,xn ,a ) = 0 |
позначимо: y ( g( x1 ,x2 ,...,xn ; y ) = 0 ). |
|
|||||||||
Кажуть, |
що |
функція |
f ( x1 ,x2 ,...,xn ) |
утворенаізфункції |
|
||||||
g( x1 ,x2 ,..., xn ; y ) операцією мінімізації, якщо: |
|
|
|
|
|
||||||
|
f ( x1 ,x2 ,...,xn ) = y ( g( x1 ,x2 ,...,xn ; y ) = 0 ). |
|
|
|
|
||||||
Операторм |
інімізації працюєнескінченно,якщо |
|
|
: |
|
|
|
|
|||
1) значення g( x1 , x2 ,..., xn ,0 ) не визначено; |
|
|
|
|
|
||||||
2) значення |
g( x1 ,x2 ,...,xn , y ) для |
y = 0,1,2,....,i −1 |
визначено, |
але |
|||||||
відміннонуля |
,а значення g( x1 ,x2 ,...,xn ,i ) – не визначено; |
|
3) значення g( x1 ,x2 ,...,xn , y )
дорівннулює .
Приклад1 3. Процесобчисленняфункції мінімізації:
f ( x, y ) = x2 .
f ( 6 ,34 ) = ?
f ( 6 ,34 ) = 36
z = 0;
z = 1;
15
визначено для усіх y = 0,1,2,....,i −1, але не
z x + y .x + z
за допомогою оператору
z = 0
. |
|
|
|
|
40 |
|
. |
z = 0 |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|||||
|
|
z |
|
|
|
|
|||
|
|
|
6 |
+ z |
|
|
|
. |
|
|
|
40 |
|
. |
0 |
≠ 0 |
|
|
|
|
|
|
|
||||
|
|
|
|
|
|||||
|
|
z |
|
|
|
|
|
||
|
|
|
6 + 0 |
|
|
|
|
|
. |
|
|
|
40 |
|
|
. |
1 |
≠ 0 |
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|||||
|
|
z |
|
|
|
|
|
|
||
|
|
|
6 + |
1 |
|
|
|
|
|
|
|
|
|
. |
|
|
|
40 |
|
|
. |
|
|
|
|
|
||||
|
z = 2; |
f ( 6 ,34 ) = 36 |
|
|
|
|
|
|
|
|
|
2 |
≠ 0 |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
z |
|
2 |
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
6 + |
|
|
|
|
|
|
|
|
||||
|
z = 3; |
f ( 6 ,34 ) = 36 |
. |
|
|
|
40 |
|
|
|
|
. |
|
3 |
≠ 0 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
z |
6 + |
3 |
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
z = 4; |
f ( 6 ,34 ) = 36 |
. |
|
|
|
40 |
|
|
|
. |
|
4 |
= 0 |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
z |
6 + |
4 |
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
f ( 6 ,34 ) = 36 |
. |
4 = 32. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
Приклад 14. Оператор мінімізації є засіб для утворення зворотніх |
|||||||||||||||||||||
функцій. Так, функцвіднможебіманняутиворенаізопераціїдодавання |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
зарахунзастосуванняк |
оператору мінімізації: |
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
f−( x, y ) = x − y = µ z ( y + z = x ). |
|
|
|
|||||||||||||||||
При x=5, y=2 змінна z приймаєзначення |
|
|
|
|
|
|
|
0,1,2,3.Значе |
ння z=3 |
||||||||||||
являється |
шуканим,боізрівнян |
|
ня |
|
y + z = x |
|
утвотожністьрює |
: |
|||||||||||||
y + z = 2 + 3 = x = 5,отжез |
начення |
f− ( 5, 2 ) = 3. |
|
|
|
|
При x=4, y=6 |
змінна z |
|||||||||||||
приймаєзначення |
0,1,2,3,4,...жодне, |
|
|
|
ізнихнезадовольняєрівняння |
|
|
|
|
|
|
|
|
|
|
|
|
|
16 |
y + z = x,оператормінімізаціїприцьомупрацює |
|
|
|
|
|
|
ескінченно,отже |
||||
значення f− ( 4,6 ) невизначено. |
|
|
|
|
|
|
|
|
|||
Відповідно,вводятьсяфункції |
|
|
|
|
|
|
ділення, |
обчисленнякореню |
|
||
квадратного,логарифм |
: |
|
|
|
|
|
|
|
|
|
|
|
f / ( x, y ) = x y = z ( y z = x ), |
|
|
|
|||||||
|
f |
|
( x, y ) = x |
|
= z ( z x = y ), |
|
|
|
|||
|
|
y |
|
|
|
||||||
|
|
|
|
|
|||||||
|
f log ( x, y ) = log x y = z ( x z |
= y ). |
|
|
|
||||||
Частково - рекурсивна функція – функція, якаможебутиворенаіз |
|
|
|||||||||
найпростішихфункційзадопомогоюскінченнчислазастосуваньго |
|
|
|
|
|
|
|
|
|
||
операторівсуперпозиції , примітивноїрекурсії |
та мінімізації. |
|
|
||||||||
Частково - рекурсивнафункціяє |
|
|
|
не усюди визначеною, |
причому там, |
||||||
де вонеа визначена,процесс їїобч |
ислення продовжується нескінченно. |
||||||||||
Загально - рекурсивнафункція |
– усюди |
визначена |
частково- |
||||||||
рекурсивна функція. |
|
|
|
|
|
|
|
|
|
||
Клчастково |
-рекурсивнихфункцій |
|
|
|
(ЧРФ) |
ширшийзаклзагальнос |
|
- |
|||
рекурсивних (ЗРФ) |
функцій,який,своючергуширшезакласпримітивно |
|
|
|
|
- |
|||||
рекурсивнихфункцій |
(ПРФ) |
(див.рис. 1 |
). |
|
|
|
|
|
Рисунок1 |
– Співвмкласамиіждношеннячастково |
|
-,загально - та |
|
примітивно-рекурсивнихфункцій |
||
Зв'язок міжалгоритмами тарекурсивни |
ми функціями дає теза Черча: |
||
класалгоритмібчислювачисловихчасткнофункційзб |
|
ігаєтьсяз |
|
класомчастково |
-рекурсивнихфункцій |
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
17 |
|
|
|
Тема №2 |
|
|
|
|
|
||||
|
|
МАШИНИТЬЮРІНГА |
|
|
|
|
|
|||||
МашиниТьюрінга |
|
(МТ) |
представляють |
алгоритм, |
як |
деякий |
||||||
детермінованийпристрій |
|
(автомат),що |
|
|
реалізуєдію |
|
надсловами. |
Машина |
||||
ТьюрінгаТьюрінга( |
-Посту,томущозапропоновананими |
|
|
|
|
|
майжеод |
ночасноі |
||||
незалежноу1936 |
-1937рр.поб) |
уднаосновіванавикоривластивостіання |
|
|
|
|
||||||
детермінованостіалгоритмів. |
|
МашинаТьюрі |
|
|
|
нгаєабс,трактноющомаєу |
|
|
|
|||
необмеженіресурси,щоєнеобхіднимдляреалізаціїбудь |
|
|
|
|
|
|
|
-якихалгоритмів. |
|
|||
Уданійтемівводят |
|
ьсядеякіпоняттясимвольнихконструкційта |
|
|
|
|
|
|||||
операційнадними, функцісаніспособизавданнуваМТ,способиння |
|
|
|
|
|
|
|
|
|
|
|
|
композиціїМТ,щод зволяюбільшбудувасклМТтдніпростих, |
|
|
|
|
|
|
|
|
|
|
|
|
наводитьсяпоняттяпроеквівалентністьМТрекурсивнихфункцій. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Символьніконструкції |
|
|
|
|
|
|||||
Алфавіт – |
кінцева |
множина попарнорізн,аківих |
|
|
які |
називають |
||||||
буквами (символами)цьогоалфавіту.Алфавітбудемопозначати |
|
|
|
|
|
|
|
|
|
|
||
заголобук,напрвнимиами: клад |
|
|
À = {a,á ,....ÿ}; |
B = {0,1}; |
C = { ,+,! ,0}. |
|||||||
Символ λ – порожнійсимвол. |
|
|
|
|
|
|
|
|
|
|
||
Словом уданомуалфавітіназиваєтьс |
|
|
|
|
ябудь |
-якінцевау(томучислій |
|
|
|
|||
пор) ожняслідовністьбуквцьогоалфавіту.Словабудемопозначати |
|
|
|
|
|
|
|
|
|
|
|
|
малимигрецькибуквами. |
|
|
|
|
|
|
|
|
|
|
|
|
Наприклад: |
α =алгоритм |
– словоалфавіті |
|
А; β = 1010100 – слово |
||||||||
алфавіті В; γ = +0 |
– словоалфавіті |
С. |
|
|
|
|
|
|||||
Порожнєсловобудемоп значати |
|
|
|
Λ. |
|
|
|
|
|
|||
Довжина слова α (позначається |
|
α |
|
) – цекількість букв |
слові. |
|
||||||
|
|
|
||||||||||
Рівнслівсть |
валфавіті А визначається індуктивно: |
|
|
|
||||||||
а)порожслорівніа |
|
; |
|
|
|
|
|
|
|
|
|
|
б)якщослово |
α дорівнюєслову |
|
|
|
β ,то |
αb = βb ,де |
b – |
буква в |
||||
алфавіті А. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
18 |
|
Якщослово |
|
α |
є |
частиноюлова |
|
|
β ,то |
|
кажуть,щомаємісце |
|
|
||||||||||
входження слова α услово β (слово |
α називається підсловом слова β )Це. |
||||||||||||||||||||
можназапивт спосібкийати: |
|
|
|
|
|
|
γ,δ( γαδ = β ),де |
|
γ,δ – словаалфавіті |
|
А. |
||||||||||
Слово α називається початкомслова |
β ,якщо |
γ( αγ = β ); кінцем |
|||||||||||||||||||
слова β ,якщо |
γ( γα = β). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
Наприклад:услові1012011201 |
|
|
|
|
|
двходженняасло12,тривходженняа |
|
|
|
|
|||||||||||
сл01,овадинадцятьвходженьпорожньогослова |
|
|
|
|
|
|
|
|
Λ – передпершоюбуквою |
, |
|||||||||||
післяостанньої |
|
іміжвсімабуквами. |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
Слдовожини |
n, |
складенезбукви |
|
|
а,повтореної |
n раз,будемо |
|||||||||||||||
позначати an ,наприклад |
xyxxxyyyy = xyx3 y4. |
|
|
|
|
|
|
|
|
|
|||||||||||
Операціярезультат( )приписуванняслів |
|
|
|
|
|
|
|
|
α |
і β |
другдодруга |
||||||||||
називається |
конкатенацією |
(позначається |
α || β)Наприклад. ,якщо |
|
|
||||||||||||||||
α = aabbcc ; β = abc |
α || β = aabbccabc . |
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
Визначення йспособизавданнямашини |
|
|
|
Тьюрінга |
|
|
|||||||||||||
ПідмашиноюТьюрінгарозумієтьсядеяка |
|
|
|
|
|
|
|
|
гіпотетичнааб( |
страктна) |
|||||||||||
машина,що |
складається знаступнихчастдив(.р. 1 |
|
|
|
|
|
). |
|
|
|
|
|
|||||||||
1) нескінченнавобидвабокистрічка, |
|
|
|
|
|
|
|
розбитана |
комірки,укожнійз |
||||||||||||
якихможебутизаписаний |
|
|
|
|
|
|
тількиодс мволн |
|
|
із |
зовнішнього |
алфавіту |
|||||||||
A = { a1 ,a2 ,....,an } ,атакпорожнійсимвол |
|
|
|
λ ; |
|
|
|
|
|
|
|
|
|||||||||
2) керуючийприст |
|
рій( |
робоча |
голівка),щоу |
|
|
кожниймоментчасу |
|
|
||||||||||||
можеперебува |
|
ти водномузістанів |
|
|
|
множини Q = { q1 ,q2 ,...,qm }.У |
|||||||||||||||
кожному зі станівголівка |
|
|
розміщуєтьсянапроти |
|
коімзчитуватиіркиоже |
|
|
||||||||||||||
(оглядати) |
абозаписувати |
|
в комірку букву ізалфавіту А. |
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
...... |
|
λ |
a |
|
...... |
a j |
|
...... |
ak |
|
λ |
|
λ |
...... |
|
|
|||
|
|
|
|
|
|
l |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
qi
Рисунок1 – МашинаТьюрінга
|
|
|
|
|
|
|
|
|
|
|
19 |
Частинастрічки,вякійзаписані |
|
символи |
алфавітуА |
|
(відпершого |
||||||
значущостанньогосимвдоолу |
: al ,…, ak ) – |
робочазона. |
|
|
|
|
|||||
ФункціонуванняМТскладаєтьсязпос |
|
|
лідовностіелементарнихкроків |
|
|
||||||
(та)Укожному. тівкроцівиконуютьсянаступнідії: |
|
|
|
|
|
|
|
|
|
||
1) |
керуючийпристрій |
(КП) зчитує( |
оглядає)символ |
a j ; |
|
||||||
2) |
залежновідсвог |
стану qi йсимволу |
a j , |
КП |
виробляє |
новий |
|||||
символ aʹj A ізаписує його комірку,що оглядаєтьсяКП |
(можливо a j |
= aʹj ); |
|||||||||
3) |
керуючийпристрій |
переміщуєтьсяна |
одну |
комірку |
вправо (R) , |
||||||
вліво (L) або залишається намісці (E); |
|
|
|
|
|
|
|
|
|||
4) |
керуючийпристрій |
переходитьвіншийвнутрішній |
|
|
|
|
стан qiʹ. |
||||
(можливо qi = qiʹ ). |
|
|
|
|
|
|
|
|
|
||
Стан q1 називається початковим, |
qz |
– |
заключним.Припереходів |
|
|
||||||
заключнстанмашзупиняється.най |
|
Повнийстан |
|
МТназивається |
|||||||
конфігурацією.Церозподіл |
букв по комірках стрічки, |
стан робочоїголівки |
і |
||||||||
комірка,щооглядається |
|
. |
|
|
|
|
|
|
|
|
|
Конфігураціявтакті |
t записуєтьсявигляді |
|
|
: |
|
|
|
|
|
||
|
|
|
Kt = αqi a j β, |
|
|
|
|
|
|
||
де a j – буква укомірці,щооглядаєтьсяКП |
|
|
, |
α – підслово ліворучід |
|||||||
цієїкомірки |
, β – підслово праворуч від цієїкомірки . |
|
|
|
|
||||||
Початковаконфігурація |
K1 = q1α |
йкінцева |
|
K z = qz α |
називаються |
||||||
стандартними. |
МТпочинаєізакінчуєсвроботувютакомустанов,колищі |
|
|
|
|
|
|
|
|
||
КПоглядаєсамийлівийсимволробо |
|
чоїзонистрічки. |
|
|
|
|
|
|
|||
Формальневизн Тьюрінгашиничення |
|
|
: |
|
|
|
|
|
|
||
|
|
|
MT = M ( A,Q,V ,q0 ,qz ,δ ), |
|
|
|
|
||||
де A – зовнішнійалфавітсимволів, |
|
|
|
|
|
|
|
|
|
||
Q – алфавітвнутрістанівмашини, ніх |
|
|
|
|
|
|
|
|
V – алфавітдопустимихрухів,
q0 ,qz – почтазаткстанилючнийовий,
20
δ = A×Q → A×Q ×V – функціяпереходів. |
|
||
Для описуроботиМТіснуєспособи3 |
|
: |
|
1) |
системакоманд |
абопрограмаМТ |
; |
2) |
функціональнатаблиця |
; |
|
3) |
граф ( діаграма )переходів. |
|
Системакомандпрограма( )МТ |
– це сукупність командвиду |
: |
|
|
qi a j → qiʹaʹj s; s {R,L,E}. |
|
|
СистемакомандМТ |
будуєтьсязаправилами |
: |
|
1)початковомукрокуалгоритмуста ідитьсяпочатковийовідність
стан;
2)сусіднімкрокамалгоритмувідперехідовідаєсуміжністани,які відповідаютьцимпунктам ;
3)циклиреалізуютьсятак,щоостанндіяциклуповідповідатиинна переходувтойстан,якийвідпочаткуциклвідає;
4)осткроканнійлгоритмувикликаєперехіддозаключногостану.
Приклад 1. ПобудуватиМТ,якаінвертуєчисладвійковійсистемі числення.
|
q0 1 → q0 0R |
q1 0 → q1 0L |
|
q0 0 → q0 1R |
q1 1 → q1 1L |
|
q0 λ → q0 λL |
q1λ → qz λR |
Комендосискомандт.ареми |
|
|
1)УстандарпочаконфігураціїтковійнійКПстоїтьнадпершим |
|
|
значущимсимволомліворуч, початкуробочоїзони. |
|
|
2)НаслідкуючомутактіМТ,незмінюєсвогостану,КПзамінює |
|
|
символна0і1 |
навпаки,ізсуваєтьсявправонаоди.мволн |
|
3)П іслеп реглядувсьоголанцюжкаКПглядвказуєсимвол,який |
|
|
напорко.УцьомуміркужнювипадкуМТпереходитьновийстані |
|
|
зсуваєтьсявлівонаоди.мволн |
|
|
4)НанаступнихтактахКПнезмінюючисвог |
остануіоглядаємого |
|
символу,перемвлдопорівощуєтьсяко.жньоїмірки |
|