Лекція 7

§ 7.1. Зв’язок машин Тюрінга і рам.

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

Розглянемо зв’язок між РАМ і МТ. Очевидно, що РАМ може моделювати роботу k-стрічкової МТ, поміщаючи по одній клітинці МТ в регістр. Зокрема, і-ту клітинку j-тої стрічки можна зберігати в регістрі , де с – постійна, призначення якої – дати РАМ деякий “оперативний простір“. У нього включаються k регістрів для запам’ятовування k голівок МТ.

РАМ може зчитувати клітинки МТ, використовуючи непряму адресацію за допомогою регістрів, які містять положення голівок.

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

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

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

Теорема 7.1. Нехай L – мова, котра розпізнається РАМ за час при логарифмічній вазі. Якщо в РАМ-програмі немає множення й ділення, то на багато стрічкових машинах Тюрінга L має часову складність не більшу .

Доведення. Подамо всі регістри, які не містять нуля, РАМ, що розглядається, так

#

#

#

#

#

#

#

#

…

#

#

#

B

…

На стрічці розміщена послідовність пар чисел , записаних у двійковій формі без нулів на початку слова й розділених маркерами. Для кожного число є вмістом регістра РАМ. Вміст суматора РАМ зберігається в двійковому коді на другій стрічці, а третя відіграє роль робочої пам’яті. Ще дві стрічки служать для запису входу й виходу РАМ. Кожен крок програми РАМ поданий скінченним числом станів МТ. Ми не будемо описувати моделювання всіх команд РАМ, а розглянемо лише команди ADD 20 i STORE 30, які пояснюють загальну ідею. Для ADD 20 можна побудувати МТ так, щоб вона працювала наступним чином.

1. На стрічці 1 відшукується місце, відповідне регістру 20 в РАМ, тобто послідовність # # 10100 #. Якщо воно знаходиться, на стрічку 3 поміщається наступне за ним число, яке буде вмістом регістру 20.Якщо ж таке місце не знайшлося, машина спиняється – вміст регістру 20 дорівнює 0, й тому непряму адресацію виконати неможна.

2. На стрічці 1 розшукується місце, де зберігається регістр РАМ, номер якого записаний на стрічці 3. Якщо воно знаходиться, то вміст цього регістру записується на стрічку 3. Якщо ні, туди поміщається 0.

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

Для моделювання STORE 30 можна так побудувати МТ, щоб вона працювала наступним чином:

1. Розшукується місце розташування регістра 30 в РАМ, тобто # # 11110 #.

2. Якщо воно знаходиться, то на стрічку 3 записується все, що розташовано справа від # # 11110 #, крім числа, котре стоїть безпосередньо справа (тобто старого вмісту регістру 30). Потім вміст суматора (на стрічці 2) записується безпосередньо справа від # # 11110 #, а за ним поміщається слово, котре скопійоване на стрічку 3.

3. Якщо на стрічці 1 не знайшлося місця, відповідного регістру 30, то, дійшовши до самого лівого порожнього символу, машина друкує

11110 # , потім вміст суматора й, на кінець, # #.

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

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

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

Теорема 7.2. РАМ і РАСП з логарифмічною вагою й машини Тюрінга поліноміально зв’язні.

Аналогічний результат має місце й для ємнісної складності.