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

1. МАШИНИ З НАТУРАЛЬНОЗНАЧНИМИ РЕГІСТРАМИ

Машина з натуральнозначними регiстрами (скорочено МНР) є iдеалiзованою моделлю комп’ютера. МНР мiстить, взагалі кажучи, нескiнченну кiлькiсть регiстрiв, вмiстом яких є натуральнi числа. Регiстри нумеруємо натуральними числами, починаючи з 0, позначаючи їх R0 , R1 , ..., Rn , ... Вмiст регiстру Rn позначаємо ’Rn .

Послiдовнiсть (’R0 , ’R1, ..., ’Rn , ...) вмiстiв регiстрiв МНР назвемо конфiгурацiєю МНР.

МНР може змiнити вмiст регiстрiв згiдно виконуваної нею команди. Скiнченний список команд утворює програму МНР. Команди програми послiдовно нумеруємо натуральними числами, починаючи з 1. Номер команди в програмі називатимемо адресою команди. МНР-програму з командами I1 , I2 ,..., Ik будемо позначати I1I2...Ik. Довжину (кiлькiсть команд) МНР-програми P позначимо |P|.

Команди МНР бувають 4-х типiв.

Тип 1. Обнулення n-го регiстру Z(n): ’Rn : 0.

Тип 2. Збiльшення вмiсту n-го регiстру на 1 S(n): ’Rn :’Rn+1.

Тип 3. Копіювання вмісту регістру T(m,n): ’Rn :’Rm

(при цьому ’Rm не змiнюється).

Тип 4. Умовний перехiд J(m,n,q): якщо ’Rn =’Rm , то перейти до виконання q-ї команди, iнакше виконувати наступну за списком команду програми.

Число q в команді J(m,n,q) назвемо адресою переходу.

Команди типiв 1-3 називають арифметичними. Пiсля виконання арифметичної команди МНР повинна виконувати наступну за списком команду програми.

Виконання однiєї команди МНР назвемо кроком МНР.

Зауважимо, що формальними моделями алгоритмів є саме МНР-програми, поняття МНР використовується для опису функціонування МНР-програм.

Виконання програми МНР починає, перебуваючи в деякiй початковiй конфiгурацiї, з виконання 1-ї за списком команди. Наступна для виконання команда програми визначається так, як описано вище. Виконання програми завершується (програма зупиняється), якщо наступна для виконання команда вiдсутня (тобто номер наступної команди перевищує номер останньої команди програми). Конфiгурацiя МНР в момент завершення виконання програми називається фiнальною, вона визначає результат роботи МНР-програми над даною початковою конфiгурацiєю.

Якщо МНР-програма P при роботi над початковою конфiгурацiєю (a0, a1, ...) нiколи не зупиняється, цей факт позначаємо P(a0, a1, ...), якщо ж коли-небудь зупиниться, цей факт позначаємо P(a0, a1,...). Якщо МНР-програма P при роботi над початковою конфiгурацiєю (a0, a1, ...) зупиняється iз фiнальною конфiгурацiєю (b0, b1, ...), цей факт позначатимемо так: P(a0, a1, ...)(b0, b1, ...).

МНР-програми як моделі алгоритмів є фінітними об’єктами, тому обмежимося розглядом скінченних конфігурацій. Конфiгурацiю вигляду (a0, a1, ..., aп , 0, 0, ...), в якiй ’Rm= 0 для всiх m>n, назвемо скiнченною. Таку конфігурацію позначаємо (a0, a1, ..., an ). Зрозуміло, що якщо МНР-програма P починає роботу над скiнченною початковою конфiгурацiєю, то в процесi виконання P МНР перебуватиме тiльки в скiнченних конфiгурацiях.

МНР-програми P та Q назвемо еквiвалентними, якщо при роботi над однаковими початковими конфiгурацiями вони або обидві зупиняються з однаковими фiнальними конфiгурацiями, або обидвi не зупиняються.

