Навигация
Главная
Поиск
Форум
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
Имитационное мо... 59474
Реклама
Сейчас на сайте
Гостей: 4
На сайте нет зарегистрированных пользователей

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

Расчет мер близости на отношениях на Delphi + Пояснительная записка
Лабораторная работа по динамическим спискам на Turbo Pascal (перемещение...
База данных - словарь терминов на Delphi + Пояснительная записка

Реклама



Подписывайся на 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 Комментариев · 2469 Прочтений · Для печати

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


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



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

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

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

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

Пароль



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

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

Случайные загрузки
iComm v.6.1 - выв...
БД студентов
DateEdit
Паскаль и Дельфи....
Win-Prolog 3.618
Алгоритмы шифрова...
Text effect
C++ Builder 6 СПР...
Globus VCL Extent...
Abc_component
Х. М. Дейтел, П. ...
CABfiles
CaptionButton
Добавление к ссы...
Последнее загруж...
AdBlaster v2.5 - ...
Run
Развивающийся фла...
SysInfo [Исходник...
Counter [Исходник...

Топ загрузок
Приложение Клие... 100512
Delphi 7 Enterp... 90282
Converter AMR<-... 20092
GPSS World Stud... 15003
Borland C++Buil... 12719
Borland Delphi ... 8944
Turbo Pascal fo... 7093
Калькулятор [Ис... 5136
Visual Studio 2... 5018
FreeSMS v1.3.1 3554
Случайные статьи
4.3. Принципы
Поимей халявный Ин...
Блок поддержки при...
Рекурсивное постро...
Чистые виртуальные...
Где взять денег в ...
Обработка транзакц...
Листинг 11.2. Сорт...
поддеревьев: какие...
Функции, макросы и...
Авторизация на сай...
использовании или ...
Вычисление произол...
Invalid object fil...
Компромиссы
S-Video
QueryInterface сим...
Google
Какие возможности ...
Способ проведения ...
Регистрация доменн...
Обход дерева
Ждать последующих ...
tldDomain Controll...
Алфавитный указате...
Статистика



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


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