Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Машина Тьюринга



План:

Література

Введення

абстрактна схема машини Тьюринга

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

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


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

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

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

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

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


2. Опис машини Тьюринга

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


3. Приклад машини Тьюринга

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

Набір правил Набір правил
q 0 * → q 0 * R q 4 a → q 4 aR
q 0 1 → q 0 1R q 4 = → q 4 = R
q 0 → q 1 R q 1 квітня → q 4 1R
q 1 січня → q 2 aR q 4 * → q 5 1R
q 1 лютого → q 2 1L q 5 * → q 2 * L
q 2 a → q 2 aL q 6 a → q 6 1R
q 2 = → q 2 = L q 6 → q 7 R
q 2 → q 3 L q 7 a → q 7 aR
q 3 січня → q 4 aR q 1 липні → q 2 aR
q 3 a → q 3 aL q 7 = → q 8 = L
q 3 * → q 6 * R q 8 a → q 8 1L
q 4 → q 4 R q 8 → q 9 H

Помножимо за допомогою МТ 3 на 2 в одиничною системі:

Протокол

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


4. Повнота по Тьюрингу

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

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

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

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

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

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

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


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

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

5.1. Машина Тьюринга, що працює на полубесконечной стрічці

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

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

Mt1.jpg

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

Mt2.jpg

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

Mt3.jpg

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


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

Інші абстрактні виконавці та формальні системи обчислень


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Універсальна машина Тьюринга
Імовірнісна машина Тьюринга
Недетермінірованним машина Тьюринга
Квантова машина Тьюринга
Тест Тьюринга
Теза Черча - Тьюринга
Машина
Слот-машина
Посудомоечная машина
© Усі права захищені
написати до нас