1. Уважаемые друзья!

    С 8 февраля 2018 года наш форум переходит в режим Элитарного Клуба.
    Теперь незарегистрированным посетителям запрещено подглядывать и подслушивать наши тайные переговоры, а чтобы зарегистрироваться, нужно... впрочем, если вы действительно достойны стать членом Клуба, то вы наверняка разберётесь, как это сделать.

    Возрадуйтесь, обладатели зарегистрированных аккаунтов! Обещаем вам чистки, репрессии и все остальные бонусы тоталитарного сообщества.

    Всегда ваша,
    Администрация Корума

ДМ. Вычисления с неподвижной точкой

Тема в разделе "Вопросы высшей математики", создана пользователем BA3a, 28 июн 2013.

Модераторы: onyx
  1. BA3a

    BA3a for love and rock-n-roll VIP

    Теоретический минимум

    Условимся о такой записи условной конструкции [​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].
    Применяя [​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]. Например, [​IMG] — тоже правомерное разложение.

    Теорема о неподвижной точке

    Ссылающееся на себя определение функции [​IMG], где [​IMG] не имеет свободного вхождения в [​IMG], можно искать в виде [​IMG].
    Доказательство:
    Если в определении [​IMG] заменить [​IMG] на [​IMG], то получим [​IMG].

    Обратите внимание, что выше, при поиске нерекурсивного выражения [​IMG], эта теорема была доказана для частного случая.

    Более обстоятельные источники

    Вольфенгаген В. Э. Комбинаторная логика в программировании. Вычисления с объектами в примерах и задачах. — М.: МИФИ, 1994. — 204 с.; 2-е изд., М.: АО «Центр ЮрИнфоР», 2003. — 336 с.

    Интересное по теме

    Реализация Y на JavaScript.
Модераторы: onyx

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