Вступ

У 1936 р. Аланом Тьюрінгом для уточнення поняття алгоритму було запропоновано абстрактний універсальний виконавець. Його абстрактність полягає в тому, що він є логічною обчислювальною конструкцією, а не реальною обчислювальною машиною. Термін "універсальний виконавець" говорить про те, що цей виконавець може імітувати будь-який інший виконавець. Наприклад, операції, які виконують реальні обчислювальні машини, можна імітувати на універсальному виконавці. Надалі, придумана Тьюрінгом обчислювальна конструкція була названа машиною Тьюрінга.

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

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

Основні положення машини Тюрінга

Машина Тюрінга (Turing machine) отримала свою назву на ім'я англійського математика Алана Тюрінга, який запропонував у 1937 р. спосіб формального завдання алгоритмів за допомогою деякої абстрактної машини. Суть роботи зводиться до наступного. Є потенційно нескінченна стрічка, розбита на комірки, у кожному з яких може бути записаний один символ деякого кінцевого алфавіту. Машина Т'юрінга має головку читання/запису, яка дозволяє прочитати символ у поточному осередку, записати символ в осередок, а також зрушити головку вліво або вправо в сусідній осередок. Машина працює дискретно, по тактах і кожному такті перебуває у одному з можливих станів, яких кінцеве число. Для кожної пари (стан, огляд символ) визначена трійка (записується символ, рух головки, новий стан). До початку роботи машина Тьюринга знаходиться в початковому стані, а головка читання-запису оглядає на стрічці найлівіший непустий осередок. Таким чином, оглядаючи черговий символ, машина записує новий символ (може бути, той самий), зрушує голівку вліво, вправо або залишається на місці і переходить в новий стан або залишається в колишньому.

Машина Тьюринга складається з трьох частин: стрічки, що зчитує (записує) головки та логічного пристрою, що наочно показано на малюнку 1.

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

Малюнок 1 - Схема машина Тюрінга

Машина Тьюринга працює у деякому довільному кінцевому алфавіті A = (_, a1…an) - цей алфавіт називається зовнішнім. У ньому виділяється спеціальний символ - _, званий порожнім знаком - його посилка в якийсь осередок стирає той знак, який раніше там знаходився, і залишає осередок порожнім. У кожен осередок стрічки може бути записаний лише один символ. Інформація, що зберігається на стрічці, є кінцевою послідовністю знаків зовнішнього алфавіту, відмінних від порожнього знака.

Головка завжди розташована над одним із осередків стрічки. Робота відбувається тактами (кроками). Система виконуваних головкою команд гранично проста: на кожному такті вона робить заміну знака в осередку, що оглядається, ai знаком aj. При цьому можливі поєднання:

1) аj = аi - означає, що в осередку, що оглядається, знак не змінився;

2) аi? _, аj = _ - що зберігається у осередку знак замінюється порожнім, тобто. стирається;

3) аi = _, аj? _ - порожній знак замінюється непустим (з номером j в абетці), тобто. провадиться вставка знака;

4) аi? аj? _ - відповідає заміні одного символу іншим.

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

Однак, хоча фактично відбувається переміщення стрічки, зазвичай розглядається зсув головки щодо секції, що оглядається. Тому команда зсуву стрічки вліво позначається R (Right), зсуву вправо - L (Left), відсутність зсуву - S (Stop). Ми говоритимемо саме про зсув голівки і вважатимемо R, L і S командами її руху.

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

Обробка інформації та видача команд на запис знака, а також зсув стрічки в машині Тьюринга проводиться логічним пристроєм (ЛУ). ЛУ може бути в одному зі станів, які утворюють кінцеву множину і позначаються Q =(q1…qm, q0) , причому стан q0 відповідає завершенню роботи, а q1 є початковим (вихідним). Q разом із знаками R, L, S утворюють внутрішній алфавіт машини. ЛУ має два вхідні канали (ai, qi) і три вихідні (ai+1, qi+1, Di+1). Схема ЛУ машини Тьюринга зображено малюнку 2.

Малюнок 2 - Схема ЛУ машини Тюрінга

