Машина Тьюринга
Машина Т'юрінга. Завдання та рішення
Одне з найважливіших питань сучасної інформатики — чи існує формальний виконавець, за допомогою якого можна імітувати будь-якого формального виконавця. відповідь на це питання було отримано майже одночасно двома видатними вченими - А. Т'юрінгом та Е. Постом. Запропоновані ними виконавці відрізнялися один від одного, але виявилося, що вони можуть імітувати один одного, а головне імітувати роботу будь-якого формального виконавця.
Що таке формальний виконавець? Що означає один формальний виконавець імітує роботу іншого формального виконавця? Якщо Ви грали в комп'ютерні ігри - на екрані об'єкти беззаперечно підкоряються командам гравця. Кожен об'єкт має набір допустимих команд. У той самий час комп'ютер сам є виконавцем, причому віртуальним, а реальним. Ось і виходить, що один формальний виконавець імітує роботу іншого формального виконавця.
Розглянемо роботу машини Тьюринга.
Машина Тьюринга являє собою нескінченну стрічку, поділену на комірки, і каретку (пристрій, що зчитує-друкує), яка рухається вздовж стрічки.
Таким чином Машина Тьюринга формально описується набором двох алфавітів:
A = - зовнішній алфавіт, служить для запису вихідних даних
Q= - Внутрішній алфавіт, описує набір станів зчитувально-друкарського пристрою.
Кожна комірка стрічки може містити символ із зовнішнього алфавіту A = (У нашому випадку A =)
Допустимі дії Машини Тьюринга такі:
1) записати будь-який символ зовнішнього алфавіту в комірку стрічки (символ, що був там до того, затирається)
2) зміститися в сусідній осередок
3) змінити стан на один із позначених символомвнутрішнього алфавіту Q
Машина Тьюринга – це автомат, який керується таблицею.
Рядки в таблиці відповідають символам вибраного алфавіту A, а стовпці станам автомата Q = . На початку роботи машина Тьюринга перебуває у стані q1. Стан q0 - це кінцевий стан, потрапивши до нього, автомат закінчує роботу.