Определение алгоритма на основе рекурсивных функций

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

Функция, для которой существует алгоритм оценки для любого аргумента в области определения функции, называется вычислимой.

Функция, для которой существует эффективная процедура ее вычисления на основе рекурсии, называется рекурсивной.

Класс рекурсивных функций тождественен с классом всюду определенных вычислимых функций – тезис Черча.

Функция, определенная не для всех значений аргументов, а только на некотором подмножестве, называется частичной функцией.

Все частичные функции, вычислимые посредством алгоритмов, являются частично рекурсивными – тезис Клини.

Понятие частично рекурсивных функций используют для доказательства алгоритмической разрешимости или неразрешимости проблемы.

Определение алгоритма на основе абстрактных автоматов (машины Тьюринга)

Алгоритмические процессы – это процессы, которые может совершать подходяще устроенная «машина».

Под «машиной» в данном случае подразумевается некоторый абстрактный, существующий лишь в воображении автомат.

В общем случае такая машина состоит из следующих частей:

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

- из головки чтения/записи, вдоль которой может перемещаться лента;

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

Такая машина может сдвигать ленту на одну ячейку влево или вправо, оставляя содержимое ячеек неизменным, или может изменять состояние воспринимаемой ячейки, оставляя ленту неподвижной. Машина Тьюринга работает в произвольном конечном алфавите и выполняет некоторое конечное число приказов.

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

Интуитивное понимание машины Тьюринга таково: имеется бесконечная лента, разделённая на клетки. По клеткам ездит каретка. Прочитав букву, записанную в клетке, каретка движется вправо, влево или остаётся на месте, при этом буква заменяется новой. Некоторые буквы останавливают каретку и завершают работу.