Розуміти схему необхідно наступним чином: на такті i на один вхід ЛУ подається знак із комірки, що оглядається в даний момент (ai), а на інший вхід - знак, що позначає стан ЛУ в даний момент (qi). Залежно від отриманого поєднання знаків (ai, qi) і наявних правил обробки ЛУ виробляє і по першому вихідному каналу направляє в осередок новий знак (ai+1), подає команду переміщення головки (Di+1 з R, L і S), а також дає команду на перехід до наступного стану (qi+1). Таким чином, елементарний крок (такт) роботи машини Тьюринга полягає в наступному: головка зчитує символ із осередку, що оглядається, і, залежно від свого стану і прочитаного символу, виконує команду, в якій зазначено, який символ записати (або стерти) і який рух здійснити . При цьому і головка переходить у новий стан. Схема функціонування такої машини представлена ​​малюнку 3.

Рисунок 3 - Схема функціонування машини Тюрінга

У цій схемі відображено поділ пам'яті на зовнішню та внутрішню. Зовнішня представлена, як зазначалося, як нескінченної стрічки - вона варта зберігання інформації, закодованої у символах зовнішнього алфавіту. Внутрішня пам'ять представлена ​​двома осередками для зберігання наступної команди протягом поточного такту: Q передається з ЛУ і зберігається наступний стан (qi+1), а D - команда зсуву (Di+1). З Q по лінії зворотнього зв'язку qi+1 надходить у ЛУ, та якщо з D команда надходить на виконавчий механізм, здійснює за необхідності переміщення стрічки однією позицію вправо чи вліво.

Загальне правило, яким працює машина Тьюринга, можна наступним записом: qi aj > qi" aj" Dk, тобто. після огляду символу aj головкою в стані qi в комірку записується символ aj", головка переходить у стан qi", а стрічка здійснює рух Dk. Для кожної комбінації qi aj є одно правило перетворення (правил немає тільки для q0, оскільки, потрапивши в цей стан, машина зупиняється). Це означає, що логічний блок реалізує функцію, що зіставляє кожній парі вхідних сигналів qi aj одну і тільки одну трійку вихідних qi"aj"Dk - вона називається логічною функцією машини і зазвичай представляється у вигляді таблиці (функціональної схеми машини), стовпці якої позначаються символами станів а рядки - знаками зовнішнього алфавіту. Якщо знаків зовнішнього алфавіту n, а кількість станів ЛУ m, то, очевидно, загальне числоправил перетворення становитиме nЧm.

Конкретна машина Тьюринга задається перерахуванням елементів множин A і Q, і навіть логічної функцією, що її реалізує ЛУ, тобто. набором правил перетворення. Ясно, що різних множин A, Q і логічних функційто, можливо нескінченно багато, тобто. і машин Тюрінга також нескінченно багато.

Потрібно також запровадити поняття зміни машин, тобто. сукупності станів всіх осередків стрічки, стану ЛУ та положення головки. Зрозуміло, що конфігурація машини може містити будь-яку кількість символів зовнішнього алфавіту і лише символ внутрішнього.

Перед початком роботи на порожню стрічку записується вихідне слово кінцевої довжини в алфавіті A; головка встановлюється над першим символом слова a, ЛУ перетворюється на стан q1 (тобто початкова конфігурація має вигляд q1a). Оскільки кожної конфігурації реалізується лише одне правило перетворення, початкова конфігурація однозначно визначає всю подальшу роботу машини, тобто. всю послідовність змін до припинення роботи.

Залежно від початкової зміни можливі два варіанти розвитку подій:

1) після кінцевого числа тактів машина зупиняється за командою зупинки; при цьому на стрічці виявляється кінцева конфігурація, що відповідає вихідній інформації;

2) зупинки не відбувається.

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

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

1. Опис машини Тюрінга. 3

1.1 Властивості машини Т'юрінга як алгоритму. 5

2. Складність алгоритмів. 7

2.1 Складність проблем.

3. Машина Тьюринга та алгоритмічно нерозв'язні проблеми.

Висновок. 16

Список литературы.. 18

Вступ

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

Пристрій машини Тьюринга надзвичайно простий, проте на ній можна виконати практично будь-яку програму. Для виконання всіх цих дій передбачена спеціальна таблиця правил, в якій прописано, що потрібно робити за різних комбінацій поточних станів і символів, прочитаних зі стрічки.

У 1947 р. Алан Т'юрінг розширив визначення, описавши "універсальну машину Тюрінга". Пізніше для вирішення певних класів завдань було введено її різновид, який дозволяв виконувати не одне завдання, а кілька.

1. Опис машини Тюрінга

