На головну

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

 




 Внутрішня стійкість графа |  ядро графа |  Побудова Кліки. |  морфізм груп |  Група Клейна четвертого ступеня |  поняття алгоритму |  складність обчислень |  машини Тьюринга |  Нормальні алгорифм Маркова |  Нормальна схема преобразуемое |

© um.co.ua - учбові матеріали та реферати