Лабораторна робота №3
Застосування машини Т'юринга до слів
Визначення машини Т'юринга. Машина Т'юринга є математично (уявна) машина, а не машина фізична. Це такий же математичний об'єкт, як функція, похідна, інтеграл, група і так далі. І так само як і інші математичні поняття, поняття машини Т'юринга відбиває об'єктивну реальність, моделює деякі реальні процеси. Її зручно представити у вигляді автоматично працюючого приладу. У кожен дискретний момент часу пристрій, знаходячись в деякому стані, оглядає вміст однієї комірки стрічки, що простягається через пристрій, і робить крок, що полягає в тому, що пристрій переходить в новий стан, змінює (чи залишає без зміни) вміст клітини, що оглядається, і переходить до огляду наступної клітини - справа або ліворуч. Причому крок здійснюється на підставі наказаної команди. Сукупність усіх команд є програмою машини Т'юринга.
Структура машини Т'юринга
Машина Т'юринга (МТ) складається з двох частин - стрічки і автомата (дивліворуч) :
Стрічка використовується для зберігання інформації. Вона нескінченна в обидві сторони і розбита на клітини, які ніяк не нумеруються і не іменуються. У кожній клітині може бути записаний один символ або нічого не записано. Вміст клітини може мінятися – в неї можна записати інший символ або стерти символ, що знаходиться там.
Домовимося порожній вміст клітини називати символом "порожньо" і означати знаком Λ ("лямбда"). У зв'язку з цим зображення стрічки, показане на малюнку справа, таке ж, як і на малюнку ліворуч. Ця угода зручна тим, що операцію стирання символу в деякій клітині можна розглядати як запис в цю клітину символу Λ, тому замість довгої фрази "записати символ в клітину або стерти символ", що знаходиться там, можна говорити просто "записати символ в клітину".
Автомат – це активна частина МТ. У кожен момент він розміщується під однією з клітин стрічки і бачить її вміст; це видима клітина, а символ, що знаходиться в ній – видимий символ; вміст сусідніх і інших клітин автомат не бачить. Крім того, в кожен момент автомат знаходиться в одному із станів, які означатимемо буквою q з номерами: q1, q2 і тому подібне. Знаходячись в деякому стані, автомат виконує якусь певну операцію (наприклад, переміщається направо по стрічці, замінюючи усі символи b на а), знаходячись в іншому стані – іншу операцію.
Опишемо тепер машину Т'юринга Sретельніше. МашинаSмає в розпорядженні кінцеве число знаків (символів, букв),які створюютьтак званий зовнішній алфавітА= {a0,а1, ...,аn}. У кожнукоміркустрічки, що оглядається, в кожен дискретний момент часу може бути записаний тільки один символ з алфавітаА. Заради одноманітності зручно вважати, що серед буквзовнішнього алфавітуАє "порожня буква", і саме вона записана в порожнюкоміркустрічки. Стрічка передбачається необмеженоюв обидві сторони, але в кожен момент часу на ній записано кінцеве число непорожніх букв.
Далі, в кожен момент часу машина Sздатназнаходитися в одному стані з кінцевого числа внутрішніх станів, сукупність якихQ= {q0,q1, ...,qm}. Серед станів виділяються два -початковийq1ізавершальний(чи стан зупинки)q0. Знаходячись встаніq1машина починає роботу. Потрапивши в станq0, машина зупиняється.
Автомат може виконувати три елементарні дії: 1) записувати у видиму клітину новий символ (міняти вміст інших клітин автомат не може); 2) зрушуватися на одну клітину вліво або управо ("перестрибувати" відразу через декілька клітин автомат не може); 3) переходити в новий стан. Нічого іншого робити автомат не уміє, тому усі більш складні операції так чи інакше мають бути зведені до цих трьох елементарних дій.
Робота машини Sвизначаєтьсяпрограмою(функціональною схемою). Програма складається з команд. Кожна командаT(i, j)(i= 1, 2, ...,m;j= 0, 1,...,n) є вираженням одного з наступних видів:
де 0 ≤ k≤m; 0 ≤ λ ≤п. У виразах першого виду символ С часто опускатимемо.
Як же працює машина Т'юринга? Знаходячись в який-небудь момент часу в незавершальному стані (тобто в змозі, відмінному від q0), машина здійснює крок, який повністю визначається її поточним станомqi і символомaj,який сприймаєтьсянею в даний момент на стрічці. При цьому зміст кроку регламентований відповідною командоюT(i,j):qiaj → qkalX, де X ϵ {С, П,Л}. Крок полягає в тому, що: 1) вмістaj, клітини, що оглядаєтьсяна стрічці, стирається і на його місце записується символal(який може співпадати зaj); 2) машина переходитьв новий станqk(він також може співпадати з попереднім станомq1); 3) машина переходить до оглядунаступноїправоїкоміркивід тієї, яка оглядалася тільки що, якщо Х = П, або до огляду наступноїлівоїкомірки, якщо X = Л, або ж продовжує оглядати тужкоміркустрічки, якщо Х = С.
У наступний момент часу (якщо qk≠q0) машина робить крок, регламентований командоюТ(k, l): qkal →qrasXі так далі. Оскільки робота машини, по умові, повністю визначається її станом qi в даний момент і вмістом aj оглядаємої у цей момент комірки, то для кожних qi і aj (i = 1, 2, ..., m; j = 0, 1, ..., n) програма машини повинна містити одну і тільки одну команду, що починається символами qiaj. Тому програма машини Т'юринга із зовнішнім алфавітомА= {а0, а1 ,..., ап}і алфавітом внутрішніх станівQ = {q0, q1 ,..., qm} міститьm(n+ 1) команд.
Словом в алфавіті А або в алфавіті Q, або в алфавіті A U Q називається будь-яка послідовність букв відповідного алфавіта. Під k-ою конфігурацією розумітимемо зображення стрічки машини з інформацією, що склалася на ній на початок k-го кроку (чи слово в алфавіті А, записане на стрічку на початок k-го кроку), з вказівкою того, яка клітина оглядається в цей крок і в якому стані знаходиться машина. Мають сенс лише кінцеві конфігурації, тобто такі, в яких усі комірки стрічки, за виключенням, можливо, кінцевого числа, порожні. Конфігурація називається завершальною, якщо стан, в якому при цьому знаходиться машина, завершальний.
Якщо вибрати яку-небудь незавершальну конфігурацію машини Т'юринга як початкову, то робота машини полягатиме в тому, щоб послідовно (крок за кроком) перетворювати початкову конфігурацію відповідно до програми машини до тих пір, поки не буде досягнута завершальна конфігурація. Після цього робота машини Т'юринга вважається такою, що закінчилася, а результатом роботи вважається досягнута заключна конфігурація.
Говоритимемо, що непорожнє слово αв алфавітіА{a0} = {а1 ,..., ап} сприймається машиноюв стандартному положенні, якщо воно записане в послідовнихкомірках стрічки, усі іншікомірки порожні, і машина оглядає крайнюсправакоміркуз тих, в яких записано слово α. Стандартне положення називаєтьсяпочатковим (завершальним), якщо машина, сприймаюча слово в стандартному положенні, знаходиться в початковому станіq1(відповідно в стані зупинкиq0). Нарешті, будемо говорить, що словоα переробляється машиною в слово β, якщо від слова α, що сприймається в початковому стандартному положенні, машина після виконання кінцевого числа команд приходить до словаβ, що сприймається в положенні зупинки.