Передісторія створення цієї роботи пов'язана з формулюванням Давидом Гільбертом на Міжнародному математичному конгресі в Парижі в 1900 невирішених математичних проблем. Однією з них була задача доказу несуперечності системи аксіом звичайної арифметики, яку Гільберт надалі уточнив як "проблему розв'язності" - знаходження загального методу для визначення здійсненності даного висловлювання мовою формальної логіки.

Стаття Тюрінга якраз і давала відповідь на цю проблему - друга проблема Гільберта виявилася нерозв'язною. Але значення статті Тьюринга виходило далеко за межі того завдання, з приводу якого вона була написана.

Наведемо характеристику цієї роботи, що належить Джону Хопкрофту: "Працюючи над проблемою Гільберта, Тьюрингу довелося дати чітке визначення самого поняття методу. Відштовхуючись від інтуїтивного уявлення про метод як про якийсь алгоритм, тобто процедуру, яка може бути виконана механічно, без , він показав, як цю ідею можна втілити у вигляді докладної моделі обчислювального процесу. Отримана модель обчислень, у якій кожен алгоритм розбивався на послідовність простих, елементарних кроків, і була логічною конструкцією, названою згодом машиною Тьюринга.

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

Формально машина Тюрінга може бути описана в такий спосіб. Нехай задані:

кінцеве безліч станів – Q, у яких може бути машина Тьюринга;

кінцева множина символів стрічки - Г;

функція δ (функція переходів або програма), яка задається відображенням пари з декартового твору Q x Г (машина знаходиться в стані qi та оглядає символ gi) у трійку декартового твору Q х Г х (L,R) (машина переходить у стан qi, замінює символ gi на символ gj і пересувається вліво або вправо на один символ стрічки) - Q x Г-> Q х Г х (L,R)

один символ із Г->е (порожній);

підмножина Σ є Г -> визначається як підмножина вхідних символів стрічки, причому е є (Г - Σ);

один із станів – q0 є Q є початковим станом машини.

Розв'язувана проблема задається шляхом запису кінцевої кількості символів з множини Σ є Г – Si є Σ на стрічку:

eS1S2S3S4... ... ... Sne

після чого машина переводиться в початковий стан і головка встановлюється у найлівішого непустого символу (q0,w) –, після чого відповідно до зазначеної функції переходів (qi,Si) - ->(qj,Sk, L або R) машина починає замінювати оглядові символи, пересувати головку вправо або вліво і переходити до інших станів, запропонованих функцій переходів.

Зупинка машини відбувається у випадку, якщо для пари (qi,Si) функція переходу не визначена.

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

1.1 Властивості машини Т'юрінга як алгоритму

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

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

Зрозумілість. На кожному кроці в осередок пишеться символ з алфавіту, автомат робить один рух (Л, П, Н), і машина Тьюринга перетворюється на одне з описаних станів.

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

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

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

2. Складність алгоритмів

Складність алгоритму визначається обчислювальними потужностями, необхідні його виконання. Обчислювальна складність алгоритму часто вимірюється двома параметрами: Т (тимчасова складність) та S (просторова складність або вимоги до пам'яті). І Т, і S зазвичай представляються як функцій від n, де n - це розмір вхідних даних. (Існують інші способи вимірювання складності: кількість випадкових біт, ширина каналу зв'язку, обсяг даних тощо)

Зазвичай обчислювальна складність алгоритму виражається за допомогою нотації "Про велике", тобто описується порядком величини обчислювальної складності. Це просто член розкладання функції складності, що найшвидше зростає зі зростанням n, всі члени нижчого порядку ігноруються. Наприклад, якщо тимчасова складність даного алгоритму дорівнює 4n2+7n+12, то обчислювальна складність порядку n2 записується як О(n2).

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

Ця нотація дозволяє побачити, як обсяг вхідних даних впливає на вимоги до часу та обсягу пам'яті. Наприклад, якщо Т=О(n), то подвоєння вхідних даних подвоїть час виконання алгоритму. Якщо Т=О(2n), додавання одного біта до вхідних даних подвоїть час виконання алгоритму.

Зазвичай алгоритми класифікуються відповідно до їх часової або просторової складності. Алгоритм називають постійним, якщо його складність залежить від n: 0(1). Алгоритм є лінійним, якщо його тимчасова складність О(n). Алгоритми може бути квадратичними, кубічними тощо. Всі ці алгоритми – поліноміальні, їх складність – О(m), де m – константа. Алгоритми з поліноміальною тимчасовою складністю називаються алгоритмами з поліноміальним часом

Алгоритми, складність яких дорівнює О(tf(n)), де t – константа, більша, ніж 1, a f(n) – деяка поліноміальна функція від n, називаються експоненціальними. Підмножина експоненційних алгоритмів, складність яких дорівнює О(сf(n)), де де - константа, a f(n) зростає швидше, ніж постійна, але повільніше, ніж лінійна функція, називається суперполіноміальним.

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

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

Що це і хто створив

Алан Т'юрінг прагнув описати найбільш примітивну модель механічного пристрою, яка мала б ті самі основні можливості, що й комп'ютер. Т'юрінг вперше описав машину в 1936 році у статті "Про обчислювані числа з додатком до проблеми вирішності", яка з'явилася в Працях Лондонського математичного товариства.

Машина Тьюринга є обчислювальним пристроєм, що складається з головки читання/запису (або сканера) з паперовою стрічкою, що проходить через нього. Стрічка розділена на квадрати, кожен із яких несе одиночний символ - "0" або "1". Призначення механізму у тому, що і як засіб для входу і виходу, як і робоча пам'ять зберігання результатів проміжних етапів обчислень.

З чого складається пристрій

Кожна така машина складається із двох складових:

1. Необмежена стрічка. Вона є нескінченною в обидві сторони та поділена на осередки.
2. Автомат – керована програма, головка-сканер для зчитування та запису даних. Вона може знаходитися в кожний момент в одному з багатьох станів.

Кожна машина пов'язує два кінцеві ряди даних: алфавіт вхідних символів A = (a0, a1, ..., am) та алфавіт станів Q = (q0, q1, ..., qp). Стан q0 називають пасивним. Вважається, що пристрій закінчує роботу, коли потрапляє саме на нього. Стан q1 називають початковим – машина починає свої обчислення, перебуваючи на старті в ньому. Вхідне слово розміщується на стрічці по одній літері поспіль у кожній позиції. З обох боків від нього розташовуються лише порожні комірки.

Як працює механізм

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

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

Властивості механізму

Машина Тьюринга, як та інші обчислювальні системи, має властиві їй особливості, і вони подібні до властивостей алгоритмів:

1. Дискретність. Цифрова машина переходить до наступного кроку n+1 лише після того, як буде виконано попередній. Кожен виконаний етап призначає яким буде n+1.
2. Зрозумілість. Пристрій виконує лише одну дію для одного ж осередку. Воно вписує символ з алфавіту і робить один рух: ліворуч чи праворуч.
3. Детермінованість. Кожній позиції у механізмі відповідає єдиний варіант виконання заданої схеми, і кожному етапі дії і послідовність їх виконання однозначні.
4. Результативність. Точний результат для кожного етапу визначає машина Тюрінга. Програма виконує алгоритм і за кінцеве число кроків перетворюється на стан q0.
5. Масовість. Кожен пристрій визначено над допустимими словами, що входять до алфавіту.

Функції машини Тюрінга

У вирішенні алгоритмів часто потрібна реалізація функції. Залежно від можливості написання ланцюжка для обчислення, функцію називають алгоритмічно розв'язною або нерозв'язною. Як безліч натуральних або раціональних чисел, слів в кінцевому алфавіті N для машини розглядається послідовність множини - слова в рамках двійкового кодового алфавіту В = (0.1). Також результат обчислення враховується «невизначене» значення, що виникає при «зависанні» алгоритму. Для реалізації функції важлива наявність формальної мови в кінцевому алфавіті та вирішуваність задачі розпізнавання коректних описів.

Програма для влаштування

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

складники для обчислень

Щоб побудувати машину Тьюринга для вирішення однієї певної задачі, необхідно визначити наступні параметри.

Зовнішній алфавіт. Це кілька кінцевих безліч символів, що позначаються знаком А, складові елементи якого називаються буквами. Один з них – а0 – має бути порожнім. Наприклад, алфавіту пристрою Тьюринга, що працює з двійковими числами, виглядає так: A = (0, 1, а0).

Безперервна ланцюжок букв-символів, що записується на стрічку, називається словом.

