Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Емуляція на ПЕОМ машин Тюрінга
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2005
Тип роботи:
Лабораторна робота
Предмет:
Теорiя алгоритмiв i математичнi основи представленння знань
Група:
КН
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний Університет “Львівська політехніка”
Інститут комп´ютерних наук та інформаційних технологій
Лабораторна робота №3
з курсу:“Теорія алгоритмів і математичні основи
представлення знань”
на тему :” Емуляція на ПЕОМ машин Тюрінга.”
Мета лабораторної роботи - емуляцiя на ПЕОМ машин Тьюрінга і конструювання програм для них.
I. ЗАГАЛЬНІ ПОЛОЖЕННЯ
Для засвоєння поняття машин Тьюрінга і освоєння конструювання Т-машин необхідно в певній мірі автоматизувати тестування та відладку програм Т-машин (Т-програм).
Для цього необхідно в данній лабораторній роботі емулювати на ПЕОМ машину Тьюрінга, яка б по заданій Т-програмі Пт і входу w імітувала обчислення функції F, що задається Пт.
В основі алгоритмічної системи Тюрінга лежить поняття абстрактнго автомата - машини Тюрінга (Т-машини). В літературі наведено багато варіантів визначення Т-машини. Ми розглядатемемо найбільш поширений варіант цієї машини.
Нехай задано вхідний алфавіт Eвх 2= 0 {a1,..,an}, внутрішній алфавіт Eвн 2= 0 {b1,..,br}, і E об’єднання алфавітів Eвх і Eвн, причому перетин Eвн і Eвх є пустою множиною. E будемо називати повним алфавітом. Елементи алфавітів називаються буквами або літерами.
Через E* позначимо множину всіх слів в алфавіті E, включаючи пусте слово e, а, відповідно, через E*вх - множину всіх вхідних слів.
Довільну скінченну підмножину Q 2= 0 {q0,q1,..,qm} деякої нескінченної множини Q^ 2= 0 {..,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
в якій різні команди мають різні Т-мітки. Машиною Тюрінга називається довільний набір Мт 2= 0 (Q,E,q^,#,Пт), де:
Q - множина міток;
E -об'єднання вхідного Eвх та внутрішнього Eвн алфавітів;
q^ - виділений елемент із Q, який називається початковою міткою Мт;
# - виділений елемент із Eвн;
Пт - Т-програма.
Коли команда q d -> q'd'r входить в програму Пт Т-машини Мт, тоді мітка q і Т-мітка (q d) називаються прміжковими мітками. Всі непроміжкові мітки і Т-мітки називаються кінцевими мітками Т-машини Мт.
Станом Т-машини (Т-станом) називається довільна нескінченна в обидва боки послідовність
t 2= 0 ...d(-2) d(-1) q d(0) d(1) d(2)... (4)
де d(j) (j 2= 0...-2,-1,0,1,2,...) - літери із E, а q - мітка із Q.
Для машини Мт Т-стан (4) називається :
а) початковим, коли q 2= 0 q^ ;
б) проміжковим, коли < q d(0) > - проміжкова Т-мітка;
в) кінцевим, коли < q d(0) > - кінцева Т-мітка Мт.
Множину всіх станів Т-машини Мт позначимо через Dм.
Тепер визначимо функцію переходів Fт : Dм --> Dм.Коли Т-мітка <q d(0)> - кінцева в стані (4), то Fт(t) 2= 0 t.Нехай <q d(0)> - проміжова Т-мітка стану (4). Тоді в програмі Пт знайдеться одна і тільки одна команда вигляду q d(0) -> q'd'r. Під дією ціїє команди Т-стан t переходить в стан t' 2= 0 Fт(t). Залежно від r 2= 0 +1,0,-1 значення tr 2= 0 Fт(t) приймає вигляд :
t+ 2= 0 ...d(-2) d(-1) d' q' d(1) d(2)...
t0 2= 0 ...d(-2) d(-1) q' d' d(1) d(2)... (5)
t- 2= 0 ...d(-2) q' d(-1) d' d(1) d(2)...
Із (5) випливає, що при r 2= 0 +1,0,-1 вираз "q d(0)" в стані (4),відповідно, замінюється на вирази " d' q' ", "q' d' " i " q' d(-1) d' " .
Тепер опишемо, яким чином кожній Т-машині Мт можна співставити функцію f[Мт] : E*вх --> E*.Далі через /d/ 2= 0 ...ddddd... будемо позначати нескінченну послідовність літери d із E. Нехай w - довільне слово із E*вх. Опишемо функціонування Мт на v.Введемо початовий стан t[0] Т-машини Мт ,де
t[0] 2= 0 /#/q^ w /#/.
Траєкторією Т-машини Мт (на вході w) називається нескінченна послідовність T^ 2= 0 t[0],t[1],t[2]..., де t[0] - початковий стан, і для кожного натурального i > 2= 0 0, t[i+1] 2= 0 Fт( t[i+1] ) .
Можливі два випадки :
1) знайдеться таке s, що t[s] 2= 0 /#/q' v /#/. – кінцевий стан, а для всіх j (0 < 2= 0 j < 2= 0 s-1) t[j] - проміжковий стан Мт в послідовності T^;
2)всі стани в послідовності T^ - проміжкові.
В перщому випадку будемо вважати, що f[Мт](w) 2= 0 v, а в другму, коли Мт циклює, вважатимемо, що f[Мт](w) 2= 0 @, тобто її значення не визначено.
Аналогічно можна вважати, що Мт обчислює предикат P[Мт] : E*вх --> {T,F},
якщо E*вн містить множину {T,F}, і : а) P[Мт](w) 2= 0 T, якщо в кінцевому стані t[s] 2= 0 /#/q' v /#/ слово v 2= 0 T; б) P[Мт](w) 2= 0 F, якщо в кінцевому стані t[s] 2= 0 /#/q' v /#/ слово v 2= 0 F;
d) P[Мт](w) 2= 0 @, якщо Мт циклює на w.
Функціонування Т-машини , її Т-стани і обчислення функції переходів Fт можна описувати на її "фізичній" моделі ,тобто можна трактувати на мові "стрічок", "блоку управління","головки" і т.п.При цій трактовці Т-машина Мт складаїться із потенційно нескінченної ( в обидва боки ) стрічки, блоку управління (У-блоку) і головки, що може пересуватися вздовж стрічки. Стрічка розділена на комірки, в яких у кожний момент часу записно певний
символ із E.
Головка здійснюї читання і запис літер на стрічці. В кожниймомент головка може сприймати одну і тільки одну комірку стрічки.В процесі роботи Т-машини Мт може стояти на місці, або пересуватися вправо і ліво по стрічці. Крім того, в головці в кожний момент записана деяка мітка із Q.
У-блок містить Т-програму Пт, і керуї роботою Т-машина Мт.В на кожному кроці функціонування Т-машини Мт головка передає У-блоку символ d(0), що вона спостерігає на вхідній стрічці, а також мітку q , що зберігається в головці. В програмі Пт У-блок знаходить команду з Т-міткою <q d(0)> (нехай вона має вигляд q d(0)-> q'd'r), потім записує на стрічку замість d(0) символ d', в голвку - стан q', і в залежності від значення r 2= 0 +1,-1,0 зсуває,відповідно, головку вправо, вліво ,або залишає на місці. Т-машина фукцінує до тих пір, поки в головку не У-блок не зустріне кінцеву Т-мітку Мт.Інакше вона зациклюється. Часткові або всюдиозначені функцію g : E*вх -->E*вх, яка задана на множині слів довільного алфавіту E , або предикат P :
E* --> {T,F}, будемо називати Т-функціїю (Т-предикатом), якщо існує Т-машина Мg(Мp), що обчислює g (P).
Як відомо, клас всіх Т-функцій міститься в класі всіх функцій,що обчислюються нормальними алгоритмами, а сам він містить у собі клас всіх функцій, що обчислюються операторними алгоритмами.
II. ПОРЯДОК РОБОТИ
1. Вивчити визначення алфавітів машин Тюрінга, Т-команд і Т-програм, а також механізм обчислення Т-машиною Тf функці• f : E* --> E*.
2. По виданому завданню ( конкретній функці• f ) скласти Т-програму Пf, що реалізуї функцію f.
3. За допомогою емулятора Т-машин відлагодити М-програму Пf.
4. Здати викладачевi розроблені процедури, продемонструвавши їх працездатнiсть на конкретних вхідних даних.
5. Проаналізувати результати роботи емулятора та Пf.
6. Оформити звіт по лабоораторній роботі.
Довести прямою побудовою рекурсивність на E* функції Fi(W) та предикату P[Lj] (w) ( P[Lj] (w) = T ( w належить Lj) (i,j=1..60). Нехай S=X1X2..Xn і T= Y1Y2..Ym -слова в алфавіті E={a,b,c}. Позначення :
1) ST - слово X1X2..XnY1Y2..Ym (конкатенація слів S і T);
R
2) S -слово Xn..X3X2X1;
3) (X^n) - послідовність n літер X із алфавіту E.
R R
F16(W) =W W W W W
// w^r w w w^r w
(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)
(q1,%) (q1,%,-1)
(q1,$) (q1,$,-1)
(q1,*) (q1,*,-1)
(q1,#) (q6,#,0)
(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,#) (q5,a,0)
(q5,a) (q5,a,-1)
(q5,b) (q5,b,-1)
(q5,c) (q5,c,-1)
(q5,%) (q1,%,0)
(q5,$) (q1,$,0)
(q5,*) (q1,*,0)
(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,#) (q5,b,0)
(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,#) (q5,c,0)
//------------------- str=w(a=$,b=%,c=*)+w^r
(q6,#) (q7,#,+1)
(q7,$) (q7,$,+1)
(q7,%) (q7,%,+1)
(q7,*) (q7,*,+1)
(q7,+) (q7,+,+1)
(q7,-) (q7,-,+1)
(q7,=) (q7,=,+1)
(q7,a) (q8,+,0)
(q7,b) (q9,-,0)
(q7,c) (q10,=,0)
(q7,#) (q12,#,-1)
(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,=) (q8,=,+1)
(q8,#) (q11,$,0)
(q11,$) (q11,$,-1)
(q11,%) (q11,%,-1)
(q11,*) (q11,*,-1)
(q11,a) (q11,a,-1)
(q11,b) (q11,b,-1)
(q11,c) (q11,c,-1)
(q11,+) (q7,+,0)
(q11,-) (q7,-,0)
(q11,=) (q7,=,0)
(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,=) (q9,=,+1)
(q9,#) (q11,%,0)
(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,=) (q10,=,+1)
(q10,#) (q11,*,-1)
//------------------- str=w(a=$,b=%,c=*)+w^r(a=+,b=-,c==)+w^r(a=$,b=%,c=*)
(q12,a) (q12,a,-1)
(q12,b) (q12,b,-1)
(q12,c) (q12,c,-1)
(q12,$) (q12,$,-1)
(q12,%) (q12,%,-1)
(q12,*) (q12,*,-1)
(q12,+) (q12,+,-1)
(q12,-) (q12,-,-1)
(q12,=) (q12,=,-1)
(q12,#) (q13,#,+1)
(q13,a) (q13,a,+1)
(q13,b) (q13,b,+1)
(q13,c) (q13,c,+1)
(q13,$) (q14,a,+1)
(q13,%) (q15,b,+1)
(q13,*) (q16,c,+1)
(q13,+) (q17,+,0)
(q13,-) (q17,-,0)
(q13,=) (q17,=,0)
(q14,$) (q14,$,+1)
(q14,%) (q14,%,+1)
(q14,*) (q14,*,+1)
(q14,+) (q14,+,+1)
(q14,-) (q14,-,+1)
(q14,=) (q14,=,+1)
(q14,#) (q12,$,-1)
(q15,$) (q15,$,+1)
(q15,%) (q15,%,+1)
(q15,*) (q15,*,+1)
(q15,+) (q15,+,+1)
(q15,-) (q15,-,+1)
(q15,=) (q15,=,+1)
(q15,#) (q12,%,-1)
(q16,$) (q16,$,+1)
(q16,%) (q16,%,+1)
(q16,*) (q16,*,+1)
(q16,+) (q16,+,+1)
(q16,-) (q16,-,+1)
(q16,=) (q16,=,+1)
(q16,#) (q12,*,-1)
// str=w+w^r(a=+,b=-,c==)+w^r(a=$,b=%,c=*)+w(a=$,b=%,c=*)
(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,#) (q18,#,+1)
(q18,a) (q18,a,+1)
(q18,b) (q18,b,+1)
(q18,c) (q18,c,+1)
(q18,+) (q19,a,+1)
(q18,-) (q20,b,+1)
(q18,=) (q21,c,+1)
(q18,$) (q100,+,0)
(q18,%) (q100,-,0)
(q18,*) (q100,=,0)
(q19,a) (q19,a,+1)
(q19,b) (q19,b,+1)
(q19,c) (q19,c,+1)
(q19,+) (q19,+,+1)
(q19,-) (q19,-,+1)
(q19,=) (q19,=,+1)
(q19,$) (q19,$,+1)
(q19,%) (q19,%,+1)
(q19,*) (q19,*,+1)
(q19,#) (q17,a,-1)
(q20,a) (q20,a,+1)
(q20,b) (q20,b,+1)
(q20,c) (q20,c,+1)
(q20,+) (q20,+,+1)
(q20,-) (q20,-,+1)
(q20,=) (q20,=,+1)
(q20,$) (q20,$,+1)
(q20,%) (q20,%,+1)
(q20,*) (q20,*,+1)
(q20,#) (q17,b,-1)
(q21,a) (q21,a,+1)
(q21,b) (q21,b,+1)
(q21,c) (q21,c,+1)
(q21,+) (q21,+,+1)
(q21,-) (q21,-,+1)
(q21,=) (q21,=,+1)
(q21,$) (q21,$,+1)
(q21,%) (q21,%,+1)
(q21,*) (q21,*,+1)
(q21,#) (q17,c,-1)
// Replace +,$=a; -,%=b; *,==c
(q100,a) (q100,a,-1)
(q100,b) (q100,b,-1)
(q100,c) (q100,c,-1)
(q100,+) (q100,+,-1)
(q100,-) (q100,-,-1)
(q100,=) (q100,=,-1)
(q100,$) (q100,$,-1)
(q100,%) (q100,%,-1)
(q100,*) (q100,*,-1)
(q100,#) (q101,#,+1)
(q101,a) (q101,a,+1)
(q101,b) (q101,b,+1)
(q101,c) (q101,c,+1)
(q101,+) (q101,a,+1)
(q101,-) (q101,b,+1)
(q101,=) (q101,c,+1)
(q101,$) (q101,a,+1)
(q101,%) (q101,b,+1)
(q101,*) (q101,c,+1)
(q101,#) (R,#,0)
L53={ (a^2n)(b^2n)(c^n)(b^n) | n>=1}
// L53={ (a^2n)(b^2n)(c^n)(b^n) | n>=1}
(q0,a) (q0,a,+1)
(q0,b) (q1,b,+1)
(q0,c) (q100,c,0)
(q0,#) (q100,c,0)
(q1,a) (q100,a,0)
(q1,b) (q1,b,+1)
(q1,c) (q2,c,+1)
(q1,#) (q100,#,0)
(q2,a) (q100,a,0)
(q2,b) (q3,b,+1)
(q2,c) (q2,c,+1)
(q2,#) (q100,#,0)
(q3,a) (q100,a,0)
(q3,b) (q3,b,+1)
(q3,c) (q100,c,0)
(q3,#) (q4,#,-1)
(q4,a) (q4,a,-1)
(q4,b) (q4,b,-1)
(q4,c) (q4,c,-1)
(q4,#) (q5,#,+1)
// L53=(a^k)(b^x)(c^y)(b^z)
(q5,a) (q6,+,+1)
(q5,b) (q7,b,-1)
(q6,a) (q5,-,+1)
(q6,b) (q100,b,0)
// L53=(+-^n)(b^x)(c^y)(b^z)
(q7,+) (q7,+,-1)
(q7,-) (q7,-,-1)
(q7,a) (q7,a,-1)
(q7,*) (q7,*,-1)
(q7,#) (q8,#,+1)
(q8,+) (q9,a,+1)
(q8,a) (q8,a,+1)
(q8,-) (q8,-,+1)
(q8,*) (q10,*,-1)
(q9,+) (q9,+,+1)
(q9,-) (q9,-,+1)
(q9,*) (q9,*,+1)
(q9,b) (q7,*,-1)
(q9,c) (q100,c,0)
// L53=(a-^n)(*^n)(b^x-n)(c^y)(b^z)
(q10,*) (q10,*,-1)
(q10,a) (q10,a,-1)
(q10,-) (q10,-,-1)
(q10,+) (q10,+,-1)
(q10,#) (q11,#,+1)
(q11,+) (q11,+,+1)
(q11,-) (q11,-,+1)
(q11,a) (q12,+,+1)
(q11,*) (q13,*,0)
(q12,+) (q12,+,+1)
(q12,-) (q12,-,+1)
(q12,a) (q12,a,+1)
(q12,*) (q12,*,+1)
(q12,b) (q10,*,-1)
(q12,c) (q100,c,0)
// L53=(+-^n)(*^2n)(b^x-2n - must be zero)(c^y)(b^z)
(q13,*) (q13,*,+1)
(q13,b) (q100,b,0)
(q13,c) (q14,c,-1)
// L53=(+-^n)(*^2n)(c^y)(b^z)
(q14,*) (q14,*,-1)
(q14,-) (q14,-,-1)
(q14,+) (q14,+,-1)
(q14,a) (q14,a,-1)
(q14,%) (q14,%,-1)
(q14,#) (q15,#,+1)
(q15,+) (q16,a,+1)
(q15,a) (q15,a,+1)
(q15,-) (q15,-,+1)
(q15,*) (q17,*,+1)
(q16,-) (q16,-,+1)
(q16,+) (q16,+,+1)
(q16,*) (q16,*,+1)
(q16,%) (q16,%,+1)
(q16,c) (q14,%,-1)
(q16,b) (q100,b,0)
// L53=(a-^n)(*^2n)(%^n)(c^y-n - must be 0)(b^z)
(q17,*) (q17,*,+1)
(q17,%) (q17,%,+1)
(q17,c) (q100,c,+1)
(q17,b) (q18,b,-1)
// L53=(a-^n)(*^2n)(%^n)(b^z)
(q18,%) (q18,%,-1)
(q18,+) (q18,+,-1)
(q18,*) (q18,*,-1)
(q18,-) (q19,-.+1)
(q19,*) (q20,+,+1)
(q19,+) (q19,+,+1)
(q19,%) (q21,%,+1)
(q20,%) (q20,%,+1)
(q20,*) (q20,*,+1)
(q20,+) (q20,+,+1)
(q20,b) (q18,+,-1)
(q21,%) (q21,%,+1)
(q21,+) (q21,+,+1)
(q21,b) (q100,b,0)
(q21,#) (q101,#,-1)
(q100,a) (q100,a,+1)
(q100,b) (q100,a,+1)
(q100,c) (q100,a,+1)
(q100,*) (q100,a,+1)
(q100,+) (q100,a,+1)
(q100,-) (q100,a,+1)
(q100,%) (q100,a,+1)
(q100,$) (q100,a,+1)
(q100,&) (q100,a,+1)
(q100,#) (q102,#,-1)
(q102,a) (q100,#,-1)
(q102,b) (q100,#,-1)
(q102,c) (q100,#,-1)
(q102,*) (q100,#,-1)
(q102,+) (q100,#,-1)
(q102,-) (q100,#,-1)
(q102,%) (q100,#,-1)
(q102,$) (q100,#,-1)
(q102,#) (q103,#,+1)
(q103,#) (q104,F,+1)
(q104,#) (q105,a,+1)
(q105,#) (q106,l,+1)
(q106,#) (q107,s,+1)
(q107,#) (R,e,0)
(q101,a) (q101,a,+1)
(q101,b) (q101,a,+1)
(q101,c) (q101,a,+1)
(q101,*) (q101,a,+1)
(q101,+) (q101,a,+1)
(q101,-) (q101,a,+1)
(q101,%) (q101,a,+1)
(q101,$) (q101,a,+1)
(q101,&) (q101,a,+1)
(q101,#) (q108,#,-1)
(q108,a) (q108,#,-1)
(q108,b) (q108,#,-1)
(q108,c) (q108,#,-1)
(q108,*) (q108,#,-1)
(q108,+) (q108,#,-1)
(q108,-) (q108,#,-1)
(q108,%) (q108,#,-1)
(q108,$) (q108,#,-1)
(q108,&) (q108,#,-1)
(q108,#) (q109,#,+1)
(q109,#) (q110,T,+1)
(q110,#) (q111,r,+1)
(q111,#) (q112,u,+1)
(q112,#) (R,e,0)
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора