Главная   Онлайн инструменты по математической логике   Мат. логика теория   Как считает компьютер?   Схемы для ЭВМ    

Рекурсивные функции

Определение булевой функции
Элементарные булевы функции
Задание булевых функций посредством элементарных
Существенные и несущественные переменные
Эквивалентные функции
Основные эквивалентности
Функциональная полнота
Нормальные формы
Совершенные нормальные формы
Минимизация ДНФ методом Квайна
Карты Карно
Полином Жегалкина
Высказывания
Предикаты
Кванторы
Определение формальной теории
Исчисление высказываний
Теорема о дедукции. Полнота ИВ
Автоматическое доказательство теорем
Метод резолюций в ИВ
Определение алгоритма
Машина Тьюринга
Рекурсивные функции
Алгоритмически неразрешимые задачи
Алгоритмы и их сложности



     Договоримся, что:
         1. множество N натуральных чисел содержит 0 (нуль), т.е. N={0,1,2,3,...};
         2. рассматриваемые функции f=f(x1,x2,…,xn) определены только тогда, когда переменные принимают значения из N, т.е. xi∈N;
         3. область значений функций D⊆N;
         4. рассматриваемые функции f=f(x1,x2,…,xn) могут быть частично определенные, т.е. определенные не для всех наборов натуральных чисел.
     Введём в рассмотрение простейшие функции:
     o(x)=0, s(x)=x+1, Inm(x1,...,xn)=xm
     Эти функции могут быть вычислены с помощью соответствующего механического устройства (например, на машине Тьюринга). Определим операторы, которые по одной или нескольким заданным функциям строят новые функции.
     Оператор суперпозиции. Пусть даны функция f(x1,x2,…,xk) от k переменных и k функций f1(x1,x2,…,xn),…,fk(x1,x2,…,xn) от n переменных. Суперпозицией функций f,f1,…,fk называется функция:
     φ(x1,x2,…,xn)= f(f1(x1,x2,…,xn),…,fk(x1,x2,…,xn))
     Мы говорим, что функция φ получается применением оператора суперпозиции Sk+1 к функциям f,f1,…,fk, и пишем φ=Sk+1(f,f1,…,fk). Например, S2(s,o)=s(o(x)), т.е. функция, тождественно равная 1, а S2(s,s)=s(s(x)) - это функция у(x)=x+2.
     Оператор примитивной рекурсии. Пусть даны функции g(x1,x2,…,xn) и h(x1,x2,…,xn+2). Построим функцию f(x1,x2,…,xn+1) Пусть зафиксированы значения x1,x2,…,xn. Тогда полагаем:
     f(x1,x2,…,xn,0)=g(x1,x2,…,xn)
     f1(x1,x2,…,xn,y+1)= h(x1,x2,…,xn,y,f(x1,x2,…,xn,y))
     Эти равенства определяют функцию f(x1,x2,…,xn+1) однозначно. Функция f называется функцией, полученной с помощью оператора R примитивной рекурсии. Используется запись f=R(g,h).
     Индуктивное определение функции (продемонстрированное в операторе примитивной рекурсии) в математике не редкость. Например, индуктивно определяются:
     1) степень с натуральным показателем: a0=1, an+1=an·a;
     2) факториал: 0!=1, (n+1)!=n!·(n+1) и т.д.
     Определение.Функции, которые могут быть получены из простейших о(x)=0, s(x)=x+1, Inm(x1,...,xn)=xm применением конечного числа раз операторов суперпозиции и примитивной рекурсии, называются примитивно рекурсивными.
     Проверим, что функция u(x,y)=x+y является примитивно рекурсивной. Действительно, мы имеем: u(x,0)=0, u(x,y+1)=x+y+1=u(x,y)+1. Это есть схема примитивной рекурсии, так как x11(x), а u(x,y)+1=s(u(x,y))=S2(s,u). Здесь g(x)=x12, а h(x,y,u)=s(u)=S2(s,I33).
     Аналогично доказывается, что функции m(x,y)=x·y, d(x,y)=xy (считаем по определению 00=1), fact(x)=x! и многие другие являются примитивно рекурсивными.
     Отметим; что примитивно рекурсивные функции всюду определены (т.е. определены для всех значений их аргументов). Действительно, простейшие функции o, s, Inm являются всюду определёнными, а применение операторов суперпозиции и примитивной рекурсии ко всюду определённым функциям даёт также всюду определённые функции. Значит, такая функция, как

