Формальне визначення алгоритму

Автор: Петрова О.О. Лабораторний практикум "Дослідження роботи машини Тьюринга", изданного в 2016 году в Харьковском национальном университете строительства и архитектуры, рекомендован к печати в мае 2015, регистрационный номер библиотеки ХНУСА № 1316

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

Така модель алгоритму була запропонована англійським математиком, логіком, інженером Аланом Тьюрингом у кінці 30 –х років минулого століття, що майже на два десятиліття випередило появу ЕОМ і послужило їх теоретичним прообразом.

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

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

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

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

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

Довести тезу Тьюринга неможливо, так як у його формулюванні не визначено поняття «будь – який алгоритм». Його можна тільки обґрунтувати, подаючи різні алгоритми у вигляді машин Тьюринга. Було доведено, що клас функцій, обчислювальних на цих машинах, збігається з класом частково рекурсивних функцій.

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

 

МОДЕЛЮВАННЯ РОБОТИ МТ

 

Структура МТ

 

Алгоритмічний процес – це робота, виконувана деякою «абстрактною обчислювальною машиною». Кожна окрема МТ здатна виконувати тільки один алгоритм, для визначення якого можна користуватись терміном «програма МТ» – набір інструкцій, які спрощені до однотипної схеми. Всі МТ відрізняються за своїми програмами [4, 5].

МТ можна класифікувати наступним чином (рис. 1)

 

	МАШИНИ ТЬЮРИНГА

 

 

по відношенню до випадковості

			Недетерміновані		Імовірнісні

 

 

 

за кількістю стрічок

 

 

 

за властивостями стрічки

		Стрічки нескінченні в обидва боки
	Стрічки нескінченні тільки вправо

 

 

 

Рисунок 1 – Схема класифікації МТ

 

Моделлю процесу обчислення служить детермінована однострічкова машина Тьюринга (ДМТ), яка схематично зображена на рисунку 2.

 

 

	Алфавіт A={a1, a2,….am}				Програма управління
	Стани Q={q1, q2,….qn}

 

 

 

Рисунок 2 – Схематичне зображення детермінованої однострічкової машини Тьюринга

 

ДТМ складається з управляючого пристрою з кінцевим числом станів, головки, яка може зчитувати та записувати символи, та необмеженої в обидва боки стрічки, яка розділена на нескінченне число одинакових клітин, пронумерованих цілими числами: ……, – 2, – 1, 0, 1, 2, 3….

Інформаційна стрічка нескінченної довжини являє собою послідовність клітин, в кожну з яких записаний тільки один символ із множини символів алфавіту: A={a₁, a₂,…,a_m}. Послідовність символів на стрічці формує слово. Пробіл між словами також є символом множини А, наприклад, # ∈ A. У формальних граматиках множину A називають множиною термінальних символів. Інформаційна стрічка виконує функції зовнішньої пам'яті МТ.

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

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

Управляючий пристрій являє собою механізм, який на кожному кроці обчислення знаходиться в одній із множин станів: Q = {q₁, q₂,…, q_n}. Залежно від стану q_i та считаного символу a_j управляючий пристрій надає команду на стирання або запис символу в клітинку, що оглядається, переводу управляючого пристрою в новий стан і переміщення головки на сусідню клітинку інформаційної стрічки. Тому стани управляючого пристрою називають «пам'яттю машини Тьюринга», так як машина пам'ятає всі проміжні стани, які перевели її зі стану q₀ в стан q_i. Із позиції формальних граматик множина символів, які описують стани управляючого пристрою, є множиною нетермінальних символів. Серед усіх станів управляючого пристрою слід виділити два: q_o – початковий стан («старт») і q_k – кінцевий стан («стоп») (у даному випадку під k розуміється не числова змінна, а мнемонічний знак кінця), що полегшує складання протоколів машин Тьюринга, а також композицію декількох МТ. Для опису переміщень головки відносно інформаційної стрічки вводиться додатковий алфавіт: D={П, Л, С}, де П – означає переміщення головки вправо на одну клітинку інформаційної стрічки, Л – вліво на одну клітинку та С – зупинка переміщення головки.

МТ має в розпорядженні кінцеве число знаків (символів): a₁, a₂,…,a_m, що утворюють зовнішній алфавіт, в якому кодуються відомості, що подаються в машину, а також ті, які виробляються в ній. В МТ обробка інформації, як і в комп’ютері, виконується в логічному блоці, який може перебувати в одному з кінцевої кількості станів: q₁, q₂,…q_n. Блок має два вхідних канали: через один із них на кожній стадії роботи машини (в кожному такті) надходить знак з клітинки, яку оглядають, через інший – знак q_i того стану, який предписується блоку на даний такт. Через вихідний канал блок посилає в клітинку, яку оглядає, відповідний «перепрацьований» знак а_j, який є однозначною функцією від сигналів а_jq_i, поданих на вхід (рис. 3).

 

Зовнішня пам'ять

аj1

аj2

аjn

a(t)

a(t+1)

Схема управління зсувом

Логічний блок

q(t)

Q (внутрішня пам'ять)

q(t+1)

 

 

 

P(t+1)

 

Рисунок 3 – Обробка інформації в МТ

 

Логічний блок реалізує функцію, яка ставить у залежність кожній парі знаків: a_i, q_n (кількість таких пар складає k*m) трійку знаків: a_j,D, q_t. Таку логічну функцію зручно подавати у вигляді прямокутної таблиці, стовпчики якої занумеровані знаками стану, а рядки – знаками зовнішнього алфавіту. В кожній клітинці таблиці записано відповідну вихідну трійку знаків. Таку таблицю можна називати функціональною схемою машини [4].