Правило примитивной рекурсии

Функция-проекция

(4.3)

Правила преобразования функций

1. Правило подстановки (суперпозиции)

Пусть даны функции:

Тогда

(4.4)

где g и h являются или простейшими, или выведенными из простейших.

Правило вывода (4.4) означает, что функция получена из функций правилом суперпозиции

ПРИМЕР

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

, (4.5)

Основывается на простейших или выведенных из простейших функциях g и h:

Пусть

Тогда новая функция может быть выведена по правилу:

(4.6)

Следует отметить, что функция зависит от аргументов, функция зависит от аргументов, функция зависит от аргументов. Иначе говоря, правило примитивной рекурсии позволяет получить n + 1 -местную функцию из n -местной и n + 2 - местной функций.

ПРИМЕР

Пусть некоторая функция задана правилом рекурсии

Нетрудно заметить, что функция , функция

Вычислим значение функции при .

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

3. m - оператор (оператор нахождения наименьшего корня у)

Оператор определяет наименьшее значение у, при котором при фиксированном значении. Принято обозначение

(4.7)

(Читается: «наименьшее такое, что »). Аналогично определяется функция многих переменных:

(4.8)

Для вычисления функции существует следующий алгоритм:

1. Вычисляется . Если это значение функции равно нулю, то . Если , то осуществляется переход к следующему шагу.

2. Вычисляется . Если это значение функции равно нулю, то . Если , то осуществляется переход к следующему шагу. И т. д.

Если окажется, что для всех функция , то функция считается неопределенной.

ПРИМЕР

Дана функция . Необходимо определить при

Таким образом,

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

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

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

Тезис А. Черча. Если функция является общерекурсивной, то она выполнима, т.е. имеет алгоритм решения.

4.2. Машина Тьюринга

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

Машина Тьюринга включает в себя:

1. Внешний алфавит - конечное множество символов . В этом алфавите в виде слова кодируется та информация, которая подается в машину. Машина перерабатывает информацию, поданную в виде слова, в новое слово. Обычно символ обозначает пробел.

2. Внутренний алфавит - конечное множество символов . Для любой машины число состояний фиксировано. Два состояния имеют особое назначение - начальное состояние машины, - заключительное состояние (стоп-состояние).

3. Операторы перемещения Т={Л, П, Н}. Л, П, Н – это символы сдвига «влево», «вправо» и «на месте».

4. Бесконечная лента Бесконечная лента характеризует память машины. Она разбита на клеточки. В каждую клеточку может быть записан только один символ из внешнего алфавита.

5. Управляющая головка. Управляющая головка (УГ) передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т. е. считывать символ

6. Управляющая головка. Управляющая головка (УГ) передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т. е. считывать символ.

Рис. 4.1. Функциональная схема машины Тьюринга.

Дата добавления: 2013-12-12