ЛУ подається знак з обозреваемой в даний момент комірки (a i ,), а на інший вхід - знак, що позначає стан ЛУ в даний момент (q i ). Залежно від отриманого поєднання знаків (a i , q i ) і наявних правил обробки ЛУ виробляє і по першому вихідному каналу направляє в оглядається осередок новий знак (a i +1 ), подає команду переміщення головки (D i +1 з R, L і S), а також дає команду на виклик наступного керуючого знака (q i +1 ). Таким чином, елементарний крок (такт) роботи машини Тьюринга полягає в наступному: головка зчитує символ з обозреваемой осередку і, залежно від свого стану і прочитаного символу, виконує команду, в якій зазначено, який символ записати (або стерти) і який рух вчинити. При цьому і головка переходить в новий стан. Схема функціонування такої машини представлена ​​на малюнку 3. br/>В
Рис. 3 - Схема функціонування машини Тьюринга
алгоритмічний машина пост Тьюринг
У даній схемі відображено поділ пам'яті на зовнішню і внутрішню. Зовнішня представлена, як вказувалося, у вигляді нескінченної стрічки - вона призначена для зберігання інформації, закодованої в символах зовнішнього алфавіту. Внутрішня пам'ять представлена ​​двома осередками для зберігання наступній команди протягом поточного такту: у Q передається з ЛУ і зберігається наступне стан (q i +1 ), а в D - команда зсуву (D i +1 ). З Q за лінії зворотного зв'язку q i +1 надходить у ЛУ, а з D команда надходить на виконавчий механізм, що здійснює при необхідності переміщення стрічки на одну позицію вправо або вліво.
Загальне правило, за яким працює машина Тьюринга, можна представити наступною записом: q i a j в†’ q i ' a j 'D k , тобто після огляду символу a j головкою в стані q i у клітинку записується символ a j ', головка переходить в стан q i ', а стрічка робить рух D k . Для кожної комбінації q i a j є рівно одне правило перетворення (правил немає тільки для z, оскільки, потрапивши в цей стан, машина зупиняється). Це означає, що логічний блок реалізує функцію, сопоставляющую кожній парі вхідних сигналів q i a j одну і тільки одну трійку вихідних q i 'a j ' D k - вона називається логічною функцією машини і зазвичай представляється у вигляді таблиці (Функціональною схемою машини), стовпці якої позначаються символами станів, а рядки - знаками зовнішнього алфавіту. Якщо знаків зовнішнього алфавіту n, а число станів ЛУ m, то, очевидно, загальне число правил перетворення складе n Г— m.
Конкретна машина Тьюринга задається перерахуванням елементів множин A і Q, а також логічною функцією, яку реалізує ЛУ, тобто набором правил перетворення. Ясно, що різних множин A, Q і логічних функцій може бути нескінченно багато, тобто і машин Тьюринга також нескінченно багато.
Перш ніж обговорювати функціонування машини Тьюринга, введемо ще одне поняття - конфігурації машин, тобто сукупності станів всіх осередків стрічки, стану ЛУ і положення головки.
Записати конфігурацію можна таким чином: О”a 1 q i a j ... a k О”, яка означає, що в слові з k символів оглядається секція номер j і при цьому управляючий пристрій знаходиться в стані q i . Ясно, що конфігурація машини може містити будь-яку кількість символів зовнішнього алфавіту і лише один символ внутрішнього. Часто конфігурацію записують у вигляді a 1 q i a 2 , де a 1 - слово на стрічці зліва від головки , a 2 - слово на стрічці праворуч від головки, включаючи розглядаємим знак. Зліва від a 1 і праворуч від a 2 стрічка порожня. p> Перед початком роботи на порожню стрічку записується вихідне слово a кінцевої довжини в алфавіті A; головка встановлюється над першим символом слова a, ЛУ переводиться в стан q 1 (тобто початкова конфігурація має вигляд q 1 a). Оскільки в кожній конфігурації реалізується тільки одне правило перетворення, початкова конфігурація однозначно визначає всю наступну роботу машини, тобто всю послідовність конфігурацій аж до припинення роботи.
Залежно від початкової конфігурації можливі два варіанти розвитку подій:
1) після кінцевого числа тактів машина зупиняється по команді зупинки; при цьому на стрічці виявляється кінцева конфігурація, відповідна вихідної інформації;
2) зупинки не відбувається. p> У першому випадку говорять, що дана машина застосовна до початковій інформації, у другому - ні. Вся сукупність вхідних конфігурацій, при яких машина забезпечує отримання результату, утворюють клас розв'язуваних завдань. Очевидно, з...