Автомат називається пристрій, який працює без втручання людей. У машині Тьюринга він має для вирішення завдань кілька різних станів і за умов, що виникають, переміщається з одного положення в інше. Сукупність таких станів каретки є внутрішнім алфавітом. Він має літерне позначеннявиду Q = (q1, q2 ...). Одне з таких положень – q1 – має бути початковим, тобто тим, що запускає програму. Ще одним необхідним елементом є стан q0, який є кінцевим, тобто тим, що завершує програму та переводить пристрій у позицію зупинки.

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

Алгоритм для автомата

Кареткою пристрою Т'юрінга під час роботи керує програма, яка під час кожного кроку виконує послідовність наступних дій:

1. Запис символу зовнішнього алфавіту на позицію, зокрема і порожнього, здійснюючи заміну що був у ній, зокрема і порожнього, елемента.
2. Переміщення на один крок-комірку вліво або вправо.
3. Зміна власного внутрішнього стану.

Таким чином, при написанні програм для кожної пари символів або положень необхідно точно описати три параметри: ai - елемент з вибраного алфавіту A, напрямок зсуву каретки ("←" вліво, "→" вправо, "точка" - відсутність переміщення) і qk - новий стан пристрою. Наприклад, команда 1 "←” q 2 має значення "замістити символ на 1, зрушити головку каретки вліво однією крок-комірку і зробити перехід у стан q 2 ”.

Машина Тюрінга: приклади

приклад 1.Дана задача побудувати алгоритм, що додає одиницю до останньої цифри заданого числа, розташованого на стрічці. Вхідні дані – слово – цифри цілого десяткового числа, записані у послідовні осередки на стрічку. У початковий момент пристрій розташовується напроти самого правого символу - цифри числа.

Рішення. Якщо остання цифра дорівнює 9, то її потрібно замінити на 0 і потім додати одиницю до попереднього символу. Програма в цьому випадку для пристрою Тьюринга може бути написана так:

Тут q1 – стан зміни цифри, q0 – зупинка. Якщо q 1 автомат фіксує елемент з ряду 0..8, він заміщає її на один з 1..9 відповідно і потім переключається в стан q 0 , тобто пристрій зупиняється. Якщо ж каретка фіксує число 9, то заміщає її на 0, потім переміщається вліво, зупиняючись у стані q 1 . Такий рух триває до того моменту, поки пристрій не зафіксує цифру, меншу за 9. Якщо всі символи виявилися рівними 9, вони заміщаються нулями, на місці старшого елемента запишеться 0, каретка переміститься вліво і запише 1 у порожню клітку. Наступним кроком буде перехід у стан q0 - зупинка.

приклад 2.Даний ряд із символів, що позначають дужки, що відкривають і закривають. Потрібно побудувати пристрій Тьюринга, який би видаляти пари взаємних дужок, тобто елементів, розташованих поспіль - “()”. Наприклад, вихідні дані: “) (() (()”, відповідь має бути такою: “) . . . ((”. Рішення: механізм, перебуваючи в q 1 , аналізує крайній ліворуч елемент у рядку).

Стан q 1: якщо зустрінуто символ “(”, то здійснити зрушення вправо та перехід у положення q 2 ; якщо визначено “a 0 ”, то зупинка.

Стан q 2: проводиться аналіз дужки "(" на наявність парності, у разі збігу має вийти ")". Якщо елемент парний, зробити повернення каретки вліво і перейти в q 3 .

Стан q 3: здійснити видалення спочатку символу “(”, потім “)” і перейти в q 1 .

Один із найважливіших питань сучасної інформатики — чи існує формальний виконавець, за допомогою якого можна імітувати будь-якого формального виконавця. у відповідь це питання було отримано майже одночасно двома видатними вченими — А. Тьюрингом і Еге. Постом. Запропоновані ними виконавці відрізнялися один від одного, але виявилося, що вони можуть імітувати один одного, а головне імітувати роботу будь-якого формального виконавця.

Що таке формальний виконавець? Що означає – один формальний виконавець імітує роботу іншого формального виконавця? Якщо Ви грали в комп'ютерні ігри— на екрані об'єкти беззаперечно підпорядковуються командам гравця. Кожен об'єкт має набір допустимих команд. У той самий час комп'ютер сам є виконавцем, причому віртуальним, а реальним. Отож виходить, що один формальний виконавець імітує роботу іншого формального виконавця.

Розглянемо роботу машини Тьюринга.

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

Таким чином Машина Тьюринга формально описується набором двох алфавітів:

A = (a1, a2, a3, ..., an) - зовнішній алфавіт, служить для запису вихідних даних

Q = (q1, q2, q3, ..., qm) - Внутрішній алфавіт, визначає набір станів зчитуюче-друкарського пристрою.

Кожен осередок стрічки може містити символ із зовнішнього алфавіту A = (a0,a1,…,an) (У нашому випадку A=(0, 1))

Допустимі дії Машини Тьюринга такі:

1) записати будь-який символ зовнішнього алфавіту в осередок стрічки (символ, що був там до того, затирається)

2) зміститися до сусіднього осередку

3) змінити стан на один із позначених символом внутрішнього алфавіту Q

