Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
l-исчисление, основоположником которого считаютАлонзо Черча, фактически, и стало основой теории алгоритмов и первой конкретизации алгоритма. l-исчисление рассматривают также как основу таких важных разделов математики, как функциональное программирование и комбинаторная логика.
l-исчисление(нотация, способ записи) формализует понятие функции не как множества или графика, а как правила.
В основе l-исчисления лежит операция аппликации.
Аппликация - применение функции к аргументу (можно применить только известную функцию).
Язык состоит из:
1. Множества переменных (х1...).
2. Множества констант(с1...).
3. Символа аппликации..
4. Символа абстракции l.
5. Символа равенства =.
l-терм:
1. Переменная или константа - l-терм.
2. Если х - переменная, и М - некоторый l-терм, то lх.М тоже l-терм.
3. Если М и N l-термы, то MN тоже l-терм.
Формула - любое выражение вида M=N, где M и N l-термы.
Замечание. В литературе прикладного плана нередко используется несколько иная терминология и форма записи.
f = lx.x + x
f - название, ранее не названной функции.
l - оператор.
х - аргумент.
.-комбинатор.
х + х - выражение, задающее значение функции.
Аксиомы:
1. M = M.
2. (lx.M)N = M {N/x} b-редукция.
где {N/x} – подстановка N вместо всех вхождений x в М.
[В альтернативном представлении часто используемая b-редукция записывается, например, так (lx.f(x))(a) = f(a)]
3. lx.M = ly.M при {y/x} a-конверсия.
где {у/x} – подстановка у вместо всех вхождений x в М.
Правила вывода:
1. M = N
N = M.
2. M = N, N = P
M = P.
3. M = N
PM = PN.
4. M = N
MP = NP.
5. M = N
lx.M = lx.N.
Рассмотрим примеры b-редукции (в прикладной варианте записи)
(lх.х + 2у)(а) = а + 2у
(lу.х + 2у)(а) = х + 2а
(lх.(lу.х + 2у))(а)(b) = (lу.а + 2у)(b) = a + 2b
(lx.((ly.xy)u))(lv.v) = (ly.(lv.v)y)u = (lv.v)u
(lx.((ly.xy)u))(lv.v) = (lx.xu)(lv.v) = (lv.v)u
(lx.xx) (lx.xx) = (lx.xx) (lx.xx) = (lx.xx) (lx.xx) =…
((lx.x*3) (ly.if y > 4 then e = 2 else x/2) (ly.y>2)) (5) = 2*5 = 10
(ln.(lx.x-n))(2) = lx.x-2
(lf.2*f(8) – f(f(8)))(half) = 2*8/2 – (8/2)/2 = 6 (half – половина).
Дата публикования: 2014-11-03; Прочитано: 289 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!