Визначення алгоритму на основі абстрактних автоматів (машини Тьюринга)
Визначення алгоритму на основі рекурсивних функцій
Рекурсія - процес визначення функції, при якому її значення для довільних значень аргументів виражається відомим чином через значення функції для менших значень аргументів.
Функція, для якої існує алгоритм оцінки для будь-якого аргументу в області визначення функції, називається обчислюваною.
Функція, для якої існує ефективна процедура її обчислення на основі рекурсії, називається рекурсивної.
Клас рекурсивних функцій тотожний з класом всюди певних обчислюваних функцій - теза Черча.
Функція, певна не для всіх значень аргументів, а тільки на деякому підмножині, називається частковою функцією.
Всі часткові функції, обчислюваних за допомогою алгоритмів, є частково рекурсивними - теза Кліні.
Поняття частково рекурсивних функцій використовують для доказу алгоритмічної можливості розв'язання або нерозв'язності проблеми.
Алгоритмічні процеси - це процеси, які може здійснювати слушно влаштована «машина».
Під «машиною» в даному випадку мається на увазі деякий абстрактний, існуючий лише в уяві автомат.
У загальному випадку така машина складається з наступних частин:
- з необмеженою в обидві сторони інформаційної стрічки, розділеної на комірки, що представляє необмежену пам'ять машини. У кожному осередку можна зберігати тільки один символ, в тому числі і нуль;
- з головки читання / запису, уздовж якої може переміщатися стрічка;
- керуючого пристрою, який в кожен даний момент знаходиться в деякому «стані». Пристрій управління може перебувати в деякому кінцевому числі станів, якщо цей стан заключне, машина закінчує роботу.
Така машина може зрушувати стрічку на одну клітинку вліво або вправо, залишаючи вміст комірок незмінним, або може змінювати стан сприймається осередки, залишаючи стрічку нерухомою. Машина Тьюринга працює в довільному кінцевому алфавіті і виконує деякий кінцеве число наказів.
Машини Тьюринга є універсальних виконавців, з використанням яких можна імітувати все алгоритмічні процеси, описувані математиками. Було доведено, що клас функцій, обчислюваних на цих машинах, точно збігається з класом всіх частково рекурсивних функцій. Т.ч. питання про існування чи не існування алгоритму для задачі того чи іншого типу слід розуміти як питання про існування чи не існування машини Тьюринга, яка має за потрібне властивістю.
Інтуїтивне розуміння машини Тьюринга таке: має цикл стрічка, розділена на клітини. По клітинах їздить каретка. Прочитавши букву, записану в клітці, каретка рухається вправо, вліво або залишається на місці, при цьому буква замінюється новою. Деякі літери зупиняють каретку і завершують роботу.
Існує кілька способів запису алгоритмів, що відрізняються один від одного наочністю, компактністю, ступенем формалізації. Найбільшого поширення набули: словесний, графічний, програмний.
Графічний спосіб запису передбачає використання певних графічних символів - блоків, кожен з яких позначає певний тип дії.
Кожен блок наказує виконання певних дій. Сукупність блоків утворює схему алгоритму або блок-схему.
Позначення деяких блоків відповідно до ГОСТ 19.701-90 СХЕМИ АЛГОРИТМІВ, програм ДАНИХ І СИСТЕМ