МНР-програма P обчислює часткову n-арну функцiю f:Nп→N, якщо f(a1, a2, ..., aп)=b P(a1, a2, ..., aп)(b,...).

Замiсть P(a1, a2 ,...)(b,...) надалі будемо писати P(a1 , a2 ,...)b.

Функцiю f:Nп→N називають МНР-обчислюваною, якщо iснує МНР-програма, яка обчислює цю функцiю.

Кожна МНР-програма обчислює безліч функцій, заданих на N, але, зафіксовуючи наперед арність функцій (тобто кількість компонент початкових конфігурацій), отримуємо, що кожна МНР-програма обчислює єдину функцію заданої арності.

Зауважимо, що кожну функцiю, задану на N, можна трактувати як предикат, інтерпретуючи значення 1 та 0 як істиннісні значення “Т” та “F” відповідно. В цьому випадку в ролі предикату виступає його характеристична функція.

Розглянемо приклади МНР-програм для функцій та предикатів.

Приклад 1. МНР-програма для всюди невизначеної функції:

1) J(0,0,1)

Приклад 2. МНР-програма для предикату "x=y":

1) J(0,1,3)

2) J(0,0,4)

3) S(2)

4) T(2,0)

Приклад 3. МНР-програма для функцiї f(x, y)=x+y:

1) J(1,2,5)

2) S(0)

3) S(2)

4) J(0,0,1)

Приклад 4. МНР-програма для функцiї f(x)=2x:

1) T(0,1)

2) J(1,2,6)

3) S(0)

4) S(2)

5) J(0,0,2)

Приклад 5. МНР-програма для функцiї f(x, y)=x-y:

1) J(0,1,5)

2) S(1)

3) S(2)

4) J(0,0,1)

5) Т(2,0)

Приклад 6. МНР-програма для функцiї f(x, y)=

1) J(0,1,7)

2) J(0,2,6)

3) S(1)

4) S(2)

5) J(0,0,1)

6) Z(2)

7) Т(2,0)

Приклад 7. МНР-програма для функцiї f(x, y)=max(x, y):

1) J(0,2,5)

2) J(1,2,6)

3) S(2)

4) J(0,0,1)

5) Т(1,0)

Приклад 8. МНР-програма для функцiї f(x)=x/2:

1) J(0,2,6)

2) S(2)

3) S(2)

4) S(1)

5) J(0,0,1)

6) Т(1,0)Приклад 9. МНР-програма для функцiї f(x)=[x/2]:

1) J(0,2,7)

2) S(2)

3) J(0,2,7)

4) S(2)

5) S(1)

6) J(0,0,1)

7) Т(1,0)

Приклад 10. МНР-програма для функцiї f(x)=sg(x):

1) J(0,1,4)

2) Z(0)

3) S(0)

Приклад 11. МНР-програма для функцiї f(x, y)=xy,

1) J(3,1,9)

2) J(0,2,6)

3) S(2)

4) S(4)

5) J(0,0,2)

6) Z(2)

7) S(3)

8) J(0,0,1)

9) Т(4,0)

2. МАШИНИ ТЬЮРIНГА

Пiд (детермінованою) машиною Тьюрiнга (скорочено МТ) будемо розумiти впорядковану 5-ку (Q,T,, q0 ,q*), де:

скiнченна множина внутрiшнiх станiв;

скiнченний алфавiт символiв стрiчки, причому T мiстить спецiальний символ порожньої клiтки ;

: QT→T{R,L,} однозначна функцiя переходiв;

q0Q початковий стан;

q*Q фiнальний стан.

Функцiю переходiв на практицi задають скiнченною множиною команд одного з 3-х видiв: qapbR, qapbL та qapb, де p, qQ, a, bT, QT. При цьому, як правило, не для всiх пар (q,a)QT iснує команда з лiвою частиною qa. Це означає, що функцiя не є тотальною. Проте зручніше вважати функцію тотальною, тому для всiх пар (q,a)D неявно (не додаючи вiдповiднi команди вигляду qaqa), вводимо довизначення (q,a)=(q,a,).

Неформально МТ складається з скiнченної пам’ятi, роздiленої на клiтки нескiнченної з обох бокiв стрiчки та голiвки читання-запису. В кожнiй клiтцi стрiчки мiститься єдиний символ iз T, причому в кожен даний момент стрiчка мiстить скiнченну кiлькiсть символiв, вiдмiнних вiд символа . Голiвка читання-запису в кожен даний момент оглядає єдину клiтку стрiчки.

Якщо МТ знаходиться в станi q та голiвка читає символ a, то при виконаннi команди qapbR (команди qapbL, команди qapb) МТ переходить в стан p, замiсть символу a записує на стрiчцi символ b та змiщує голiвку на 1 клiтку направо (відповідно на 1 клiтку налiво, залишає голiвку на мiсцi).

Конфiгурацiя, або повний стан МТ це слово вигляду xqy, де x,yT*, qQ. Неформально це означає, що на стр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,yT*, a, cT, qQ. Пiсля виконання команди qapbR (команди qapbL, команди qapb) МТ перейде до конфiгурацiї xcbpy (вiдповiдно до конфiгурацiї xpcby, конфiгурацiї xcpby).

Кожна МТ задає вербальне вiдображення T* →T* таким чином.

МТ М переводить слово uT в слово vT*, якщо вона з почат-кової конфiгурацiї q0u переходить до фiнальної конфiгурацiї xqy, де qF*,. При цьому перший та останн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 q1L

q1| q*

Приклад 2. МТ, яка обчислює функцiю f(x, y) =x-y:

q0| q1R

q1| q1|R

q1# q1#R

q1 q2L

q2| q3L

q3| q3|L

q3# q3#L

q3 q0R

q2# q*|

q0# q4R

q4 q*

Приклад 3. МТ, яка обчислює функцiю f(x, y)=

q0| q1R

q1| q1|R

q1# q1#R

q1 q2L

q2| q3L

q3| q3|L

q3# q3#L

q3 q0R

q2# q*|

q0# q4R

q4| q4R (єдина відмінність від МТ для f(x, y) =x-y )

q4 q*

Приклад 4. МТ, яка обчислює функцiю f(x)=sg(x):

q0 q*

q0| q1|R

q1| q1R

q1 q*

Приклад 5. МТ, яка обчислює предикат "x парне":

q0| q1R

q1| q0R

q0 q*|

q1 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 yT*, iнакше вважаємо, що результат роботи A над х невизначений.

НА A i B еквiвалентнi вiдносно алфавiту T, якщо для всiх xT* A(x) та B(x) одночасно визначенi або невизначенi, та у випадку визначеностi A(x)=B(x).

Відомо [7], що для кожного НА над алфавітом Т існує еквiвалентний йому вiдносно T НА в алфавіті Т {s} з єдиним допоміжним символом Т. Відомо також [7], що вербальне відображення, яке кожне слово xT* переводить в слово хх, не може бути заданим жодним НА в алфавіті Т. В той же час маємо

Приклад 1. НА, який кожне xT* переводить в слово xх (тут #Т):

##aa#а## для всіх aТ

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

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

##

##

НА A обчислює часткову функцiю f:Nk→N, якщо він кожне слово вигляду переводить в слово у випадку (x1,...,xk)Df , та A( ) невизначене при (x1 ,...,xk)Df .

Функцiя називається обчислюваною за Марковим, або НА-обчислюваною, якщо iснує НА, який її обчислює.

Зауважимо, що кожний НА обчислює безліч функцій натуральних аргументів та значень, але зафіксовуючи наперед арність функцій, дістаємо, що кожний НА обчислює єдину функцію заданої арності.

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

Канонiчною системою Поста над алфавiтом T називають формальну систему (T*, A, P), в якої множина аксiом A є скiнчен-ною підмножиною множини T*, а множина правил виведення P складається з слiв вигляду 0S11...m-1Smm Тут T, всі k та і фiксованi слова iз T* , всі символи SkT, причому всi ji{1,...,m}.

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

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

Множина правил P визначає на словах iз T* вiдношення безпосереднього виведення таким чином: Р , якщо iснує правило 0S11...m-1SmmP таке, що для деяких слiв 1, mT* маємо 011...mm

Рефлексивно-транзитивне замикання в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={SaSa, SbSb} породжує всi слова-палiндроми в алфавiтi {a,b}, тобто слова, якi читаються однаково злiва направо i справа налiво.

Множина XT* породжувана за Постом, якщо iснують алфавiт TT та система Поста 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 :

ТЕЗА ЧОРЧА

Розглянемо співвідношення між різними формальними моделями поняття алгоритмічно обчислюваної функції. Обмежимося розглядом п-арних функцiй на множині N.

Теорема 8.1. Наступнi класи функцiй спiвпадають:

1) клас ЧРФ;

