Машина тьюринга: опис і приклади машин тьюринга

Машина Тьюринга - одне з найбільш інтригуючих і захоплюючих інтелектуальних відкриттів 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. Зміна свого внутрішнього стану.

Таким чином, при написанні програм для кожної пари символів або положень необхідно точно описати три параметра: a_i - елемент з обраного алфавіту A, напрямок зсуву каретки ( "larr;" вліво, ";" вправо, "точка" - відсутність переміщення) і q_k - новий стан пристрою. Наприклад, команда 1 "larr;" q₂ має значення "замістити символ на 1, зрушити голівку каретки вліво на один крок-осередок і зробити перехід в стан q₂".

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

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

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

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

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

стан q₁: Якщо зустрінутий символ "(", то зробити зрушення вправо і перехід в стан q₂- якщо визначено "a₀", То зупинка.

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

стан q₃: Здійснити видалення спочатку символу "(", а потім ")" і перейти в q₁.