МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра АСУ Звіт з лабораторної роботи №3 з дисципліни “ Теорія алгоритмів і математичні основи представлення знань ” на тему: Емуляція на ПЕОМ машин Тюрінга Львів-2007 Мета лабораторної роботи - емуляцiя на ПЕОМ машин Тюрінга і констроювання програм для них. I. ЗАГАЛЬНІ ПОЛОЖЕННЯ Для засвоєння поняття машин Тюрінга і освоєння конструювання Т-машин (єх програм) необхідно в певній мірі автоматизувати тестування та відладку програм Т-машин (Т-програм). Для цього необхідно в данній лабораторній роботі емулювати на ПЕОМ машину Тюрінга, якаб по заданій Т-програмі Пт і входу w імітувала обчислення функціє F, що задається Пт. В основі алгоритмічноє системи Тюрінга лежить поняття абстрактнго автомата - машини Тюрінга (Т-машини). В літературі наведено багато варіантів визначення Т-машини. Ми розглядатемемо найбільш поширений варіант цієє машини. I. Нехай задано вхідний алфавіт Eвх   =  {a1,..,an},внутрішній алфавіт Eвн   =  {b1,..,br},і E є об"єднання алфавітів Eвх і Eвн, причому перетин Eвн і Eвх є пустою множиною. E будемо називати повним алфавітом. Елементи алфавітів називаються буквами або літерами. Через E* позначимо множину всіх слів в алфавіті E, включаючи пусте слово e, а, відповідно, через E*вх - множину всіх вхідних слів. Довільну скінченну підмножину Q   =  {q0,q1,..,qm} деякої нескінченноє множини Q^   =  {..,q(-1),q0,..qm,..} будемо називати множиною міток, а єє елементи - мітками. Будемо вважати, що перетин Q і E є пустою множиною. Командю Тюрінга (Т-командою ) називається вираз вигляду q d -> q'd'r (1) де q і q' - мітки із Q, d і d' - літери із E, а r приймає значення одного із трьох чисел : -1,0,+1. Пара qd із (1) називається Т-міткю. Програмою Тюрінга (Т-прграмою) називається двільна скінченна сукупність Пт Т-команд U0 U1 (2) .. Um в якій різні команди мають різні Т-мітки остання умова означає, що кожна Т-команда Ui   =  ( qi di -> qi'di'ri ) (3) в Пт однзначно визначається по своєй Т-мітці. Машиною Тюрінга називається довільний набір Мт   =  (Q,E,q^,#,Пт), --------------- --------------- де: Q - множина міток; E -об'єднання вхідного Eвх та внутрішнього Eвн алфавітів; q^ - виділений елемент із Q, який називається початковою міткою Мт; # - виділений елемент із Eвн; Пт - Т-програма. Коли кманда q d -> q'd'r входить в програму Пт Т-машини Мт, тді мітка q і Т-мітка (q d) називаються прміжковими мітками йієє машини. Всі непромщжкві мітки і Т-мітки називаються кінцевими мітками Т-машини Мт. Станом Т-машини (Т-станом) називається довільна нескінченна в обидва боки послідовність t   =  ...d(-2) d(-1) q d(0) d(1) d(2)... (4) де d(j) (j   =  ...-2,-1,0,1,2,...) - літери із E, а q - мітка із Q. Для машини Мт Т-стан (4) називається : а) початковим, коли q   =  q^ б) проміжковим, коли < q d(0) > - проміжкова Т-мітка; в) кінцевим, коли < q d(0) > - кінцева Т-мітка Мт. Множину всіх станів Т-машини Мт позначимо через Dм. Тепер визначимо функцію переходів Fт : Dм --> Dм. Коли Т-мітка <q d(0)> - кінцева в стані (4), то Fт(t)   =  t. Нехай <q d(0)> - проміжова Т-мітка стану (4). Тоді в програмі Пт знайдеться одна і тільки одна команда вигляду q d(0) -> --> q'd'r. Під дією цієї команди Т-стан t переходить в стан t'   =  Fт(t). Залежно від r   =  +1,0,-1 значення tr   =  Fт(t) приймє вигляд : t+   =  ...d(-2) d(-1) d' q' d(1) d(2)... t0   =  ...d(-2) d(-1) q' d' d(1) d(2)... (5) t-   =  ...d(-2) q' d(-1) d' d(1) d(2)... Із (5) випливає,що при r   =  +1,0,-1 вираз "q d(0)" в стані(4), відповідно,замінюється на вирази " d' q' ", "q' d' " i " q' d(-1) d'" Тепер опишемо, яким чином кожній Т-машині Мт можна співставити функцію f[Мт] : E*вх --> E*. Далі через /d/   =  ...ddddd... будемо позначати Нескінченну послідовність літери d із E. Нехай w - довільне слово із E*вх. Опишемо функціонування Мт на v.Введемо початовий стан t[0] Т-машини Мт ,де t[0]   =  /#/q^ w /#/. Траєкторією Т-машини Мт (на вході w) називається нескінченна послідовність T^   =  t[0],t[1],t[2]..., де t[0] - початковий стан, і для кожного натурального i >  =  0, t[i+1]   =  Fт( t[i+1] ) . Можливі два випадки : 1) знайдеться таке s, що t[s]   =  /#/q' v /#/. -кінцевий стан, а для всіх j (0 <  =  j <  =  s-1) t[j] - проміжковий стан Мт в послідовності T^; 2)всі стани в послідовності T^ - проміжкові. В перщому випадку будемо вважати,що f[Мт](w)   =  v, а в другому коли Мт циклює, вважатимемо, що f[Мт](w)   =  @, тобто її значення не визначено. Аналогічно можна вважати, що Мт обчислює предикат P[Мт] : E*вх --> {T,F}, якщо E*вн містить множину {T,F}, і : а) P[Мт](w)   =  T,якщо в кінцевому стані t[s]   =  /#/q' v /#/ слово v   =  T; б) P[Мт](w)   =  F, якщо в кінцевому стані t[s]   =  /#/q' v /#/ слово v   =  F; d) P[Мт](w)   =  @, якщо Мт циклює на w. Функціонування Т-машини , її Т-стани і обчислення функції переходів Fт можна описувати на її "фізичній" моделі ,тобто можна трактувати на мові "стрічок", "блоку управління","головки" і т.п. При цій трактовці Т-машина Мт складається із потенційно нескінченноє ( в обидва боки ) стрічки, блоку управління (У-блоку) і головки, що може пересуватися вздовж стрічки. Стрічка розділена на комірки, в яких у кожний момент часу записно певний символ із E. Головка здійснює читання і запис літер на стрічці. В кожний момент головка може сприймати одну і тільки одну комірку стрічки. В процесі роботи Т-машини Мт може стояти на місці, або пересуватися вправо і ліво по стрічці. Крім того, в головці в кожний момент записана деяка мітка із Q. У-блок містить Т-програму Пт, і керує роботою Т-машина Мт. ───────────────────────────────────── ...|d(-2)| d(-1)| d(0)| d(1)| d(2)|... ──────────────────────────────────────- ┌─  ─┐ │    q    │ ├─────   ──────────────────────┐ │ У-БЛОК │ │ Т-програма Мт │ └──────────────────────┘ В на кожному кроці функціонування Т-машини Мт голвка передає У-блоку символ d(0), що вона спостерігає на вхідній стрічці, а також мітку q , що зберігається в головці. В прграмі Пт У-блок знаходить команду з Т-міткою <q d(0)> (нехай вона має вигляд q d(0) -> q'd'r), потім записує на стрічку замість d(0) символ d', в голвку - стан q', і в залежності від значення r   =  +1,-1,0 зсуває,відповідно,головку вправо, вліво ,або залишає на місці. Т-машина фукцінує до тих пір, поки в головку не У-блок не зустріне кінцеву Т-мітку Мт.Інакше вона зациклюється. Часткові або всюдиозначенні функцію g : E*вх -->E*вх, яка задана на множині слів довільного алфавіту E , або предикат P : E* --> {T,F}, будемо називати Т-функцією (Т-предикатом), якщо існує Т-машщина Мg(Мp), що обчислює g (P). Як відомо [1], клас всіх Т-функцій містиця в класі всіх функцій,що обчислюються нормальними алгоритмами, а сам він містить у собі клас всіх функцій, що обчислюються операторними алгоритмами. Приклад Т-машини і опис її фукціонування наведено в розділі VI данної інструкції. II. ПОРЯДОК РОБОТИ 1. Вивчити визначення алфавітів машин Тюрінга, Т-команд і Т-програм, а також механізм обчислення Т-машиною Тf функції f : E* -->E*. 2. Розробити алгоритм емуляції нормальних алгоритмів на ПЕОМ. Засобами мови Паскаль або Си реалiзувати процедуру , що емулює на ПЕОМ функціонування Т-машини, створивши відповідні типи даних, що забезпечать ввід інформації, а також візщуалізації результатів роботи Мт.Відладити емулятор Т-машин. 3. По виданому завданню ( конкретній функціє f ) скласти Т-програму Пf, що реалізує функцію f. 4. За допомогою емулятора Т-машин відлагодити М-програму Пf. 5. Здати викладачевi розроблені процедури, продемонструвавши їх працездатнiсть на конкретних вхідних даних. 6. Проаналізувати результати роботи емулятора та Пf. 7. Оформити звіт по лабоораторній роботі. 3) v(w,s1,s2)  =  s3s2s4, якщо w   =  s3s1s4; 4) перехід від n до n+1 в десятковій системі числення; 5) перетворення унарного запису числа в десятковий. 6) додавання десяткових чисел 7) віднімання десяткових чисел VI. КОНТРОЛЬНИЙ ПРИКЛАД Необхідно побудувати машину Тюрінга М1, яка реалізує функцію f1(x)   =  x + 1, вважаючи ,що числа x і значення f1(x) задаються в десятковій системі счислення, тобто числа x і f1(x) задаються словом у алфавіті E1вх   =  {0,1,..,8,9},причому вважається,що число нуль може задаватися літерою 0 із E1вх, або пустим словом е   =  '' із E*вх. При конструюванні Т-машини будемо номерувати єє команди, щоб потім можна було по кроках описати її роботу. Т-машина,що реалізує f1 має вигляд М1   =  (Q1,E1,q^,#,П1),де Q1 = {q^,q1,Я}, E1вн   =  {#}, а Т-програма П1 наведена нижче : 1) q^ 0 --> q^ 0 +1 12) q1^ 0 --> Я 1 +1 2) q^ 1 --> q^ 1 +1 13) q1^ 1 --> Я 2 +1 3) q^ 2 --> q^ 2 +1 14) q1^ 2 --> Я 3 +1 4) q^ 3 --> q^ 3 +1 15) q1^ 3 --> Я 4 +1 5) q^ 4 --> q^ 4 +1 16) q1^ 4 --> Я 5 +1 6) q^ 5 --> q^ 5 +1 17) q1^ 5 --> Я 6 +1 7) q^ 6 --> q^ 6 +1 18) q1^ 6 --> Я 7 +1 8) q^ 7 --> q^ 7 +1 19) q1^ 7 --> Я 8 +1 9) q^ 8 --> q^ 8 +1 20) q1^ 8 --> Я 9 +1 10) q^ 9 --> q^ 9 +1 21) q1^ 9 --> q1^ 0 -1 11) q^ # --> q1^ # -1 22) q1^ # --> Я 1 0 Наведемо траєктрію T1^ роботи М1 при x   =  '349'. Тоді : Стани траєктрії T1^ Номера команд П1 t[0]  2= 0 /#/q^ 349/#/ 4 t[1]  2= 0 /#/3 q^ 49/#/ 5 t[2]  2= 0 /#/34 q^ 9/#/ 10 t[3]  2= 0 /#/349 q^ #/#/ 11 t[4]  2= 0 /#/34 q1^ 9#/#/ 21 t[5]  2= 0 /#/3 q1^ 40#/#/ 16 t[6]  2= 0 /#/3 Я 50#/#/ кінцева Значить, f1[М1]('349')   =  '350' Самостійно побудуйте траєкторії машини Тюрінга М1 при x   =  '9999', '0' i e   =  ''. Завдання: R R R F6(W) =W W W W W Текст прорами: ; @-a ; &-b ; %-c (q0,a) (q0,a,+1) (q0,b) (q0,b,+1) (q0,c) (q0,c,+1) (q0,#) (q1,!,-1) (q1,a) (q2,@,+1) (q1,b) (q3,&,+1) (q1,c) (q4,%,+1) (q2,a) (q2,a,+1) (q2,b) (q2,b,+1) (q2,c) (q2,c,+1) (q2,&) (q2,&,+1) (q2,@) (q2,@,+1) (q2,%) (q2,%,+1) (q2,!) (q2,!,+1) (q2,#) (q5,@,-1) (q3,a) (q3,a,+1) (q3,b) (q3,b,+1) (q3,c) (q3,c,+1) (q3,&) (q3,&,+1) (q3,@) (q3,@,+1) (q3,%) (q3,%,+1) (q3,!) (q3,!,+1) (q3,#) (q5,&,-1) (q4,a) (q4,a,+1) (q4,b) (q4,b,+1) (q4,c) (q4,c,+1) (q4,&) (q4,&,+1) (q4,@) (q4,@,+1) (q4,%) (q4,%,+1) (q4,!) (q4,!,+1) (q4,#) (q5,%,-1) (q5,a) (q1,a,0) (q5,b) (q1,b,0) (q5,c) (q1,c,0) (q5,&) (q5,&,-1) (q5,@) (q5,@,-1) (q5,%) (q5,%,-1) (q5,!) (q5,!,-1) (q5,#) (q6,#,+1) (q6,@) (q6,@,+1) (q6,&) (q6,&,+1) (q6,%) (q6,%,+1) (q6,!) (q70,!,+1) ;(q6,#) (q7,!,0) (q70,#) (q71,?,-1) (q70,@) (q70,a,+1) (q70,&) (q70,b,+1) (q70,%) (q70,c,+1) (q71,!) (q7,!,+1) (q71,a) (q71,a,-1) (q71,b) (q71,b,-1) (q71,c) (q71,c,-1) ;++++++++++++++++++++++++++++++ ;(q7,!) (q7,!,+1) (q7,a) (q8,@,+1) (q7,b) (q9,&,+1) (q7,c) (q10,%,+1) (q7,?) (q13,?,0) (q8,a) (q8,a,+1) (q8,b) (q8,b,+1) (q8,c) (q8,c,+1) (q8,&) (q8,&,+1) (q8,@) (q8,@,+1) (q8,%) (q8,%,+1) (q8,!) (q8,!,+1) (q8,?) (q8,?,+1) (q8,#) (q12,a,-1) (q9,a) (q9,a,+1) (q9,b) (q9,b,+1) (q9,c) (q9,c,+1) (q9,&) (q9,&,+1) (q9,@) (q9,@,+1) (q9,%) (q9,%,+1) (q9,!) (q9,!,+1) (q9,?) (q9,?,+1) (q9,#) (q12,b,-1) (q10,a) (q10,a,+1) (q10,b) (q10,b,+1) (q10,c) (q10,c,+1) (q10,&) (q10,&,+1) (q10,@) (q10,@,+1) (q10,%) (q10,%,+1) (q10,!) (q10,!,+1) (q10,?) (q10,?,+1) (q10,#) (q12,c,-1) (q12,!) (q12,!,-1) (q12,?) (q12,?,-1) (q12,a) (q12,a,-1) (q12,b) (q12,b,-1) (q12,c) (q12,c,-1) (q12,@) (q7,@,+1) (q12,&) (q7,&,+1) (q12,%) (q7,%,+1) (q12,#) (q13,#,+1) (q13,a) (q13,a,+1) (q13,b) (q13,b,+1) (q13,c) (q13,c,+1) (q13,@) (q13,a,+1) (q13,&) (q13,b,+1) (q13,%) (q13,c,+1) (q13,?) (q13,?,+1) (q13,!) (q13,!,+1) (q13,#) (q14,^,-1) ;================================ (q14,?) (q15,?,+1) (q14,a) (q14,a,-1) (q14,b) (q14,b,-1) (q14,c) (q14,c,-1) (q15,a) (q16,@,+1) (q15,b) (q17,&,+1) (q15,c) (q18,%,+1) (q15,^) (q20,^,+1) (q16,a) (q16,a,+1) (q16,b) (q16,b,+1) (q16,c) (q16,c,+1) (q16,&) (q16,&,+1) (q16,@) (q16,@,+1) (q16,^) (q16,^,+1) (q16,%) (q16,%,+1) (q16,!) (q16,!,+1) (q16,?) (q16,?,+1) (q16,#) (q19,a,-1) (q17,a) (q17,a,+1) (q17,b) (q17,b,+1) (q17,c) (q17,c,+1) (q17,&) (q17,&,+1) (q17,@) (q17,@,+1) (q17,%) (q17,%,+1) (q17,!) (q17,!,+1) (q17,^) (q17,^,+1) (q17,?) (q17,?,+1) (q17,#) (q19,b,-1) (q18,a) (q18,a,+1) (q18,b) (q18,b,+1) (q18,c) (q18,c,+1) (q18,&) (q18,&,+1) (q18,@) (q18,@,+1) (q18,%) (q18,%,+1) (q18,!) (q18,!,+1) (q18,?) (q18,?,+1) (q18,^) (q18,^,+1) (q18,#) (q19,c,-1) (q19,!) (q19,!,-1) (q19,^) (q19,^,-1) (q19,?) (q19,?,-1) (q19,a) (q19,a,-1) (q19,b) (q19,b,-1) (q19,c) (q19,c,-1) (q19,@) (q15,@,+1) (q19,&) (q15,&,+1) (q19,%) (q15,%,+1) (q19,#) (q20,#,+1) (q20,a)(q20,a,+1) (q20,b)(q20,b,+1) (q20,c)(q20,c,+1) (q20,#)(q21,!,-1) (q21,a)(q22,@,+1) (q21,b)(q23,&,+1) (q21,c)(q24,%,+1) (q21,!) (q21,!,-1) (q21,^) (q21,^,-1) (q21,?) (q21,?,-1) (q21,@) (q21,@,+1) (q21,&) (q21,&,+1) (q21,%) (q21,%,+1) (q21,#)(R,#,0) (q22,a) (q22,a,+1) (q22,b) (q22,b,+1) (q22,c) (q22,c,+1) (q22,&) (q22,&,+1) (q22,@) (q22,@,+1) (q22,%) (q22,%,+1) (q22,!) (q22,!,+1) (q22,#) (q25,@,-1) (q23,a) (q23,a,+1) (q23,b) (q23,b,+1) (q23,c) (q23,c,+1) (q23,&) (q23,&,+1) (q23,@) (q23,@,+1) (q23,%) (q23,%,+1) (q23,!) (q23,!,+1) (q23,#) (q25,&,-1) (q24,a) (q24,a,+1) (q24,b) (q24,b,+1) (q24,c) (q24,c,+1) (q24,&) (q24,&,+1) (q24,@) (q24,@,+1) (q24,%) (q24,%,+1) (q24,!) (q24,!,+1) (q24,#) (q25,%,-1) (q25,a)(q21,a,0) (q25,b)(q21,b,0) (q25,c)(q21,c,0) (q25,#)(q26,#,+1) (q25,&) (q25,&,-1) (q25,@) (q25,@,-1) (q25,%) (q25,%,-1) (q25,!) (q25,!,-1) (q25,^) (q25,^,-1) (q25,?) (q25,?,-1) ;++++++++++++++++++++++++++ (q26,@) (q26,a,+1) (q26,&) (q26,b,+1) (q26,%) (q26,c,+1) (q26,?) (q26,.,+1) (q26,^) (q26,.,+1) (q26,!) (q26,.,+1) (q26,#) (R,#,0) Результати роботи програми: Введіть стрічку даних: aaabcc Результуюча стрічка: aaabcc.ccbaaa.ccbaaa.ccbaaa.aaabcc Введіть стрічку даних: ababab Результуюча стрічка: ababab.bababa.bababa.bababa.ababab Введіть стрічку даних: a Результуюча стрічка: a.a.a.a.a Введіть стрічку даних: cccca Результуюча стрічка: cccca.acccc.acccc.acccc.cccca Завдання: L1= { (a^n)(b^2n)(c^3n)(a^n) | n>=1} Текст прорами: (q0,b) (R,F,0) (q0,c) (R,F,0) (q0,a) (q1,$,+1) (q0,#) (R,F,0) (q1,b) (q22,@,+1) (q1,c) (R,F,0) (q1,a) (q1,a,+1) (q1,#) (R,F,0) (q1,@) (q1,@,+1) (q22,b) (q2,@,+1) (q22,c) (R,F,0) (q22,a) (q22,a,+1) (q22,#) (R,F,0) (q22,@) (q22,@,+1) (q2,b) (q2,b,+1) (q2,c) (q3,@,+1) (q2,a) (R,F,0) (q2,#) (R,F,0) (q2,@) (q2,@,+1) (q3,b) (R,F,0) (q3,c) (q4,@,+1) (q3,a) (R,F,0) (q3,#) (R,F,0) (q4,b) (R,F,0) (q4,c) (q5,@,+1) (q4,a) (R,F,0) (q4,#) (R,F,0) (q5,b) (R,F,0) (q5,c) (q5,c,+1) (q5,a) (q6,@,-1) (q5,#) (R,F,0) (q5,@) (q5,@,+1) (q6,@) (q6,@,-1) (q6,b) (q6,b,-1) (q6,c) (q6,c,-1) (q6,a) (q6,a,-1) (q6,$) (q7,$,+1) (q7,a) (q1,$,+1) (q7,@) (q8,@,+1) (q8,@) (q8,@,+1) (q8,b) (R,F,0) (q8,c) (R,F,0) (q8,a) (R,F,0) (q8,#) (R,T,0) Результати роботи програми: Введўть стрўчку даних: abbccca Результуюча стрўчка: $@@@@@@T Введўть стрўчку даних: aac Результуюча стрўчка: $aF Введўть стрўчку даних: aaccc Результуюча стрўчка: $aFcc Введўть стрўчку даних: aaaaa Результуюча стрўчка: $aaaaF Висновок: під час виконання лабораторної роботи я вивчив емуляцiю на ПЕОМ машин Тюрінга і констроювання програм для них.