Документ Microsoft Word (6). А) Зобразимо схематично початкову конфігурацію (початковий стан машини)

Название	А) Зобразимо схематично початкову конфігурацію (початковий стан машини)
Дата	11.07.2022
Размер	35.91 Kb.
Формат файла
Имя файла	Документ Microsoft Word (6).docx
Тип	Документы #628812

1) На деякому етапі виникає стан, яких розглядається як заключний або цільовий, при цьому відбувається зупинка обчислення і визначається результат Q.

2) Кожний поточний стан змін наступний до нескінченності, тобто процес обчислення ніколи не зупиниться.

3) При деякому стані виникає ситуація, коли процес обчислення переривається без видачі результату.

У випадку 3 не має переходу до наступного кроку і не має результату обчислень, тоді говорять, що відбувається безрезультатна зупинка. Вважається, що алгоритм А можна застосувати до вхідного набору даних Р, тоді і тільки тоді, коли виникає випадок 1, тобто процес обчислення закінчився і отримано результат обчислень Q.

Даний результат позначаємо А(Р). Зауваження: у випадках 2 і 3 результат А(Р) не існує.

Термін алгоритм походить від латинського перекладу арабського імені середньоазіатського вченого Аль-Хорезмі –Мухамеда Бен Муси.

2)

а) Зобразимо схематично початкову конфігурацію (початковий стан машини):

1 0 a 1 1 0 a 0 a 1 1

Схема означає, що машина перебуває в положенні 1 q й оглядає комірку, в якій записана буква 1, у сусідній ліворуч комірці записана та же буква, а в сусідній праворуч комірці записана буква 0 a (тобто, згідно з нашою домовленістю, нічого не записано) тощо. Нічого не записано й у всіх непоказаних комірках стрічки. На першому такті роботи згідно з командою q11Пq11 машина залишається в колишньому положенні 1, в комірку, що оглядається, вписує букву 1 (тобто фактично залишає уже писану в цю комірку букву 1 незмінною) і переходить до огляду наступної правої комірки (тобто, комірки 5). Зобразимо схематично положення, в якому оказалась машина:

1 q 1 0 a 1 1 0 a 0 a 1 1

На другому такті роботи згідно з командою q01q1a0 машина вписує в комірку 5, що оглядається, букву 1, продовжує оглядати ту же комірку і переходить у стан 0 q , тобто зупиняється. Конфігурація, що склалась, має вигляд:

1 q 1 0 a 1 1 1 0 a 1 1

Таким чином, з даного начального положення слово 1a011a0a011 переробляється машиною в слово 1a0111a011. 2. Надана машина Тюрінга із зовнішнім алфавітом a0 A , алфавітом,1 внутрішніх положень q0 Q , q1 , q2 , q3 , q4 , q5 , q6 , q7 і з такою функціональною схемою (програмою):

9 Q A 1 q 2 q q3 4 q q5 6 q 7 q 0 a q4a0П q6a0П q6a0П q01 q4a0П q0a0 q6a0П 1 q21Л q31Л q11Л q5a0 q5a0 q7a0 q7a0

Зображуючи на кожному такті роботи машини конфігурацію, що отримується, визначте, в яке слово переробляє машина кожне з наступних слів, виходячи з початкового стандартного положення: а) 11111; б) 111111; в) 1111; г) 1111111; д) 111; е) 1a0111a0a01111 ; ж) 11a0a0111111 ; з) 11a0111

3)

1 Створимо НАМ U₅для обчислення ф-ції S(x) = x + 1, коли х записано в 5-значній системі числення. НАМ U₅запишемо у вигляді 3-х стовпчиків формул підстановок

01) 0	1 6) 0*	1 11) 0у
12) 1	2 7) 1*	2 12) 1у
23) 2	3 8) 2*	3 13) 2у
34) 3	4 9) 3*	4 14) 3у
45) 4	у010) 4*	у015) 4у
		1 16) у
		*17)

2 Застосуємо U₅для обчислення S(n), (де n=24₁₀), попередньо перевівши цей порядковий номер у 5- значну систему числення

( n=44₅). Протокол застосування U₅(в дужках вкажемо номер застосованої підстановки) :

44 (17)

*44 (5)

4*4 (5)

44* (10)

*4у4 (15)

у00 (16)

100 (17)

U_m (44₅)=100₅=25₁₀..

} в частку від ділення цього числа на 3, записану в тому самому алфавіті.3 Побудуємо нормальний алгоритм Маркова, який перетворює кожне натуральне число, записане в алфавіті А= {

f	I1) III 2) I  3) * *

4 Побудуємо нормальний алгоритм Маркова U, який є композицією двох нормальних алгоритмів Маркова U₁іU₂, при чому:

U₁} на число 2;- збільшує кожне натуральне число, записане в алфавіті А= {

U₂ } на число 1;- збільшує кожне натуральне число, записане в алфавіті А= {

II1) *

I 2)

*3)

4)

Припустимо що існує набір F <--> H для якого справджується нерівність

F->H

Застосовуючи рівносильні перетворення отримаємо наступне:

H^L, (L^Z) <->F, Z <-> H

Що протирічить нерівності Коші. Отже правильна початкова нерівність.

5)

1. При n=7 маємо:

((P<->Q) ^ R) -> ((R^P) <-> Q) тобто нерівність правильна.

2. Припустимо, що нерівність виконується при