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

Машина Тьюринга - одне з найбільш інтригуючих і захоплюючих інтелектуальних відкриттів 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, напрямок зсуву каретки ("larr-" вліво, "-" вправо, "точка" - відсутність переміщення) і qk - новий стан пристрою. Наприклад, команда 1 "larr-" q2 має значення "замістити символ на 1, зрушити голівку каретки вліво на один крок-клітинку і зробити перехід в стан q2".

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

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



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

a00123...789
q11 H q01 H q02 H q03 H q04 H q0...8 H q09 H q00 lambda- q1

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

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

a0()
q1a0 H q0(П q2) П q1
q2a0 H q0(П q2) lambda- q3
q3a0 H q0a0 П q3a0 П q1

Стан q1: Якщо зустрінутий символ "(", то здійснити зрушення вправо і перехід в положення q2- якщо визначений "a0", То зупинка.

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

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



Оцініть, будь ласка статтю
Всього голосів: 31

Увага, тільки СЬОГОДНІ!