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

Тема в разделе "Вопросы высшей математики", создана пользователем Silver MC's, 29 июн 2013.

Модераторы: onyx
  1. Silver MC's

    Silver MC's ┬┴┬┴┤(・_├┬┴┬┴

    Примитивно-рекурсивные функции
    Теоретический минимум

    Класс примитивно-рекурсивных функций определяется путем указания конкретных исходных функций (они называются базисными) и фиксированного множества операций над ними, применяемых для получения новых функций из ранее заданных.
    В качестве базисных функций обычно берутся следующие:
    •Функция следования [​IMG];
    •Функция тождества (функция проекции, или функция выбора аргументов)[​IMG];
    •Функция константы [​IMG].
    Допустимыми операциями над функциями являются операции:
    •суперпозиции (подстановки)[​IMG];
    •примитивной рекурсии[​IMG].
    Эти три функции и две операции образуют базис Клини
    Для начала, рассмотрим каждую из функций.
    1) функция – следование: [​IMG], где [​IMG] – число, непосредственно следующее за натуральным числом [​IMG]. Например, [​IMG] и т.д.
    2) функция - тождество: [​IMG], где n – кол-во переменных, а i – номер переменной, по которой берется тождество. Функция тождества – функция, равная одному из своих аргументов. Например, [​IMG].
    3) функция - константа: [​IMG], где n – число переменных, q – значение, которое принимает функция. Функция константа принимает всюду одно значение. Например, [​IMG].
    Далее рассмотрим операции.
    1) операция примитивной рекурсии [​IMG]
    Если мы имеем функцию одной переменной [​IMG], то схема рекурсии называется «рекурсия без параметров» и задается системой уравнений:
    [​IMG]
    [​IMG]
    Функция, заданная такими уравнениями, кратко задается схемой вида [​IMG]. Поскольку вид системы уравнений (и способ задания трех разрешенных функций) строго определен, то схема является однозначной.
    Если мы имеем функцию нескольких переменных [​IMG], то схема рекурсии называется «рекурсия с параметрами» и задается системой уравнений:
    [​IMG]
    [​IMG]
    Функция, заданная такими уравнениями, кратко задается схемой вида [​IMG]

    2) операция подстановки (суперпозиции) [​IMG]:
    Пусть заданы [​IMG] каких-либо частичных арифметических функций [​IMG] от одного и того же числа [​IMG] переменных, определенных на множестве [​IMG] со значениями в множестве [​IMG]. Пусть на множестве [​IMG] задана частичная функция [​IMG] от [​IMG] переменных, значения которой принадлежат множеству [​IMG]. Введем теперь частичную функцию [​IMG] от [​IMG] переменных, определенную на [​IMG] со значениями в [​IMG], полагая по определению для произвольных [​IMG].
    [​IMG]
    Говорят, что функция [​IMG] получается операцией суперпозиции или подстановки из функций [​IMG]. Обозначается эта операция [​IMG] где n показывает от скольких переменных зависят внутренние функции [​IMG], а [​IMG] – количество самих функций [​IMG].
    [​IMG],
    При этом функция [​IMG] при подсчете внутренних функций не учитывается.

    Примеры
    Пример 1. Доказать примитивную рекурсивность функции [​IMG].
    Будем строить рекурсию по первой переменной. Применяем операцию примитивной рекурсии:
    [​IMG]
    [​IMG]
    Теперь наша задача - переписать все, используя только три основные функции:
    [​IMG]
    [​IMG]
    Для удобства, в будущем не будем писать аргументы функций:
    [​IMG]
    [​IMG]
    В итоге, мы получили [​IMG]
    Примечание 1. Все функции, рассмотренные в примерах, далее будем считать примитивно-рекурсивными без доказательства. Это позволит нам делать более компактные записи, используя в общей записи помимо трех основных функций еще и полученные, например функция суммы двух элементов [​IMG]
    Примечание 2. По умолчанию будем считать, что аргументы функций будут идти в стандартном порядке, причем первым аргументом будет либо исходная функция ([​IMG]), либо переменная, которая определяется однозначно ([​IMG]).
    Пример 2. Доказать примитивную рекурсивность функции [​IMG].
    Будем строить рекурсию по первой переменной. Применяем операцию примитивной рекурсии:
    [​IMG]
    [​IMG]
    В итоге получаем: [​IMG]
    Примечание. Далее [​IMG] - произведение двух чисел
    Пример 3. Доказать примитивную рекурсивность факториала [​IMG].
    Применяем операцию примитивной рекурсии:
    [​IMG]
    [​IMG]
    В итоге получаем: [​IMG]

    Задачи для тренировки
    Задача 1. Докажите примитивную рекурсивность функции [​IMG]
    Задача 2. Докажите примитивную рекурсивность для псевдоразности [​IMG].
    Примечание. Псевдоразность [​IMG]
    Задача 3. Докажите примитивную рекурсивность функции [​IMG]
    Примечение. [​IMG]

    Частично-рекурсивные функции
    Теоретический минимум

    Частично-рекурсивные функции могут представлены с помощью тех же трех функций ([​IMG]), но уже с тремя операциями: примитивной рекурсии, суперпозиции и минимизации; т.е. задана в расширенном базисе Клини.

    Оператор минимизации.
    Пусть имеется функция [​IMG], принадлежащая множеству частичных арифметических функций (ЧАФ). Пусть существует какой-то механизм ее вычисления, причем значение функции не определено тогда и только тогда, когда этот механизм работает бесконечно, не выдавая никакого определенного результата.
    Фиксируем какие-нибудь значения [​IMG] для первых [​IMG] аргументов функции [​IMG] и рассмотрим уравнение: [​IMG]
    Чтобы найти решение [​IMG] (натуральное) этого уравнения, будем вычислять при помощи указанного выше "механизма" последовательно значения [​IMG] для [​IMG]. Наименьшее значение [​IMG], для которого получится [​IMG], обозначим через [​IMG]
    Описанный процесс нахождения выражения [​IMG] будет продолжаться бесконечно в следующих случаях:
    • Значение [​IMG] не определено;
    • Значения [​IMG] для [​IMG] определены, но отличны от [​IMG], а значение [​IMG] – не определено;
    • Значения [​IMG] определены для всех [​IMG] и отличны от [​IMG].
    Во всех этих случаях значение выражения [​IMG] считается неопределенным. В остальных случаях описанный процесс обрывается и дает наименьшее решение [​IMG] уравнения [​IMG]. Это решение, как сказано, и будет значением выражения [​IMG].
    Например, функция разности [​IMG] c помощью оператора минимизации будет записана так:
    [​IMG]
    Подсчет значений функции [​IMG] в этом случае будет проходить по двум сценариям.
    Пример 4. Пусть [​IMG]. Последовательно, начиная с [​IMG], перебираем возможные значения для нахождения [​IMG]:
    • при [​IMG] получим выражение [​IMG], его значение «ложь»;
    • при [​IMG] получим выражение [​IMG], его значение «ложь»;
    • при [​IMG] получим выражение [​IMG], его значение «истина», следовательно, процесс обрывается, и получаем результат: [​IMG].
    Пример 5. Пусть [​IMG]. Последовательно, начиная с [​IMG], перебираем возможные значения для нахождения [​IMG]:
    • при [​IMG] получим выражение [​IMG], его значение «ложь»;
    • при [​IMG] получим выражение [​IMG], его значение «ложь»;
    • при [​IMG] получим выражение [​IMG], его значение «ложь»;
    и т.д. – т.е. при увеличении [​IMG] ситуация, при которой выражение [​IMG] будет иметь значение «истина», так и не наступит, а значит значение функции [​IMG] так и не будет найдено.
    Пример 5 – это иллюстрация случая, при котором оператор минимизации не дает результата именно тогда, когда такой результат не может быть получен в принципе, по той причине, что в заданной точке функция действительно не определена. Это третий случай, в котором процесс поиска выражения [​IMG] продолжается бесконечно.
    Напротив, значение выражения [​IMG] не определено, так как уже при [​IMG] значение терма [​IMG] для любого [​IMG] не определено. В то же время уравнение [​IMG] имеет решение [​IMG], но оно не совпадает со значением выражения [​IMG].
    Этот пример показывает, что для частичных функций [​IMG] выражение [​IMG], строго говоря, не есть наименьшее решение уравнения [​IMG]. Если же функция [​IMG] всюду определенная и уравнение [​IMG] имеет решения, то [​IMG] есть наименьшее решение для этого уравнения. Отсюда возникает закономерное желание использовать под оператором минимизации только всюду определенные функции. Наилучший способ убедиться в том, что функция всюду определена – использовать заведомо примитивно-рекурсивные функции (или функции, примитивная рекурсивность которых уже доказана ранее или вытекает из способа их задания). В этом случае значения [​IMG] будет неопределенно только в одном из трех случаев, а именно если значения [​IMG] определены для всех [​IMG] и отличны от [​IMG]. Для этого имеющуюся функцию нужно преобразовать таким образом (путем переноса слагаемых, умножения обеих частей, и т.д.) чтобы по обе стороны равенства стояли примитивно рекурсивные (а значит всюду определенные) выражения. В общем виде, под оператором минимизации получим некое рекурсивное уравнение, части которого зависят от переменных [​IMG]. Это уравнение принимает значение «истина» или «ложь» при последовательно выбираемых значениях параметра [​IMG].
    Итак, для того, чтобы задать частично-рекурсивную функцию в виде элементарной схемы ее вычисления, необходимо расширить введенный ранее базис Клини за счет появления новой операции: операции минимизации. Здесь важно понимать, что в расширенном базисе Клини в итоге могут оказаться заданы также и примитивно-рекурсивные функции – но для примитивно-рекурсивных функций использование этого оператора, по сути, является избыточным.

    Пример 6. Нигде неопределенная функция [​IMG]. Построим рекурсивное уравнение: [​IMG]. Результат операции минимизации не определен даже для точки [​IMG].
    Пример 7. Функция, определенная в одной точке, [​IMG]. Построим рекурсивное уравнение: [​IMG]. Результат операции минимизации определен только для точки [​IMG], при остальных значениях [​IMG] вычисление (подбор нужного значения [​IMG]) никогда не будет закончено.
    Пример 8. Применить оператор минимизации для функции [​IMG].
    Будем проводить минимизацию по каждому элементу. Т.е. вместо [​IMG] каждый раз будем подставлять [​IMG], а [​IMG] будет стоять справа. Каждое из этих уравнений надо будет решить сначала в общем виде, а затем подобрать [​IMG], либо доказать невычислимость.
    1)[​IMG]
    Решаем уравнение относительно [​IMG] и получаем:
    [​IMG]
    Теперь проанализируем исходное уравнение и полученное решение.
    Из исходного уравнения видно, что при [​IMG] может принимать любое значение, но нам нужно минимальное, т.е [​IMG]. Это первое решение.
    из решения можно увидеть, что [​IMG] при условии, что [​IMG] и [​IMG] кратно разности [​IMG]. Это второе решение. Оба решения найдены.
    2)[​IMG]
    решение полностью аналогичное первому пункту.
    3)[​IMG]
    решаем уравнение относительно z и получаем:
    [​IMG] при [​IMG]. В противном случае решений нет.
    4)[​IMG]
    В этом случае [​IMG] - может быть любое, если равенство выше выполняется, поэтому выбираем наименьшее, т.е [​IMG], в противном случае решений нет.

    Задачи для тренировки
    Применить оператор минимизации для функций:
    Задача 4.[​IMG]
    Задача 5.[​IMG]
    Задача 6.[​IMG]
  2. BA3a

    BA3a for love and rock-n-roll VIP

    О, а я уже начал это забывать потихоньку.
  3. Silver MC's

    Silver MC's ┬┴┬┴┤(・_├┬┴┬┴

    BA3a, я оказывается тоже :huh: но семинары полистал, вспомнил) сегодня наверно еще парочку примеров добавлю, а после экзамена добавлю теорию по ЧРФ
  4. BA3a

    BA3a for love and rock-n-roll VIP

    Silver MC's, если найти конспекты, то и я за какое-то время вспомню. Но найти их — не такая уж и простая задача.
  5. Silver MC's

    Silver MC's ┬┴┬┴┤(・_├┬┴┬┴

    Update 1. Добавил еще 2 примера и три задачи для самостоятельного решения. Просьба, ответ здесь не писать. Для проверки - напишите в ЛС. Спасибо :huh:
  6. Silver MC's

    Silver MC's ┬┴┬┴┤(・_├┬┴┬┴

    Update 2. Добавил теорию, примеры и задачи по частично-рекурсивным функциям
  7. BuTaJIuÚ

    BuTaJIuÚ Новичок

    Подскажите пожалуйста как решить если можно с объяснением

    Вложения:

    • 30000.png
      30000.png
      Размер файла:
      36,5 КБ
      Просмотров:
      12
Модераторы: onyx

Поделиться этой страницей