Приклади машин Тьюринга - студопедія

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

Приклад 1. Побудувати машину Тьюринга, яка обчислює функцію.

Нехай алфавіт машини Тьюринга складається з двох символів, де 0 - порожній символ, а 1 - символ використаної клітинки. У цьому алфавіті будь-яке ціле невід'ємне число k представляється k + 1 символами 1, записаними в сусідніх осередках стрічки. У цьому випадку число 0 буде записано так ... 010 ...

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

Програма роботи машини Тьюринга, що обчислює функцію. має вигляд:

- видалена одна зайнята осередок аргументу.

- Новомосковскются зайняті осередки аргументу.

- знайдена розділяє порожня клітинка.

- Новомосковскются зайняті осередки результату.

- заповнена одна порожня клітинка результату.

- заповнена друга осередок результату.

- проглядаються в зворотному порядку зайняті осередки результату.

- знайдена порожня розділяє осередок.

- знайдена друга порожня клітинка.

- знову Новомосковскется порожня розділова осередок.

- видаляється один зайнятий символ. Кінець.

- знайдена зайнята осередок аргументу.

- проглядаються в зворотному порядку зайняті осередки аргументу.

- знайдена порожня клітинка перед зайнятими осередками аргументу.

Приклад 2. Побудувати машину Тьюринга, яка застосовується до всіх слів в алфавіті a, b> і переводить їх в слово. Перевірити роботу побудованої машини над деякими словами.

Рішення. Опишемо роботу алгоритму, вирішального цю задачу. Спочатку за допомогою команд. проходимо до кінця слова, не змінюючи його символів. Ознакою закінчення слова будемо зчитування символу в стані.

За допомогою команд. . рухаємося вліво, не змінюючи останнього символу.

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

Якщо в стані зчитується символ. значить, вся робота виконана, і пора зупинятися за допомогою команди.

Якщо в стані зчитуємо символ b. значить,. треба все символи, крім. замінити буквами b. Це робимо за допомогою команд. . .

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

Перевіримо роботу побудованої машини Тьюринга над словом abba:

У слові bbaaa передостанній символ - a. і всі букви вихідного слова, крім останнього, замінені порожніми символами.

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

У наведених прикладах показана реалізація на машинах Тьюринга основних властивостей алгоритму: дискретності, детермінованості, масовості і результативності.

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

Композицією машин Тьюринга М1 і М2 називається машина Тьюринга М. яка спочатку функціонує як машина Тьюринга М1. заключне стан якої q0 змінюють на початковий стан машини Тьюринга М2. І далі машина М функціонує як машина Тьюринга М2.

Композицію машин Тьюринга позначають: М = М1 º М2.

Так, якщо необхідно побудувати машину Тьюринга, яка обчислює функцію ƒ (х, у) = х + у + 1, то досить виконати композицію машин Тьюринга. Нехай машина М1 обчислює функцію ƒ (х) = х + 1, а машина М2 обчислює функцію ƒ (х + у). Тоді машина М = М1 º М2 буде обчислювати, очевидно, функцію ƒ (х, у) = х + у + 1. Для цього потрібно до програми, яка описує машину М1. приєднати команди машини М2. Стану машини М1 будуть також станами машини М. Заключне стан q0 машини М1 слід замінити станом q2, яке буде відповідати початкового стану машини М2. тоді зміниться відповідним чином нумерація станів машини М2. стан q1 зміниться на стан q2 машини М. стан q2 зміниться на стан q3 і так далі.

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

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

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

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

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