Современные информационные технологии.

2. Вычислительная техника и программирование

Морозов М.С.

Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»

ПРИНЦИП РОБОТИ МАШИНИ ТЮРІНГА

Формальні визначення алгоритму з'явилися в тридцятих-сорокових роках XX століття. Машина Тюрінга — це абстрактна машина (автомат), запропонована англійським математиком Аланом Тюрінгом для формального уточнення інтуїтивного поняття алгоритму. Інакше кажучи, Тюрінг формалізував правила виконання дій за допомогою опису роботи деякої конструкції [1]. Машиною Тюрінга називається п'ятірка об'єктів виду [2]:

T=(A,S,ν,δ,μ),

де A={a1,a2,…,an} — алфавіт;

S={s0,s1,…,sm} — множина внутрішніх станів, причому s0 — заключний, а s1 — початковий стани;

ν: A×S → A — функція виходу;

δ: A×S → S — функція переходу;

μ: A×S → {R, L, N} — функція управління.

Програмою машини Тюрінга є набір усіх її команд. Командою машини Тюрінга є запис виду [2]:

aksi → apDsj,

де a, D, s — значення функцій ν, μ, δ відповідно.

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

Робота машини Тюрінга над словом α, записаним на стрічці, відбувається наступним чином [1]:

• машина Тюрінга починає свою роботу завжди у стані s₁, а її зчитувальний пристрій розташований над першим зліва символом слова, записаного на стрічці;

• після читання символу у комірці, над яким розташований зчитувальний пристрій, вона друкує у цю комірку символ, що знайдений за допомогою функції виходу ν, рухається вздовж стрічки вправо, вліво чи залишається на місці, у випадку, якщо функція μ приймає значення R, L або N відповідно та переходить у стан, що визначається за допомогою функції переходу δ. У випадку переходу машини Тюрінга у стан s₀, вважають, що вона закінчила роботу над словом α і кажуть, що машина Тюрінга застосовна до слова α.

Кодом машини Тюрінга є запис набору її команд в алфавіті {*,1}, що дозволяє однозначно відновлювати кожну команду.

У нашому випадку числовою функцією називається функція виду:

Зображенням набору аргументів (x1,x2,…,xn) називається запис виду:

(1),

де 1^Z — послідовність із Z одиниць.

Числова функція f(x1,x2,…,xk) є обчислюваною за Тюрінгом, якщо існує машина Тюрінга, що застосовна до будь-якого слова виду (1), що переводить його в слово 1y+1, де y=f(x1,x2,…,xk).

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

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

Література:

1. Тишин В.В. Дискретная математика в примерах и задачах. – СПб.: БХВ-Петербург, 2012. – С. 163-178.

2. Карпов Ю. Г. Теория автоматов. – СПб.: Питер, 2003. – 208 с.

3. Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Глава 8. Введение в теорию машин Тьюринга // Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. – М.: «Вильямс», 2002. – С. 528.