2) клас програмованих на N п-арних функцiй;

3) клас МНР-обчислюваних функцiй;

4) клас функцiй, обчислюваних за Тьюрiнгом;

5) клас функцiй, обчислюваних за Марковим;

6) клас функцiй, обчислюваних за ПостомОтже, розглянутi нами формалiзми задають один i той же клас п-арних функцiй на N. При цьому самi визначення формалiзмiв гарантують ефективну обчислюванiсть описуваних ними функцiй. Тому є всi пiдстави вважати, що такi формалiзми є рiзними математичними уточненнями iнтуїтивного поняття алгоритмiчно обчислюваної функцiї (АОФ). Вперше таке твердження стосовно рекурсивних функцiй було висунуте в 1936 роцi А. Чорчом, тому дiстало назву ”теза Чорча”. Узагальнення тези Чорча на випадок часткових функцiй в цьому ж роцi запропонував С. Клiнi. В такому розширеному виглядi теза Чорча формулюється наступним чином:

Tеза Чорча. Клас ЧРФ співпадає з класом п-арних АОФ, заданих на множині натуральних чисел.

Поняття АОФ не є строго визначеним математичним поняттям, тому теза Чорча математичному доведенню не пiдлягає. Теза Чорча є природно-науковим фактом, який засвідчує адекватність формальних моделей інтуїтивного поняття АОФ.

Із тези Чорча як наслiдок випливає:

клас РФ спiвпадає з класом тотальних АОФ, заданих на множинi натуральних чисел.

Значення тези Чорча (скорочено ТЧ) полягає в наступному.

1) Прийняття тези Чорча перетворює iнтуїтивнi поняття алгоритму, обчислюваностi, розв’язностi в об’єкти математичного вивчення.

2) Використання тези Чорча як своєрiдної аксiоми дозволяє в багатьох випадках замiнити формальнi завдання алгоритмiв на неформальнi їх описи. Це дає iстотне спрощення доведень, звiльняючи його вiд зайвих деталей. Проте доведення на основi тези Чорча має бути ретельно аргументованим! При виникненнi сумнiвiв треба вміти провести чисто формальне доведення.

Розглянемо приклад використання тези Чорча. Нехай функція f є ЧРФ. Доведемо, що функція h(x)= теж є ЧРФ. Для цього розглянемо процес глобального обчислення всіх значень функції f. Такий процес розіб'ємо на етапи. На кожному етапі починаємо обчислення для наступного значення аргументу. На етапі 0 робимо 1-й крок обчислення f(0). На етапі 1 робимо 1-й крок обчислення f(1) та 2-й крок обчислення f(0) і т.д. На етапі п робимо 1-й крок обчислення f(п), 2-й крок обчислення f(п-1), … , (п+1)-й крок обчислення f(0). Якщо на якомусь етапі обчислення певного f(т) завершується, порівнюємо f(т) та х. При умові f(т)=х процес глобальних обчислень завершується, адже тоді хEf , тому результатом нашої роботи буде число 1. При умові f(т)х продовжуємо процес глобальних обчислень. Таким чином, описано алгоритм для обчислення функції h(x), звідки за тезою Чорча функція h(x) є ЧРФ.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать