§5.4. Дерева розв’язань.

Розглянуті три модифікації РАМ, які ігнорують команди розгалуження й враховують лише ті кроки програми, котрі включають арифметичне обчислення. В деяких задачах зручно в якості основної міри складності брати число виконуваних команд розгалуження. У випадку сортування, наприклад, виходи збігаються з входами з точністю до порядку. Тому доцільно розглядати модель, в якій всі кроки дають розгалуження, котрі виникають в результаті порівняння двох величин. Зазвичай програму, яка складається із розгалужень, подають у вигляді дерева, котре називається деревом розв’язання. Кожна внутрішня вершина представляє один із кроків розв’язання. Тест, представлений коренем, виконується першим, а потім “управління“ передається одному із його нащадків в залежності від результату тесту. В загальному випадку управління передається від вершини до одного із нащадків (причому вибір у кожному випадку залежить від результату тесту в цій вершині), до тих пір поки не буде досягнутий листок. Потрібний вихід знаходиться в досягнутому листку.

Часова складність дерева розв’язання рівна висоті цього дерева як функція розміру задачі. Зазвичай вимірюють найбільшу кількість порівнянь, які потрібно робити, щоб знайти потрібний шлях від кореня до листка. Порядок величин при використанні моделі дерев розв’язувань (порівнянь) позначатимемо через . Відзначимо, що загальна кількість вершин у дереві може бути значно більшою, ніж його висота. Наприклад, дерево розв’язання для сортування n чисел повинно містити принаймні n! листків, хоч його висота може бути .

Лекція 6

§6.1. Машина Тюрінга.

Для доведення того, що для обчислення даної функції потрібен деякий мінімальний час, потрібна деяка модель, настільки ж загальна, як і розглянуті вище моделі, але більш проста. Система команд повинна бути обмежена, наскільки це можливо, хоч ця модель повинна бути здатною не лише обчислювати все те, що може обчислювати РАМ, а й робити це “майже“ так же швидко. Під словом“майже“ розумітимемо “поліноміально зв’язно“ .

Визначення 6.1. Говорять, що невід’ємні функції і поліноміально зв’язні (еквівалентні), якщо знайдуться такі поліноми і , що для всіх n виконуються нерівності і .

Приклад 6.1. Дві функції і поліноміально зв’язні: можна взяти , оскільки і , оскільки . Але й не є поліноміально зв’язними, тому що немає такого полінома , що для всіх n.

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

Визначення 6.2. Функція називається експоненціальною, якщо існують такі константи що для всіх, крім скінченого числа, значень n.

Відносно поліноміальної зв’язності всі експоненціальні функції, по суті, однакові; Будь-яка функція, поліноміально зв’язна з експоненціальною, сама експоненціальна.

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

Визначення 6.1. Багатострічкова машина Тюрінга складається з k стрічок, які нескінченні справа. Кожна стрічка розбита на клітинки, в кожній з яких міститься один із скінченного числа символів на стрічці. Одна клітинка на кожній стрічці оглядається голівкою стрічки; голівка може зчитувати із стрічки й записувати на неї. Робота машини Тюрінга визначається програмою, котра називається керуючим пристроєм. Він завжди знаходиться в одному із скінченного числа станів, які можна розглядати як теперішній номер команди в програмі.

Один крок обчислення на машині Тюрінга полягає у наступному. У відповідності до стану керуючого пристрою й символу на стрічці, котрий оглядається кожною із голівок, машина Тюрінга може виконати деякі або всі із наступних операцій:

1. змінити стан керуючого пристрою,

2. надрукувати нові символи на стрічках замість старих в яких-небудь або всіх клітинках під голівкою,

3. змістити які-небудь або всі голівки незалежно одна від іншої на одну клітинку вліво (L) або вправо (R) або залишити на місці (S).

Формально k-стрічкова машина Тюрінга задається семіркою

(Q, T, I, , b, , ),

де 1. Q – множина станів,

2.T – множина символів на стрічках,

3. I – множина вхідних символів, ,

4. b – порожній символ, b ,

5. – початковий стан,

6. – заключний стан,

7. – функція переходів, вона відображає деяку підмножину множини в {L, R, S})^k, тобто за довільним набором із станів і k символів на стрічках вона видає новий стан і k пар, кожна із яких складається із нового символу на стрічці й напрямку зсуву голівки.

Нехай і машина Тюрінга знаходиться в стані q, а її голівка на і-тій стрічці оглядає символ , . Тоді за один крок ця машина переходить в стан , змінює , на й зміщує голівку на і-тій стрічці в напрямку , .