f(x,y)={x-y, если x≥y
не существует, если x<y

примитивно рекурсивной быть не может. Рассматривать функцию f(x,y)=x-y здесь мы не имеем права, так как значения функций должны быть натуральными числами (поэтому не отрицательными). Однако, можно рассмотреть функцию

x÷y={x-y, если x≥y
0, если x<y

     Проверим, что она примитивно рекурсивна. Докажем вначале, что функция φ(x)=x÷1 примитивно рекурсивна. Действительно, φ(0)=0. φ(y+1)=(y+1)÷1=y, что служит схемой примитивной рекурсии для функции x÷1. Наконец, x÷0=x, x÷(y+1)=(x÷y)÷1=φ(x÷y) ? схема примитивной рекурсии для x÷y.
     Существенно более широким классом функций, чем примитивно рекурсивные функции, является класс рекурсивных функций (определение см. ниже). В литературе эти функции называют также частично рекурсивными. Для их определения введём ещё один оператор.
     Оператор минимизации. Пусть дана функция f(x1,x2,… ,xn,xn+1). Зафиксируем какие-либо значения x1,x2,…,xn первых n переменных и будем вычислять f(x1,x2,…,xn,0), f(x1,x2,…,xn,1), f(x1,x2,…,xn,2) и т.д. Если y ? наименьшее натуральное число, для которого f(x1,x2,…,xn,y)=xn+1 (т.е. значения f(x1,x2,…,xn,0), f(x1,x2,…,xn,1),…,f(x1,x2,…,xn,y-1) все существуют и не равны xn+1), то полагаем g(x1,x2,…,xn,xn+1)=y. Таким образом,
     g(x1,x2,…,xn,xn+1)=min(y|f(x1,x2,…,xn,y)=xn+1).
     Если такого y нет, то считаем, что f(x1,x2,…,xn,xn+1) не определено. Итак, возможны три случая:
         1. f(x1,x2,…,xn,0), f(x1,x2,…,xn,1),…,f(x1,x2,…,xn,y-1) существуют и не равны xn+1, а f(x1,x2,…,xn,y)=xn+1;
         2. f(x1,x2,…,xn,0), f(x1,x2,…,xn,1),…,f(x1,x2,…,xn,y-1) существуют и не равны xn+1, а f(x1,x2,…,xn,y) не существует;
         3. f(x1,x2,…,xn,i) существуют при всех i∈N и отличны от xn+1.
     Если имеет место 1-й случай, то g(x1,x2,…,xn,xn+1)=y, а если 2-й или 3-й, то g(x1,x2,…,xn,xn+1) не определено. Про функцию g полученную таким образом, говорят, что она получена из f применением оператора минимизации М. Мы пишем g=Мf.
     Оператор минимизации - это очевидное обобщение оператора взятия обратной функции. Обобщение довольно глубокое, так как от функции f не требуется, чтобы она была взаимно однозначной (по переменной xn+1).
     Определение. Функции, которые могут быть получены из простейших о(x)=0, s(x)=x+1, Inm(x1,...,xn)=x применением конечного числа раз операторов суперпозиции, примитивной рекурсии и минимизации, называются рекурсивными.
     Класс рекурсивных функций шире класса примитивно рекурсивных функций хотя бы по тому, что он содержит не только всюду определённые функции. Докажем, например, что функция

f(x,y)={x-y, если x≥y
не существует, если x<y

является рекурсивной. Действительно, f(x,y)=min(z|y+z=x), а ранее было установлено, что функция u(x,y)=x+y примитивно рекурсивна.
     Рекурсивные функции отражают наше интуитивное представление о функциях, вычислимых некоторым механическим устройством. В частности, они вычислимы на машинах Тьюринга. Наоборот, всякая функция, вычислимая на машине Тьюринга является рекурсивной. Мы не будем проверять этот факт, так как это потребовало бы слишком много времени и места.
     Отметим, что не всякая функция натуральных аргументов является рекурсивной, даже не всякая функция одного аргумента. Существование нерекурсивных функций и является "математической причиной" наличия алгоритмически неразрешимых задач.

@ 2010 - 2016 tablica-istinnosti.ru Рейтинг@Mail.ru