Машина Т'юрінга - це автомат, який управляється таблицею.

Рядки в таблиці відповідають символам вибраного алфавіту A, а стовпці - станам автомата Q = (q0, q1, ..., qm). На початку роботи машина Т'юрінга знаходиться в стані q1. Стан q0 це кінцевий стан, потрапивши в нього, автомат закінчує роботу.

У кожній клітині таблиці, що відповідає деякому символу ai та деякому стану qj, знаходиться команда, що складається з трьох частин
· символ з алфавіту A
· Напрямок переміщення: «>» (вправо), «<» (влево) или «.» (на месте)
· Новий стан автомата

У наведеній вище таблиці алфавіт A = (0, 1, _) (містить 3 символи), а внутрішній алфавіт Q = (q1, q2, q3, q4, q0), q0 - стан, що змушує каретку зупинитися.

Розглянемо кілька завдань розв'язком. Завантажити машину Т'юрінга Ви можете на сайті в розділі .

Завдання 1. Нехай A = (0, 1, _). На стрічці в осередках знаходяться символи з алфавіту в наступному порядку 0011011. Каретка знаходиться над першим символом. Необхідно скласти програму, яка замінить 0 на 1, 1 на 0 і поверне каретку до початкового положення.

Тепер визначимося зі станами каретки. Я називаю їх – «бажання каретки щось зробити».

q1) Каретка повинна піти праворуч: якщо бачить 0 змінює його на 1 і залишається в стані q1, якщо бачить 1 — змінює його на 0 і залишається в стані q1, якщо бачить _ — повертається назад на 1 осередок «бажає щось інше» , тобто перетворюється на стан q2. Запишемо наші міркування до таблиці виконавця. Синтаксис дивіться у довідці до програми)

q2) Тепер опишемо «бажання каретки» q2. Ми маємо повернутися в початкове становище. Для цього: якщо бачимо 1 залишаємо її і залишаємося в стані q2 (з тим самим бажанням дійти до кінця ряду символів); якщо бачимо 0 - залишаємо його і продовжуємо рухатися вліво в стані q2; бачимо _ - Зсувається вправо на 1 осередок. Ось ви опинилися там, де потрібна умова завдання. переходимо у стан q0.

Переглянути роботу програми можна на відео:

Завдання 2. Дано: кінцева послідовність 0 та 1 (001101011101). Необхідно виписати їх після даної послідовності, через порожню комірку, а в даній послідовності замінити їх на 0. Наприклад:

З 001101011101 отримаємо 00000000000 1111111.

Як бачите, сім одиниць записалися після цієї послідовності, але в їх місцях стоять нулики.

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

q1) побачив 1 - виправи на нолик і перейди в інший стан q2 (новий стан вводиться, щоб каретка не змінила на нулі всі одиниці за один прохід)

q2) нічого не змінювати, рухатися до кінця послідовності

q3) як тільки каретка побачила порожню комірку, вона робить крок праворуч і малює одиничку, якщо вона бачить одиничку — то рухається далі, щоб підписати символ у кінці. Як тільки намалював одиницю, переходимо у стан q4

q4) проходимо по написаних одиницях, нічого не змінюючи. Як тільки доходимо до порожнього осередку, що розділяє послідовність від одиниць, переходимо з нового стану q5

q5) у цьому стані йдемо початок послідовності, нічого не змінюючи. Доходимо до порожнього осередку, розвертаємось і переходимо в стан q1

Стан q0 каретка прийме в тому випадку, коли вона пройде в стані q1 до кінця цієї послідовності і зустріне порожню комірку.

Отримаємо таку програму:

Роботу Машини Тюрінга можете переглянути на відео нижче.

