Лямбда-исчисление. Нумералы и комбинаторы

Сообщение №23172 от Envy 26 декабря 2007 г. 07:05
Тема: Лямбда-исчисление. Нумералы и комбинаторы

Прошу помощи в решении задач по лямбда-исчислению. Задачки (по идее) элементарные, но мне не дались. Сдавать завтра.
Собственно, задачки:
1)
(Х. Барендрегт) Определим комбинаторы:
V = \λxyz.zxy,
T = \λxy.yx;
<0> = I, = (false, ).
Доказать, что функции следования, предшествования и тест на ноль можно определить следующим образом :
succ =≡ V false; (следование)
pred =≡ T false (предшествование)(значение pred для <0> не определено);
zero? =≡ T true. (проверка на 0)

2)
Пусть B =≡ \λfgx.f(gx).
Доказать, что для любого нумерала Черча при n>0 имеет место равенство B f g x1…xn = f (g x1…xn). ( B f g – аналог композиции функций f и g, когда g имеет n аргументов.) Используйте математическую индукцию.

Буду благодарен за любую помощь. Заранее спасибо.


Отклики на это сообщение:

Прошу прощения, кривизна рук привысила максимально допутстимую и в текст попали ошибки:
\λ следует читать как lambda;
=≡ как ≡


__________Структура форума. Разделы.


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100