Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Бип из системно... 65535
Гостевая книга ... 65535
Invision Power ... 65535
Пример работы с... 65535
Содержание сайт... 65535
ТЕХНОЛОГИИ ДОСТ... 65535
Организация зап... 65535
Вызов хранимых ... 65535
Создание отчето... 65535
Программируемая... 65535
Эмулятор микроп... 65535
Подключение Mic... 65535
Создание потоко... 65535
Приложение «Про... 65535
Оператор выбора... 65535
Модуль Forms 65535
Имитационное мо... 60083
Реклама
Сейчас на сайте
Гостей: 6
На сайте нет зарегистрированных пользователей

Пользователей: 13,113
новичок: SaRdOr0493
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Моделирование системы управления качеством производственного процесса на...
Обработка задач на ЭВМ на GPSS + Пояснительная записка
Моделирование работы узла коммутации сообщений на GPSS + Пояснительная з...

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании
Использование комбинатора Y
В качестве основного примера, выполнение которого иллюстрирует
основные эффекты вычислений с неподвижной точкой воспользуем-
ся функцией факториала F AC. Запишем функцию F AC сокращен-
но:
F AC = λn.(. . . F AC . . .). (9.1)



Применяя λ-абстракцию, получим:
λf ac.F AC f ac = (λf ac.(λn.(. . . f ac . . .)))F AC. (9.2)



9.2. ИСПОЛЬЗОВАНИЕ КОМБИНАТОРА Y
По правилу (η) получаем:
λf ac.F AC f ac = F AC,



и определение (9.2) запишется в виде:
F AC = (λf ac.(λn.(. . . f ac . . .)))F AC. (9.3)



Полагая H = λf ac.(λn.(. . . f ac . . .)), получим:
F AC = H F AC. (9.4)



Определение H представляет собой обычную λ -абстракцию, не ис-
пользующую рекурсию. Рекурсия выражена только лишь в форме
равенства (9.4). Определение (9.4) похоже на математическое урав-
нение. Например, решить уравнение (x2 −2) = x - это значит найти
значения x, которому удовлетворяют (x = −1, x = 2). Аналогич-
но, для того, чтобы решить (9.4), необходимо найти λ -абстракцию
для F AC, которая удовлетворяет (9.4). Уравнение F AC = H F AC
выражает тот факт, что когда функция H применяется к аргументу
F AC, в результате снова получаетсяF AC. ПоэтомуF AC называет-
ся неподвижной точкой функции H.
Пример 1. Числа 0 и 1 являются неподвижными точками функции
f = λx.×x x, то есть f0 = 0 и f1 = 1. Действительно,
f0 = (λx.×x x)0 = (β)
= × 0 0 = 0,
f1 = (λx.×x x)1 = (β)
= × 1 1 = 1.



Итак, нужно найти неподвижную точку функции H. Ясно, что эта
точка зависит только от H. Введем функцию Y , которая работает по
схеме: получив на входе в качестве аргумента функцию, на выходе
Y формирует неподвижную точку этой функции. То есть, получа-
ем Y H = H(Y H), где Y -- комбинатор неподвижной точки. Если
найдем такой Y , то получим решение уравнения (9.4):
F AC = Y H.



В ходе получения этого решения использован довольно общий ме-
тод. Он опирается на основную в теории рекурсивных вычислений
теорему о неподвижной точке. Фактически, пришлось дать ее част-
ное “доказательство” для функции F AC. Полученное решение дает
нерекурсивное определение F AC. Существо теоремы о неподвиж-
ной точке как раз и состоит в том, чтобы гарантировать переход от ре-
курсивных по форме записи определений к нерекурсивным по фор-
ме записи определениям. В последнем случае эффект цикличности
определения (и соответствующего вычисления) оказывается завуа-
лированным посредством комбинатора Y . Для того, чтобы убедится,
что определенная таким образом функцияF AC работает правильно,
приложим ее к некоторому аргументу, например, к 1:

F AC 1 = Y H 1 (F AC)
= H(Y H)1 (Y )
= (λf ac.(λn.(IF(= n 0)1)(×n(f ac(− n 1))))(Y H)1 (H)
= (λn.IF(− n ))1(×n(Y H(− n 1))))1 (β)
= IF(= 1 0)1(×1(Y H(− 1 1)))) (β)
= ×1(Y H)0 = ×1(H(Y H))0 (Y )
= ×1((λf ac.λn.IF(= n 0)1(×n(f ac(− n 1))))(Y H)0 (H)
= ×1((λn.IF(= n 0)1(×n(Y H(− n 1))))0) (beta)
= ×1(IF(= 0 0)1(×0(Y H(− 0 1)))) (β)
= ×11
= 1.


Опубликовал Kest April 15 2014 16:44:24 · 0 Комментариев · 2490 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
Geo-Whois
Delphi. Разработк...
Измерение тактово...
Панель статистики...
Ehlib
База предприятий ...
AdBlaster v2.5 - ...
Искусство програм...
Atb
Binary2XMLDemo (Р...
Swing. Эффектные...
Blib [Исходник на...
Calendar
Flash MP3 Player ...
Система баннеро-о...
Converter AMR<->W...
Delphi 2005. Разр...
Программирование ...
База данных: Книж...
Visual Basic Script

Топ загрузок
Приложение Клие... 100519
Delphi 7 Enterp... 91109
Converter AMR<-... 20098
GPSS World Stud... 15138
Borland C++Buil... 12878
Borland Delphi ... 9073
Turbo Pascal fo... 7105
Калькулятор [Ис... 5156
Visual Studio 2... 5027
FreeSMS v1.3.1 3557
Случайные статьи
Одной из мощных ко...
Как вывести сайт и...
Передача символьно...
Цель
Настройки публикации
Модель стоимости в...
Aura SE Parser / Л...
Двойной амперсанд ...
Функции GetX и Get...
систем безопасност...
2.6.3. Установле...
Переработка
Взаимосвязь станда...
Шифрование сообщен...
Записи Android-при...
Прямой городской н...
Команда DIV
Применение вспышки...
транспортном режим...
Расчет стоимости э...
Представление дере...
Меню
Перенос WSUS из Se...
Работа с транзакта...
ВВЕДЕНИЕ В ОТСЕЧЕНИЕ
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?