Конспект установочных лекций по комплексному курсу Информатика, Теория информации



         

Рекурсивные функции - часть 4


Тем самым она определяется однозначно, что просто показывается через индукцию. Конечно, функция Аккермана интуитивно вычислима. Ее Т-вычислимость можно показать путем задания машины Тьюринга, которая вычисляет эту функцию. Этого можно достигнуть путем  моделирования магазина на Т-машине

Функция ack не является примитивно-рекурсивной. Фнкция ack состоит и множества примитивно-рекурсивных функций.

Теорема. Для любого числа n Î N функция Вn: N -> N,

специфицированная через

Теорема. Функция ack не является примитивно-рекурсивной.

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

m-рекурсивные функции

Примитивно-рекурсивные функции, соответственно определению, всегда являются тотальными. Как показывает пример функции Аккермана, существуют также тотальные функции, которые интуитивно являются вычислимыми и также

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

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

Пример (частично вычислимая функция). Для одноместной функции, заданной примитивно-рекурсивным определением (выражением), вычисляется ее наименьшее нулевое место - наименьшее натуральное число, для которого функция имеет значение 0 (т. е. min {х Î N: f (х) = 0}). Известно, что существует универсальная функция F (i, х), представляющая множество  всех  одноместных  частично  рекурсивных  функций (выражений).


Содержание  Назад  Вперед