Проблема уточнення поняття алгоритму. Машина Тьюрінга.

⇐ ПредыдущаяСтр 6 из 7Следующая ⇒

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

Розвиток математики нечислових об'єктів у другій половині 18 століття (виникнення неевклідових геометрій, абстрактних алгебраїчних теорій) підвищило вимоги до строгості математичних міркувань. Створення Г. Кантором теорії множин явилося одною з вирішальних обставин, що привели до перегляду основ математики, тобто, принципів, що лежать в основі математичних міркувань. Парадокси, виявлені в основах математики на початку 20 століття, зажадали точного вивчення принципів математичних міркувань (які досі здавалися інтуїтивно ясними) математичними ж засобами. Поняття алгоритму саме стало об'єктом математичного дослідження і тому повинно було мати точне означення. Крім того, до цього примушував розвиток фізики і техніки, що швидко наближав початок ери ЕОМ.

У інтуїтивному означенні сформульовані основні вимоги до алгоритмів. Однак, поняття, використані в цих формулюваннях самі мають потребу в уточненні. Наприклад, простий аналіз опису процесу знаходження НСД двох цілих невідємних чисел показує необхідність уточнити майже всі характеристики алгоритму: дані і форму їхнього представлення (чи можна вважати даними і ?), елементарність кроку (крок 1 явно неелементарний). Тільки дві вимоги виконані в достатній мірі (вони і створюють враження ясності): результативність і детермінованість.

Багато алгоритмічних проблем розв’язувалися шляхом указівки конкретних розв’язувальних процесів. На початку 20століття виникли такі алгоритмічні проблеми, існування позитивного розв’язку яких було сумнівним. Довести ж неіснування алгоритму, користуючись інтуїтивним означенням, неможливо, необхідно було мати точне означення алгоритму. У 20-х роках 20 століття задача точного означення поняття алгоритму стала однією з центральних проблем математики. Розв’язок її було отримано в 1936-1937р. у роботах Давіда Гільберта, Курта Геделя, Алонсо Черча, Еміля Поста, Алана Тьюрінга та ін. Один з підходів до точного означення алгоритму заснований на уявленні про алгоритмічний процес, як про процес, який може здійснювати придатно влаштована „машина”. Основною теоретичною моделлю цього типу є машина, незалежно побудована Постом в 1936 р. і Тьюрінгом у 1937 р.

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

Змістовне означення МТ: МТ складають такі частини:

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

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

3. Голівка, що зчитує і пише – пристрій звернення до стрічки, який в кожен момент часу оглядає комірку стрічки, у залежності від символу в цій комірці і стану керуючого пристрою записує у комірку символ або стирає його (записує ), зсувається на комірку вправо чи вліво або залишається на місці; при цьому керуючий пристрій переходить у новий стан (або залишається в старому).

Дані машини Тьюрінга - це слова в алфавіті стрічки; на стрічці записуються і вихідні дані, і результати.

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

Детермінованість машини Тьюрінга, тобто послідовність її кроків, задається програмою. Програма складається з команд. Команда має наступний вигляд:

, (1)

де - однозначно задані внутрішній стан і символ на скінченій стрічці;

- наступний внутрішній стан;

- символ, якій потрібно записати замість у ту ж саму комірку

(стирання символу розуміється як запис порожнього символу ).

- напрямок зсуву голівки, який позначається одним з трьох символів: - вправо, – уліво, – на місці.

Програму машини Тьюрінга часто задають у вигляді таблиці, рядкам якої відповідають внутрішні стани, стовпцям – символи на скінченій стрічці, а на перетині рядка і стовпця записана трійка (права частина команди (1)).


... ...	... ...

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

Програму можна також задати блок-схемою, яка називається діаграмою переходів. Діаграма переходів – це орієнтований граф, вершинам якого відповідають внутрішні стани, а ребру; яке йде з вершини у вершину відповідає правило вигляду (1). Ребро надписується .

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

Повний стан МТ, за яким однозначно визначається її подальша поведінка визначається:

1) станом стрічки, тобто словом ;

2) внутрішнім станом ;

3) положенням голівки, що зчитує, на стрічці, тобто номером комірки , яка оглядається .

Сукупність усіх цих даних можна записати одним словом:

(2)

Повний стан називається конфігурацією МТ або машинним словом. Для стислості конфігурацію (2) позначають трійкою

: ( )

де і - слова в алфавіті A, - поточний внутрішній стан, причому ліворуч від і праворуч від немає непорожніх символів.

Конфігурація вигляду називається стандартною початковою (голівка оглядає крайній лівий символ, записаний на стрічці). Конфігурація вигляду називається стандартною заключною. До всякої незаключної конфігурації машини застосовна точно одна команда вигляду (1), яка переводить в . Це позначається так: .

Формальне означення машини Тьюрінга. Машина Тьюрінга вважається заданою, якщо заданий набір , де A – зовнішній алфавіт, Q – внутрішній алфавіт, P – програма, - початковий стан, - заключний стан, - символ порожньої комірки.