Машину Тюрінга можна застосовувати для розпізнавання мови. Символи на стрічках такої машини включають алфавіт мови, котра розглядається (її букви виконують роль вхідних символів), порожній символ, який позначається b, і, можливо, інші символи. Спочатку на першій стрічці записано слово з вхідних символів по одному в клітинці, починаючи з самої лівої. Всі клітинки справа від клітинок, які містять вхідне слово, порожні. Всі інші стрічки повністю порожні.Слово з вхідних символів допускається (сприймається) тоді й тільки тоді, коли машина Тюрінга, почавши роботу у виділеному початковому стані (голівки про цьому знаходилися на лівих кінцях своїх стрічок), зробить послідовність кроків, які в кінці кінців приведуть в заключний стан. Мовою, котра допускається даною машиною Тюрінга, називається множина всіх слів із вхідних символів, які допускаються в описаному тільки що смислі.

Роботу машини Тюрінга формально можна описати за допомогою “миттєвого опису“. Миттєвим описом (МО) k-стрічкової машини Тюрінга М називається набір , де для кожного і є слово вигляду xqy, причому xy – слово на і-тій стрічці машини М (порожні символи, котрі стоять справа від його правого кінця, опускаються), а q – стан, в якому на даний час знаходиться машина. Голівка на і-тій стрічці оглядає символ, що стоїть справа від q.

Якщо миттєвий опис переходить в миттєвий опис за один крок Машини Тюрінга М, то пишуть |– (знак |– читається “переходить в“).

Якщо |– |– . . . |– для деякого то пишуть |– .

Якщо або , або |– , то пишуть |– .

Задана k-стрічкова машина Тюрінга М=(Q, T, I, , b, , ) допускає слово , де – елемент із І, якщо

|– для деяких котрі містять .

Приклад 6.1. Розглянемо машину Тюрінга, котра розпізнає паліндроми й на вхід якій подано слово 010.

Стан на даний час	Символ на		Новий символ, зсув голівки		Новий стан	Пояснення
	стрічці 1	стрічці 2	стрічка 1	стрічка 2
	0 1 B	b b b	0, S 1, S b, S	, R , R b, S		Якщо вхід не порожній, то на стрічці 2 друкується , голівка зміщується вправо; машина переходить в стан . В іншому випадку машина переходить в стан .
	0 1 B	B b b	0, R 1, R b, S	0, R 1, R b, L		Машина залишається в стані й переписує стрічку 1 на стрічку 2, поки на стрічці 1 не зустрінеться b. Потім вона переходить в стан .
	b b b	0 1	b, S b, S b, L	0, L 1, L , R		Голівка на стрічці 1 залишається на місці, на стрічці 2 зміщується вліво до . Потім машина переходить в стан .
	0 1	0 1	0, S 1, S	0, R 1, R		Стани і почережно змінюються. В порівнюються символи на обох стрічках, голівка на стрічці 2 зміщується вправо й машина переходить в стан . Далі вона переходить в і допускає вхідне слово, якщо голівка досягла b на стрічці 2. Якщо не досягла, то голівка на стрічці 1 зміщується вліво й машина повертається в стан . Чергування і не дає голівці зайти на стрічці 1 за її лівий кінець.
	0 0 1 1 0 1	0 1 0 1 b b	0, L 1, L 1, L 1, L 0, S 1, S	0, S 1, S 0, S 1, S b, S b, S
						Вхідне слово допускається.

Послідовність МО розглянутої машини Тюрінга: |–

|–

|–

|–

|–

|–

|–

|–

|–

|–

|–

|–

|–

|–

|– .

Оскільки – заключний стан, то ця машина Тюрінга допускає слово 010.

Машину Тюрінга, котра природно інтерпретується як пристрій, що допускає деяку мову, можна також розглядати як пристрій, що обчислює деяку функцію f. Аргументи цієї функції кодуються на вхідній стрічці у вигляді слова х із спеціальним маркером # , котрий відділяє їх один від одного. Якщо машина Тюрінга спиняється, маючи на стрічці, визначеної у значенні вихідної, ціле число у (значення функції), то покладають . Таким чином , процес обчислення мало відрізняється від процесу допущення мови.

Часова складність машини Тюрінга М - найбільше число кроків, зроблених нею при обробці входу довжини n (для всіх входів довжини n). Якщо на деякому вході довжини n машина спиняється, то для цього n значення не визначене.

Ємнісна складність машини Тюрінга М - найбільша відстань від лівого кінця стрічки, яку повинна пройти голівка при обробці входу довжини n. Якщо голівка на якійсь стрічці невизначено довго зміщується вправо, то функція не визначена. Порядок величин при застосуванні в якості моделі машини Тюрінга позначають .