1632
правки
Изменения
м
{{nohate}}
:<tex>\begin{tabular}{cc}|! Standart & ! de Bruijn \\|-| $\lambda x.x$ & | $\lambda .0$ \\|-| $\lambda z.z$ & | $\lambda .0$ \\|-| $\lambda x. \lambda y.x$ & | $\lambda . \lambda .1$\\|-| $\lambda x. \lambda y. \lambda s. \lambda z.x\ s\ (y\ s\ z)$ & | $\lambda . \lambda . \lambda . \lambda .3\ 1(2\ 1\ 0)$\\|-| $(\lambda x.x\ x)(\lambda x.x\ x)$ & | $(\lambda .0\ 0)(\lambda .0\ 0)$\\|-| $(\lambda x. \lambda x.x)(\lambda y.y)$ & | $(\lambda .\lambda .0)(\lambda .0)$\\\end{tabular|}</tex>
rollbackEdits.php mass rollback
'''Лямбда-исчисление''' (''англ. lambda calculus'') {{---}} формальная система, придуманная в 1930-х годах
Алонзо Чёрчем. Лямбда-функция является, по сути, анонимной функцией.
по <tex>x</tex>.
===α-эквивалетностьэквивалентность===
{{Определение
|definition='''<tex>\alpha</tex>-эквивалетностьюэквивалентностью''' (англ. ''<tex>\alpha</tex> -equivalence'') {{---}} называется наименьшее соотношение эквивалентности на <tex>\Lambda</tex> такое что:
:<tex>P=_\alpha P</tex> для любого <tex>P</tex>
:<tex>\lambda x.P=_\alpha \lambda y.P[x:=y]</tex> если <tex>y \not\in FV(P)</tex>
Примеры выражений в этой нотации:
Переменная называется свободной, если ей соответствует число, которое больше
===+1===
Функция, прибавляющая <tex>1 </tex> к числу, должна принимать первым аргументом число.
Но число {{---}} функция двух аргументов. Значит, эта функция должна принимать три
аргумента: "число" <tex>n</tex>, которое хочется увеличить, функция, которую надо будет
===Комбинатор неподвижной точки===
Попробуем выразить в лямбда-исчислении какую-нибудь функцию, использующую рекурсию. НапрмерНапример, факториал.
<tex>\operatorname{fact} = \lambda x\ .\ \operatorname{if}\ (\operatorname{isZero}\ x)\ \bar 1\ (\operatorname{fact}\ (\operatorname{pred}\ x))</tex>
===Проверка на простоту===
<tex>\operatorname{isPrimeHelp}</tex> {{---}} принимает число, которое требуется проверить на простоту и то, на что его надо опытаться поделить, перебирая это от <tex>2 </tex> до <tex>p-1</tex>. Если на что-нибудь разделилось, то число {{---}} составное, иначе {{---}} простое.
<tex>\operatorname{isPrimeHelp'} =</tex><tex>\lambda f\ .\ \lambda p\ .\ \lambda i\ .\ \operatorname{if}\ (\operatorname{le}\ p\ i)\ \operatorname{true}\ (\operatorname{if}\ (\operatorname{isZero}\ (\operatorname{mod}\ p\ i))\ \operatorname{false}\ (f\ p\ (\operatorname{succ}\ i)))</tex>
