МОДЕЛИ ЛАМБДА-ИСЧИСЛЕНИЯ

С.В. Косиков
НОУ «Институт актуального образования «Юринфор-МГУ»
г. Москва

Публикуется в сокращении

Комбинаторные алгебры

Аппликативная структура

Определение. M = (X, ·) называется аппликативной структурой, если · – бинарная операция на множестве X.

Определение. Аппликативная структура M = (X, ·) экстенсиональна, если для любых a, b из X
(для любого x из X) (a · x = b · x) ⇒ a = b.

Определение. Пусть M = (X, ·) – аппликативная структура. Множество термов над M определяется следующим образом:
(i) 1. x - переменная    ├    x - терм над M.
     2. a из M    ├    c_a - терм над M.
(ii) A, B - термы над M    ├    (AB) - терм над M.
(iii) Других термов нет.

Определение. Оценка ρ в M – это отображение из переменных в M.
Определение. Пусть M = (X, ·) – аппликативная структура. Интерпретация терма в M при оценке ρ определяется следующим образом:
(i) 1. [x]_ρ = ρ(x).
     2. [c_a]_ρ = a.
(ii) [AB]_ρ = [A]_ρ · [B]_ρ

Комбинаторная полнота

Определение. Пусть M = (X, ·) – аппликативная структура и φ: X ⁿ → X – отображение.
1. φ называется представимым над M, если
существует f из X такая, что для любых a₁, ..., a_i, ..., a_n из X f a₁...a_n = φ (a₁, ..., a_n)
2. φ называется алгебраическим над M, если существует терм A над M такой, что FV(A) включено в {x₁, ..., x_n} и
для любых a₁, ..., a_n из X φ (a₁, ..., a_n) = [A]_{ρ (x := a)}
Очевидно, что все представимые функции – алгебраические.

Определение. Аппликативная структура M = (X, ·) комбинаторно полна, если все функции, алгебраические над M, представимы над M.

Комбинаторные алгебры

Определение. Комбинаторная алгебра – это аппликативная структура M = (X, ·, k, s) с двумя выделенными элементами k, s, удовлетворяющими равенствам k · x · y = k k · x · y · z = x · z · (y · z).

Теорема. Аппликативная структура комбинаторно полна тогда и только тогда, когда она может быть расширена до комбинаторной алгебры (путём выбора k, s). Следовательно, любая комбинаторная алгебра комбинаторно полна.

Никакая часть содержащегося здесь текста ни в каких целях не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами, будь то электронные или механические, если на то нет письменного разрешения АО "Центр ЮрИнфоР".

(Размещена 12 января 2010 г.)