L-исчисление

M-оператор.

my[g(x₁, ... , x_n, y) = 0]

где y - выделенная переменная.

Работу m-оператора можно описать следующим образом.

Выделяется переменная (здесь – у). Затем фиксируется значение остальных переменных (x₁, ... , x_n). Значение y последовательно увеличивается, начиная с нуля. Значением m-оператора будет значение y, при котором функция впервые обратилась в ноль. Значение m-оператора считается неопределенным, если функция вообще не принимает значения ноль, либо она принимает отрицательое значение до того как примет значение ноль.

Пример.

Пусть функция g(х, y) = х – у + 3. Зафиксируем х = 1

my[g(1, y) = 0] = 4

так как 1 – 4 + 3 = 0.

Класс (множество, которое может быть получено из примитивных функций с помощью операторов суперпозиции, примитивной. рекурсии и m-оператора, называется. множеством частично-рекурсивных функций.

Множество частично-рекурсивных функций совпадает с множеством вычислимых функций - алгоритмически разрешимых задач.

l-исчисление, основоположником которого считаютАлонзо Черча, фактически, и стало основой теории алгоритмов и первой конкретизации алгоритма. l-исчисление рассматривают также как основу таких важных разделов математики, как функциональное программирование и комбинаторная логика.

l-исчисление(нотация, способ записи) формализует понятие функции не как множества или графика, а как правила.

В основе l-исчисления лежит операция аппликации.

Аппликация - применение функции к аргументу (можно применить только известную функцию).

Язык состоит из:

1. Множества переменных (х₁...).

2. Множества констант(с₁...).

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