Основна гіпотеза теорії алгоритмів

Будь-яка практична задача, що приводить до необхідності створення ефективного обчислювального методу (алгоритму), може бути поставлена в точних математичних термінах.

Ця парадигма (гіпотеза, принцип) стосовно уточнення поняття алгоритм, як абстрактної машини відома, у вигляді тези Т'юринга: «Для всякого алгоритму Sf в якому-небудь алфавіті може бути побудований тьюріноговський алгоритм, що дає при однакових вихідних даних, ті ж самі результати, що і алгоритм Sf».

Прийняття тези Т'юринга рівносильне прийняттю тези Черча (для частково-рекурсивних функції) або принцип нормалізації (для нормальних алгоріфмов).

Всі відомі приклади алгоритмів можна звести до питання обчислення відповідної функції. Вважаючи цю межу алгоритмів основною, можна побудувати формальне уточнення поняття обчислюваної функції. У основі цього твердження лежить теза Черча: “Всяка функція, значення якої може обчислюватися ефективно, є частково-рекурсивною” (тобто обчислюваними функціями є частково-рекурсивні функції – функції, що отримуються за кінцеве число кроків з простих за допомогою суперпозиції, примітивної рекурсії і μ-оператора).

В світлі викладеного в алгоритмічній системі Черча вихідними конструктивними об'єктами є базисні функції (x1, x2.,xm,.,xn)= xm, конструктивний процес обумовлений застосуванням до базисних функцій операторів суперпозиції S, примітивній рекурсії R і мінімізації?, а результатом кінцевого процесу є рекурсивні функції, тобто:

В даний час широко використовується в теорії алгоритмів теза Черча-Т'юрінга: «Будь-яка теоретично вирішувана обчислювальна задача може бути вирішена за допомогою машини Тюрінга».