Лекція 10

§1. Детерміноване моделювання нмт

За допомогою моделювання можна показати, що будь-яка мова, яка допускається якою-небудь НМТ, допускається також і деякою ДМТ, проте за це приходиться розплачуватися значним збільшенням часової складності. Найменша верхня межа, яку можна установити для такого моделювання, експоненціальна. Іншими словами, якщо – розумна функція, котра задає часову складність ( розумна в тому сенсі, що вона “конструйована за часом“), то для кожної НМТ М, час роботи якої обмежений функцією , можна знайти такі постійну с і ДМТ , що , і час роботи машини складає .

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

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

Потрібно підкреслити, що не відомо ніяких нетривіальних нижніх оцінок, які стосуються складності моделювання НМТ за допомогою ДМТ. А саме, не відома ніяка мова L, котру може допустити деяка НМТ з часовою складністю , але про яку можна довести, що вона не допускається ніякою ДМТ з часовою складністю . Ситуація з ємкісною складністю дещо краща.

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

Можна показати, що коли – конструйована по ємкості функція, а М – НМТ з ємкісною складністю, обмеженою функцією , то знайдеться така ДМТ з ємнісною складністю , що .

Одна із стратегій, за допомогою якої може моделювати М, полягає в цікавому застосуванні прийому “ розділяй і володарюй“. Якщо ємкісна складність k- cтрічкової НМТ М=(Q, T, I, δ, b, , ) обмежена функцією , яка конструюється по ємкості, то для деякої константи с число різних МО, в які М може попасти, почавши роботу з входом довжини n, не перевищує , а точніше , де перший множник представляє число станів, другий обмежує число можливих станів стрічок, а останній – число можливих положень голівок. Тому, якщо |– , то М може дійти із МО в МО за 2і кроків, перевіривши для всіх чи здійсненні переходи |– і |– за і кроків.

Таким чином, стратегія, на якій ґрунтується робота , полягає в тому, щоб установити за допомогою описаного нижче алгоритму, чи приведе початкове МО до деякого допускаю чого МО.