Машина Тьюринга - студопедія

Машина Тьюринга подібна машині Посту, але функціонує трохи інакше.

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

Порядок роботи МТ (з робочим алфавітом a0. A1. Аt і станами q0. Q1. Qs) описується таблицею машини Тьюринга. Ця таблиця є матрицею з чотирма стовпцями і (s + 1) (t + 1) рядками. Кожен рядок має вигляд

Тут через vij позначений елемент об'єднання алфавіту 0. а1. аt> і безлічі приписів для механізму протягування стрічки: l - перемістити стрічку вліво, r - перемістити стрічку вправо, s - зупинити машину; vij - дія МТ, що складається або в занесенні в осередок стрічки символу алфавіту a0. а1. аt, або в русі головки, або в зупинці машини; qij є наступним станом.

МТ працює згідно з такими правилами: якщо МТ знаходиться в стані qi, головка прочитує символ 0 в робочій комірці. Нехай рядок qi аj vij qij, що починається з символів qi. aj. зустрічається тільки один раз в таблиці. Якщо vij - буква робочого алфавіту, то головка стирає вміст робочої комірки і заносить туди цю букву. Якщо vij - команда r або l для механізму протягування стрічки, то стрічка зсувається на одну клітинку вправо або вліво (якщо не відбувається вихід за лівий край стрічки) відповідно. Якщо vij = s, то відбувається машинний останов.

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

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

Розглянемо приклади декількох схем машини Тьюринга.

1. Алгоритм додавання одиниці до числа п в десятковій системі числення. Дана десяткова запис числа п (тобто уявлення натурального числа п в десятковій системі числення); потрібно отримати десяткову запис числа п + 1.

Очевидно, що зовнішній алфавіт МТ повинен складатися з десяти цифр 0,1,2,3,4,5,6,7,8,9 і символу пробілу _. Ці цифри записують по одній в осередку (поспіль, без пропусків).

Виявляється достатнім мати два внутрішніх стану машини: q1 і q2.

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

2. Алгоритм запису числа в десятковій системі числення.

Дана кінцева послідовність міток, записаних в клітини стрічки поспіль, без пропусків. Потрібно записати в десятковій системі число цих міток перерахувати мітки).

Суть алгоритму може полягати в тому, що до числа 0, записаному на стрічці на початку роботи машини, машина додає 1, стираючи мітку за міткою, так що замість нуля виникає число 0 + k.

Легко можуть бути побудовані алгоритми складання чисел, їх перемноження, нападу найбільшого загального дільника і т.д. Однак, головна мета введення машин Посту і Тьюринга НЕ програмування для них, а вивчення властивостей алгоритмів і проблеми алгоритмічної можливості розв'язання задач.

Залежно від числа використовуваних стрічок, їх призначення і числа станів пристрою управління можна розглядати різні модифікації машин Тьюринга.

Припустимо, ми розширили визначення МТ, додавши певний стан q. пристрою управління машини. Будемо говорити, що якщо пристрій управління переходить в стан q0 для заданого вхідного слова х, то машина допускає х; якщо пристрій переходить в стан qx. то машина забороняє х. Таку машину будемо називати машиною Тьюринга з двома виходами. Можуть бути розглянуті численні варіанти машини Тьюринга, що мають деякий кінцеве число стрічок. У кожній клітині цих стрічок може перебувати один із символів зовнішнього алфавіту А = a0. a1. аn>. Пристрій управління машиною в кожен момент часу знаходиться в одному з кінцевого безлічі станів Q = 0. q1. qm>. Для K -ленточной машини конфігурація її в i -й момент часу описується системою k -слів виду:

перший індекс відповідає моменту часу, другий - номеру стрічки, третій -Номери клітини, вважаючи зліва направо. Кажуть, що машина виконує команду

Якщо, перебуваючи в стані qi і оглядаючи осередку з символами aa1 - aаk, машина переходить в стан qj, замінюючи вміст комірок відповідно символами аb1 - аbк, то після цього стрічки відповідно зсуваються в напрямках k1. kk.

До сих пір приймалося, що різні алгоритми здійснюються на різних машинах Тьюрінга, що відрізняються набором команд, внутрішнім і зовнішнім алфавітами. Однак, можна побудувати універсальну машину Тьюринга, здатну виконувати будь-який алгоритм будь-якої машини Тьюринга. Це досягається шляхом кодування конфігурації і програми будь-якої даної машини Тьюринга в символах зовнішнього алфавіту універсальної машини. Саме кодування повинно виконуватися в такий спосіб:

1) різні символи повинні замінюватися різними кодовими групами, але один і той же символ повинен замінятися усюди, де б він не зустрівся, однією і тією ж кодовою групою;

2) рядки кодових записів повинні однозначно розбиватися на окремі кодові групи;

3) повинна бути можливість розпізнати кодові групи, відповідні командам Л, П, С, розрізняти кодові групи, відповідні символам зовнішнього алфавіту і внутрішнім станам.

Для порівняння структур різних машин і оцінки їх складності необхідно мати відповідну міру складності машин. К.Шеннон запропонував розглядати в якості такого заходу твір числа символів зовнішнього алфавіту і числа внутрішніх станів. Великий інтерес викликає завдання побудови універсальної машин Тьюринга найменшою складності.

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

Таким же чином визначається операція зведення в ступінь: n -м ступенем машини Т називається твір T. Т c n співмножники.

Операція ітерації застосовна до однієї машини і визначається наступним чином. Нехай машина T1 має декілька заключних станів. Виберемо її r-е заключне стан і ототожнив його в схемі машини з її початковим станом. Отримана машина T є результатом ітерації машини Т1. Т = T1.

Перш ніж зупинитися на проблемі алгоритмічної можливості розв'язання задач звернемося до інших способів формалізації поняття алгоритму.