Вычислимость и разрешимость

Доказано, что классы функций, вычислимых с помощью рекурсивных функций, машин Тьюринга или нормальных алгоритмов Маркова, совпадают. Это позволяет рассматривать понятие «вычислительный алгоритм» инвариантным к способу описания. Различия наблюдаются лишь в использовании алгоритмических объектов. Если для рекурсивных функций объектами являются числа и числовые функции, а процесс вычисления задан операторами суперпозиции, рекурсии, минимизации и итерации, то для машин Тьюринга такими объектами являются символы алфавитов внешней и внутренней памяти, а процесс вычисления задан протоколом, использующим функции выхода, перехода и перемещения головки. Для нормального алгоритма Маркова такими объектами являются слова или последовательности символов, а процесс вычисления задан правилами подстановки или продукциями, изменяющими состав и структуру исходной последовательности символов до искомого результата.

Функция называется вычислимой, если существует вычисляющий её алгоритм. Вычислимость является одним из основных понятий теории алгоритмов, инвариантным к вычисляемой функции и алгоритму. Различие между вычислимой функцией и алгоритмом – это различие между описанием функции и способом вычисления её значений при заданных значениях независимых аргументов.

Если для решения задачи, принадлежащей единому классу задач, найден алгоритм вычисления, то о задаче говорят как об алгоритмически разрешимой проблеме. Иначе говоря, обязательным условием вычислимости или результативности вычисления является её алгоритмическая разрешимость. В этом смысле понятие разрешимости является также основным понятием в теории алгоритмов.

Анализ трех типов моделей показывает, что основные свойства дискретности, детерминизма, массовости и результативности остаются неизменными для различных способов описания:

• Свойство дискретности: алгоритм состоит из отдельных элементарных действий, выполняемых по шагам; множество элементарных шагов, из которых состоит алгоритмический процесс, конечно и счетно.

• Свойство детерминированности: после каждого шага дается точное указание, как и в какой последовательности выполнять следующие шаги алгоритмического процесса.

• Свойство массовости: использование алгоритма допустимо для множества алгоритмических объектов данного типа и данного класса задач.

• Свойство результативности: остановка алгоритмического процесса обязательна после конечного числа шагов с указанием искомого результата.