и Посту. Оскільки вид програми (Послідовності команд машини) залежить від початкового стану машини, воно повинно бути в явному вигляді зазначено в постановці завдання. В
4. Алгоритмічна машина Тьюринга
Машина Тьюринга (Turing machine) отримала свою назву за імені англійського математика Алана Тьюрінга, який запропонував в 1937 р. спосіб формального завдання алгоритмів за допомогою деякої абстрактної машини. Суть роботи зводиться до наступного. Мається потенційно нескінченна стрічка, розбита на клітинки, в кожній з яких може бути записаний один символ з деякого кінцевого алфавіту. Машина Тьюринга має головку читання/запису, яка дозволяє прочитати символ в поточному осередку, записати символ в комірку, а також зрушити голівку вліво або вправо в сусідню клітинку. Машина працює дискретно, по тактам і на кожному такті знаходиться в одному з можливих станів, яких кінцеве число. Для кожної пари (стан, оглядає, символ) визначена трійка (записуваний символ, рух головки, новий стан). До початку роботи машина Тьюринга знаходиться в початковому стані, а головка читання-запису оглядає на стрічці саму ліву непорожню клітинку. Таким чином, оглядаючи черговий символ, машина записує новий символ (може бути, той же самий), зрушує голівку вліво, вправо чи залишається на місці і переходить у новий стан чи залишається в колишньому. p> Машина Тьюринга складається з трьох частин: стрічки, що зчитує (Записуючої) головки і логічного пристрою (рис. 1). p> Стрічка виступає в якості зовнішньої пам'яті. Вона вважається необмеженої (нескінченної). Вже це свідчить про те, що машина Тьюринга є модельним пристроєм, оскільки жодне реальний пристрій не може володіти пам'яттю нескінченного розміру.
В
Рис. 1 - Схема машина Тьюринга
Як і в машині Посту, стрічка розбита на окремі осередки, проте в машині Тьюринга нерухомою є головка, а стрічка пересувається щодо неї вправо або вліво. p> Іншою відмінністю є те, що вона працює не в двійковому, а деякому довільному кінцевому алфавіті A = {О”, a 1 ... a n } - Цей алфавіт називається зовнішнім. У ньому виділяється спеціальний символ - О”, званий порожнім знаком - його посилка в будь-яку клітинку стирає той знак, який до цього там перебував, і залишає клітинку порожньою. У кожну клітинку стрічки може бути записаний лише один символ. Інформація, що зберігається на стрічці, зображується кінцевої послідовністю знаків зовнішнього алфавіту, відмінних від порожнього знака.
Головка завжди розташована над однією з комірок стрічки. Робота відбувається тактами (кроками). Система виконуваних головкою команд гранично проста: на кожному такті вона робить заміну знака в оглядається осередку a i знаком a j . При цьому можливі поєднання:
- j = i - означає, що в оглядається осередку знак не змінився;
- i в‰ 0, j = 0 - зберігався в комірці знак замінюється порожнім, тобто стирається;
- i = 0, j в‰ 0 - порожній знак замінюється непустою (з номером j в алфавіті), тобто виробляється вставка знака;
- i в‰ j в‰ 0 - відповідає заміні одного знака іншим. p> Таким чином, в машині Тьюринга реалізується система гранично простих команд обробки інформації. Ця система команд обробки доповнюється також гранично простою системою команд переміщень стрічки: на комірку вліво, на клітинку вправо і залишитися на місці, тобто адреса оглядає, осередки в результаті виконання команди може або змінитися на 1, або залишитися незмінним. Однак, хоча фактично відбувається переміщення стрічки, зазвичай розглядається зсув голівки щодо оглядає, секції. З цієї причини команда зсуву стрічки вліво позначається R (Right), зсуву вправо - L (Left), відсутність зсуву - S (Stop). Ми будемо говорити саме про зрушення головки і вважати R, L і S командами її руху. Елементарність цих команд означає, що при необхідності звернення до вмісту деякої комірки, вона відшукується тільки за допомогою ланцюжка окремих зрушень на одну клітинку. Зрозуміло, це значно подовжує процес обробки, зате дозволяє обійтися без нумерації осередків і використання команд переходу за адресою, тобто скорочує кількість істинно елементарних кроків, що важливо в теоретичному відношенні.
Обробка інформації та видача команд на запис знака, а також зсуву стрічки в машині Тьюринга проводиться логічним пристроєм (ЛУ). ЛУ може знаходитися в одному з станів, які утворюють кінцеве безліч і позначаються Q = {q 1 ... q m , z}, причому стан z відповідає завершенню роботи, а q 1 є початковим (вихідним). Q спільно зі знаками R, L, S утворюють внутрішній алфавіт машини. ЛУ має два вхідних каналу (a i , q i ) і три вихідних (a i +1 , q i +1 , D i +1 ) (див. рис. 2):
В
Рис. 2 - Схема логічного пристрою машини Тьюринга
Розуміти схему необхідно наступним чином: на такті i на один вхід ...
