Формалізація поняття алгоритму

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

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

Розглянемо взаємозв'язок між функцією і алгоритмом. Відразу відзначимо, що основні властивості цього взаємозв'язку ми будемо тут наводити без доведення. Тому є як мінімум дві причини. Перша - у читача не передбачається знання необхідного математичного апарату; друга - це відвів би нас у бік від основної мети - Формалізації поняття алгоритму.

Визначення 2.1. Кажуть, що алгоритм А обчислює функцію f (x), якщо:

Існує взаємно однозначна відповідність j між областю визначення f (х) і областю застосовності А;

Для будь-якого х з області визначення f вірно: f (x) = A (j (x))

У цьому випадку функція f (x) називається вичіслімой функцією.

Визначення 2.2. Кажуть, що Алгоритм А дозволяє безліч М щодо безлічі Х, де М