Машина Тюрінга (МТ)- Абстрактний виконавець (абстрактна обчислювальна машина). Була запропонована Аланом Тюрінгом в 1936 році для формалізації поняття алгоритму.

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

Тобто будь-який інтуїтивний алгоритм може бути реалізований за допомогою деякої машини Тьюринга.

Енциклопедичний YouTube

1 / 5

✪ 09 - Введення у алгоритми. Машина Тюрінга

✪ Машина Тюрінга - Олександр Шень

✪ Лекція 20: Машина Тюрінга

✪ Машина Тюрінга. Приклад роботи

✪ 16 - Обчислюваність. Машини Тюрінга. Мотивування та приклади

Субтитри

Пристрій машини Тюрінга

До складу машини Тюрінга входить необмежена в обидва боки стрічка(можливі машини Т'юрінга, які мають кілька нескінченних стрічок), розділена на осередки , і керуючий пристрій(також називається головкою запису-читання (ГЗЛ)), здатне перебувати в одному з безлічі станів. Число можливих станів пристрою, що управляє, звичайно і точно задано.

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

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

Машина Тюрінга називається детермінованою, якщо кожній комбінації стану та стрічкового символу в таблиці відповідає не більше одного правила. Якщо існує пара «стрічковий символ - стан», для якої існує 2 і більше команд, така машина Т'юрінга називається недетермінованою.

Опис машини Тюрінга

Конкретна машина Тьюринга задається перерахуванням елементів множини літер алфавіту A, множини станів Q і набором правил, якими працює машина. Вони мають вигляд: qiaj →q i1 a j1 dk (якщо головка знаходиться в стані qi , а в осередку записана буква aj , то головка переходить у стан q i1 , в комірку замість aj записується a j1 , головка робить рух dk , яке має три варіанти: на комірку ліворуч (L), на комірку праворуч (R), залишитися на місці (N)). Для кожної можливої ​​конфігурації є одно правило (для недетермінованої машини Тьюринга може бути більша кількість правил). Правил немає тільки для заключного стану, потрапивши до якого машина зупиняється. Крім того, необхідно вказати кінцевий та початковий стани, початкову конфігурацію на стрічці та розташування головки машини.

Приклад машини Тюрінга

Наведемо приклад МТ для множення чисел в унарній системі обчислення . Запис правила «qiaj →q i1 a j1 R/L/N» слід розуміти так: qi - стан при якому виконується це правило, aj - дані в осередку, в якому знаходиться головка, q i1 - стан, в який потрібно перейти, a j1 - що потрібно записати в комірку, R/L/N – команда на переміщення.

Машина працює за наступним набором правил:

	q 0	q 1	q 2	q 3	q 4	q 5	q 6	q 7	q 8
1	q 0 1→q 0 1R	q 1 1→q 2 aR	q 2 1→q 2 1L	q 3 1 → q 4 aR	q 4 1→q 4 1R			q 7 1→q 2 aR
×	q 0 ×→q 1 ×R		q 2 ×→q 3 ×L		q 4 ×→q 4 ×R		q 6 ×→q 7 ×R		q 8 ×→q 9 ×N
=			q 2 =→q 2 =L		q 4 =→q 4 =R			q 7 =→q 8 =L
a			q 2 a→q 2 aL	q 3 a→q 3 aL	q 4 a→q 4 aR		q 6 a→q 6 1R	q 7 a→q 7 aR	q 8 a→q 8 1L
*	q 0 *→q 0 *R			q 3 *→q 6 *R	q 4 *→q 5 1R
						q 5 →q 2 *L

Опис станів:

початок
q 0	початковий стан. Шукаємо "x" праворуч. При знаходженні переходимо у стан q1
q 1	замінюємо "1" на "а" і переходимо в стан q2
Переносимо всі «1» з першого числа на результат
q 2	шукаємо "х" зліва. При знаходженні переходимо у стан q3
q 3	шукаємо "1" зліва, замінюємо її на "а" і переходимо в стан q4. Якщо «1» закінчилися, знаходимо «*» і переходимо в стан q6
q 4	переходимо в кінець (шукаємо "*" праворуч), замінюємо "*" на "1" і переходимо в стан q5
q 5	додаємо «*» в кінець і переходимо в стан q2
Обробляємо кожен розряд другого числа
q 6	шукаємо «х» праворуч і переходимо у стан q7. Поки що шукаємо замінюємо «а» на «1»
q 7	шукаємо «1» або «=» праворуч при знаходженні «1» замінюємо його на «а» та переходимо в стан q2 при знаходженні "=" переходимо в стан q8
Кінець
q 8	шукаємо "х" зліва. При знаходженні переходимо у стан q9. Поки що шукаємо замінюємо «а» на «1»
q 9	термінальний стан (зупинка алгоритму)

Помножимо за допомогою МТ 3 на 2 одиничній системі. У протоколі вказано початковий та кінцевий стан МТ, початкова конфігурація на стрічці та розташування головки машини (підкреслений символ).

Початок. Перебуваємо у стані q 0 , ввели в машину дані: *111x11=*, головка машини розташовується першому символі *.

1-й крок. Дивимося по таблиці правил що робити машина, перебуваючи у стані q 0 і над символом «*». Це правило з 1-го стовпця 5-го рядка - q0*→q0*R. Це означає, що ми переходимо в стан q 0 (тобто не міняємо його), символ стане «*» (тобто не зміниться) і зміщуємося за введеним текстом «*111x11=*» вправо на одну позицію (R), то є на 1-й символ 1. У свою чергу стан q 0 1 (1-й стовпець 1-й рядок) обробляється правилом q 0 1→q 0 1R. Тобто знову відбувається просто перехід праворуч на 1 позицію. Так відбувається, доки ми не станемо на символ «х». І так далі: беремо стан (індекс при q), беремо символ, на якому стоїмо (підкреслений символ), з'єднуємо їх та дивимося обробку отриманої комбінації за таблицею правил.

Простими словами, алгоритм множення наступний: помічаємо 1 одиницю 2-го множника, замінюючи її на букву «а», і переносимо весь 1-й множник за знак рівності. Перенесення проводиться шляхом чергової заміни одиниць одного множника на «а» і дописування такої кількості одиниць в кінці рядка (ліворуч від крайнього правого «*»). Потім міняємо всі "а" до знака множення "х" назад на одиниці. І цикл повторюється. Справді, адже A помножити на можна уявити як А+А+А В раз. Помічаємо тепер 2 одиницю 2-го множника літерою «а» і знову переносимо одиниці. Коли до знака «=» не виявиться одиниць – значить множення завершено.

Повнота по Тюрінгу

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

Елементарність дій полягає в тому, що дія змінює лише невеликий шматочок даних у пам'яті (у випадку машини Тьюринга – лише один осередок), і число можливих дій звичайно. Незважаючи на простоту машини Т'юрінга, на ній можна обчислити все, що можна обчислити на будь-якій іншій машині, що здійснює обчислення за допомогою послідовності елементарних дій. Ця властивість називається повнотою.

Один із природних способів доказу того, що алгоритми обчислення, які можна реалізувати на одній машині, можна реалізувати і на іншій, - це імітація першої машини на другий.

Імітація полягає у наступному. На вхід другої машини подається опис програми (правил роботи) першої машини D (\displaystyle D)та вхідні дані X (\displaystyle X), які повинні були надійти на вхід першої машини Потрібно описати таку програму (правила роботи другої машини), щоб у результаті обчислень на виході виявилося те саме, що повернула б перша машина, якби отримала на вхід дані X (\displaystyle X).

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

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

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

Варіанти машини Тюрінга

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

Машина Т'юрінга, що працює на напівнескінченній стрічці

Як приклад такого відомості розглянемо таку теорему: Для будь-якої машини Т'юрінга існує еквівалентна машина Т'юрінга, що працює на напівнескінченній стрічці (тобто на стрічці, нескінченній в один бік).

Розглянемо підтвердження, наведене Ю. Р. Карповим у книзі «Теорія автоматів». Доказ цієї теореми конструктивний, тобто ми дамо алгоритм, яким для будь-якої машини Тьюринга може бути побудована еквівалентна машина Тьюринга з оголошеною властивістю. По-перше, довільно занумеруємо осередки робочої стрічки МТ, тобто визначимо нове розташування інформації на стрічці:

Потім перенумеруємо осередки, причому вважатимемо, що символ «*» не міститься у словнику МТ:

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

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

Двовимірні машини Тюрінга

• Мураха Ленгтона

Див. також

• JFLAP кроссплатформенна програма симулятор автоматів, машини Тюрінга, граматик, малює граф автомата