Лекция: L-исчисление

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 – половина).