Алгоритмические (формальные математические) модели.

Приведенное выше «наивное» (интуитивное) понятие алгоритма как первичное (исходное) понятие математики не допускает его определения в терминах более простых понятий. Возможные уточнения понятия алгоритма приводят, строго говоря, к известному сужению этого понятия. Каждое такое уточнение состоит в том, что для каждого из семи параметров алгоритма точно описывается некоторый класс, в пределах которого этот параметр может меняться. Выбор таких классов и отличает одно уточнение от другого. Поскольку семь параметров однозначно определяют некоторый алгоритм, то выбор семи классов изменения этих параметров определяет некоторый класс алгоритма.

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

Так, понятие машины Тьюринга как FS¹следующим образом может быть использовано для уточнения общего представления об алгоритме в данном алфавите, еслиТьюринговским алгоритмом в алфавите Аназывается всякий алгоритмUследующего вида:

• фиксируется некоторая машина Тьюринга в алфавите А, то есть <A,Q,R>, здесьQ– множество внутренних состояний машины, аR– правило перехода из одной конфигурации машины к другой);

• задается - слово, принимаемое в качестве исходного данного дляU(A^*);

• строится исходная конфигурация машины a₀q₀a₀, гдеq₀ – начальное состояние машиныq₀Q,a₀ – пустой символ,a₀А;

• машина, отправляясь из a₀q₀a₀, заканчивает работу в заключительной конфигурации.

Считается, что для всякого алгоритма Uв каком-либо алфавите может быть построен тьюринговский алгоритм, дающий при одинаковых исходных данных те же самые результаты, что и алгоритмU. Это соглашение в теории алгоритмов известно как тезис Тьюринга: «Всякий алгоритм может быть реализован машиной Тьюринга».

Замечания:

1. Доказать тезис Тьюринга нельзя, поскольку само понятие алгоритма (или эффективной процедуры) является неточным. Это не теорема и не постулат математической теории, а утверждение, которое связывает теорию с теми объектами, для описания которых она создана. По своему характеру тезис Тьюринга напоминает гипотезы физики об адекватности математических моделей физическим явлениям и процессам. Подтверждением правильности тезиса Тьюринга является математическая практика, а также эквивалентные тезисы и, в частности, тезис Черча для рекурсивных функций: «Всякая функция, вычислимая некоторым алгоритмом, частично-рекурсивная».

2. Из сопоставления двух вышеприведенных тезисов вытекает утверждение: «Функция вычислима машиной Тьюринга тогда и только тогда, когда она частично-рекурсивна». Это утверждение об эквивалентности двух алгоритмических моделей является (в отличие от тезисов) вполне точным математическим утверждением и, следовательно, доказуемо, то есть имеют место две теоремы:

Теорема 1:Всякая частично-рекурсивная функция вычислима на машине Тьюринга.

Теорема 2: Всякая функция, вычислимая на машине Тьюринга частично-рекурсивная.

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

4. Тезисы позволяют выявлять случаи невозможности алгоритмов, однако, не указывают в случае их существования пути построения удобного для практики алгоритма (Напоминание: «Теория алгоритмов не учит строить конкретные алгоритмы»).