Если лямбда равно 0 то точка м

Добавил пользователь Владимир З.
Обновлено: 19.09.2024

Начнём мы с традиционного (но краткого) экскурса в историю. В 30-х годах прошлого века перед математиками встала так называемая проблема разрешения (Entscheidungsproblem), сформулированная Давидом Гильбертом. Суть её в том, что вот есть у нас некий формальный язык, на котором можно написать какое-либо утверждение. Существует ли алгоритм, за конечное число шагов определяющий его истинность или ложность? Ответ был найден двумя великими учёными того времени Алонзо Чёрчем и Аланом Тьюрингом. Они показали (первый — с помощью изобретённого им λ-исчисления, а второй — теории машины Тьюринга), что для арифметики такого алгоритма не существует в принципе, т.е. Entscheidungsproblem в общем случае неразрешима.

Так лямбда-исчисление впервые громко заявило о себе, но ещё пару десятков лет продолжало быть достоянием математической логики. Пока в середине 60-х Питер Ландин не отметил, что сложный язык программирования проще изучать, сформулировав его ядро в виде небольшого базового исчисления, выражающего самые существенные механизмы языка и дополненного набором удобных производных форм, поведение которых можно выразить путем перевода на язык базового исчисления. В качестве такой основы Ландин использовал лямбда-исчисление Чёрча. И всё заверте…

λ-исчисление: основные понятия

Синтаксис

В основе лямбда-исчисления лежит понятие, известное ныне каждому программисту, — анонимная функция. В нём нет встроенных констант, элементарных операторов, чисел, арифметических операций, условных выражений, циклов и т. п. — только функции, ~~только хардкор~~. Потому что лямбда-исчисление — это не язык программирования, а формальный аппарат, способный определить в своих терминах любую языковую конструкцию или алгоритм. В этом смысле оно созвучно машине Тьюринга, только соответствует функциональной парадигме, а не императивной.

Мы с вами рассмотрим его наиболее простую форму: чистое нетипизированное лямбда-исчисление, и вот что конкретно будет в нашем распоряжении.

Термы:

переменная:	x
лямбда-абстракция (анонимная функция):	λx.t , где x — аргумент функции, t — её тело.
применение функции (аппликация):	f x , где f — функция, x — подставляемое в неё значение аргумента

Применение функции левоассоциативно. Т.е. s t u — это тоже самое, что (s t) u
Аппликация (применение или вызов функции по отношению к заданному значению) забирает себе всё, до чего дотянется. Т.е. λx. λy. x y x означает то же самое, что λx. (λy. ((x y) x))
Скобки явно указывают группировку действий.

Процесс вычисления

Рассмотрим следующий терм-применение:

Существует несколько стратегий выбора редекса для очередного шага вычисления. Рассматривать их мы будем на примере следующего терма:

который для простоты можно переписать как

(напомним, что id — это функция тождества вида λx.x )

В этом терме содержится три редекса:

Недостатком стратегии вызова по значению является то, что она может зациклиться и не найти существующее нормальное значение терма. Рассмотрим для примера выражение

(λx.λy. x) z ((λx.x x)(λx.x x))

Ещё одна тонкость связана с именованием переменных. Например, терм (λx.λy.x)y после подстановки вычислится в λy.y . Т.е. из-за совпадения имён переменных мы получим функцию тождества там, где её изначально не предполагалось. Действительно, назови мы локальную переменную не y , а z — первоначальный терм имел бы вид (λx.λz.x)y и после редукции выглядел бы как λz.y . Для исключения неоднозначностей такого рода надо чётко отслеживать, чтобы все свободные переменные из начального терма после подстановки оставались свободными. С этой целью используют α-конверсию — переименование переменной в абстракции с целью исключения конфликтов имён.

Так же бывает, что у нас есть абстракция λx.t x , причём x свободных вхождений в тело t не имеет. В этом случае данное выражение будет эквивалентно просто t . Такое преобразование называется η-конверсией.

На этом закончим вводную в лямбда-исчисление. В следующей статье мы займёмся тем, ради чего всё и затевалось: программированием на λ-исчислении.

Вычет функции относительно изолированной особой точки. Основная теорема о вычетах

Вычетом функции $f(z)$ относительно изолированной особой точки $z_0$ называется коэффициент $c_$ при $(z-z_0)^$ в разложении в ряд Лорана функции $f(z)$ в окрестности $z_0$. $$ \mboxf(z_0) = c_. $$

Вычетом функции $f(z)$ относительно изолированной особой точки $z_0$ называется интеграл $$ \mboxf(z_0) =\frac1<2\pi i>\oint\limits_L f(z)\,dz, $$ где $L$ - произвольный контур в кольце $0<|z-z_0|

Основная теорема о вычетах (Коши)

Пусть функция $f(z)$ является аналитической всюду в замкнутой области $\overline D$, за исключением конечного числа изолированных особых точек $z_1,z_2,\dots,z_N$, лежащих внутри области $D$. Тогда $$ \oint\limits_L f(z)\,dz=2\pi i\sum\limits_^N \mboxf(z_k), $$ где $L$ - полная граница области $D$, проходимая в положительном направлении.

Вычисление вычетов в конечных особых точках

Вычет в устранимой особой точке равен $0$.

Если $z_0$ - существенно особая точка, то имеется только один способ вычисления вычета - разложение функции в ряд Лорана и определение коэффициента $c_$.

Для нахождения вычета в полюсе есть несколько приемов.

* Для простого полюса можно воспользоваться формулой: \begin\label \mboxf(z_0)=\lim\limits_ \Big(f(z)(z-z_0)\Big). \end * Для полюса порядка $m$: \begin\label \mboxf(z_0)=\frac1\lim\limits_ \frac>>\Big(f(z)(z-z_0)^m\Big). \end * Для простого полюса в случае функции $ f(z)=\frac$, где
$g(z)$ и $\varphi(z)$ - аналитические функции в окрестности точки $z_0$ и $g(z_0)\neq 0$, а для $\varphi(z)$ точка $z_0$ есть нуль первого порядка (для $f(z)$ же точка $z_0$ есть полюс первого порядка): \begin\label \mboxf(z_0)=\frac. \end

Строим контур интегрирования - окружность $|z-i|=2$. Подынтегральная функция имеет особые точки $z_1=0$, $z_2=1$ и $z_3=5i$. Точка $5i$ не лежит внутри контура интегрирования. Точка $z_1=0$ - полюс 2-го порядка, $z_2=1$ - полюс 1-го порядка. По основной теореме о вычетах получаем $$ I=2\pi i\big(\mboxf(0)+\mboxf(1)\big). $$ По формуле для вычисления вычета в полюсе 2-го порядка $$ \mboxf(0)=\frac1\lim\limits_\left( \left(\frac\right)'\right)= $$ $$ =\lim\limits_\frac =\frac. $$ Для простого полюса вычет равен $$ \mboxf(1) =\lim\limits_\frac =-\frac6. $$

Окончательно, $$ I=2\pi i\left(\frac-\frac6\right) =\pi\left(\frac5-\fraci\right). $$

О бесконечно удаленной точке $z=\infty$

Выберем любое $r \geqslant0$. Разложим функцию $f(z)$ по степеням $z$ во внешности круга $|z|> r$, которое иногда называют окрестностью бесконечно удаленной точки, $$ f(z)=\sum\limits_<-\infty>^\infty c_kz^k=F_1(z)+F_2(z) =\sum\limits_^\infty c_kz^k +\sum\limits_^\infty\frac>. $$ В этом случае $F_1(z)$ называют главной частью, а $F_2(z)$ - правильной частью.

В зависимости от поведения функции $f(z)$ в окрестности $z=\infty$ введена следующая классификация:

- Особенность в точке $z=\infty$ устранимая, если все $c_k=0$, $k=1,2,\ldots$, т.е. если $f(z)=F_2(z)$ для $|z|>r$. В этом случае $$ \lim\limits_f(z)=c_0. $$ Очевидно, что $$ \frac1<2\pi \mathbf i >\oint\limits_f(z)\,dz=-c_, $$ где $L^-$ - произвольный контур, ориентированный по часовой стрелке, содержащий внутри себя окружность $|z|=r$.

Можно считать, что точка $z=\infty$ находится внутри контура $L^-$. Если двигаться по контуру $L^-$ по часовой стрелке, то точка $z=\infty$ остается слева.

Видим, что в случае, когда $z=\infty$ - устранимая особая точка, то вычет не обязательно равен нулю!

- Точка $z=\infty$ есть полюс порядка $m$, если $f(z)=\sum\limits_^m c_k z^k+F_2(z)$ и $c_m\ne0$. В этом случае, очевидно, $$ \lim\limits_f(z)=\infty. $$

$$ \oint\limits_f(z)\,dz=\sum\limits_^\infty c_ \oint\limits_\frac+\sum\limits_^m c_k \oint\limits_z^k\,dz= $$ $$ =-c_\int\limits_L\fracz=-2\pi\mathbf i c_, $$ потому, что $\displaystyle\oint\limits_z^k\,dz=-\oint\limits_L z^k\,dz=0$, когда $k\ne-1$;

- Точка $z=\infty$ является существенно особой точкой, если $f(z)=\sum\limits_^\infty c_kz^k+F_2(z)$ и имеется бесконечное число чисел $c_k$, не равных нулю. В данном случае функция из-за первого слагаемого не имеет предела при $z\to\infty$. $$ \oint\limits_f(z)\,dz=\sum\limits_^\infty c_k \oint\limits_z^k\,dz=-2\pi \mathbf i c_. $$

Вычетом функции $f(z)$ в бесконечно удаленной точке называется $$ \mboxf(\infty)=\frac1<2\pi \mathbf i >\oint\limits_f(z)\,dz, $$ где $L^-$ - произвольный замкнутый контур, ориентированный по часовой стрелке, принадлежащий множеству $|z|>r$ (где функция $f(z)$ аналитична).

Кроме того, если $f(z)=\sum\limits_^\infty c_kz^k$ - ряд Лорана функции во внешности окружности $|z|=r$, то $$ \mboxf(\infty)=-c_. $$

Теорема о сумме вычетов

Пусть функция $f(z)$ аналитична на всей плоскости $z$ за исключением конечного числа изолированных особых точек $z_1,z_2,\dots,z_N$. Тогда сумма всех вычетов этой функции, включая вычет в бесконечно удаленной точке, равна нулю: $$ \sum\limits_^N\mboxf(z_k)+\mboxf(\infty)=0. $$

Р е ш е н и е.
Все особые точки $z_k=\sqrt[4]$, $\sqrt[3]$ лежат в круге $|z|=2$. Вычисление вычетов в этих точках довольно затруднительно, поэтому воспользуемся формулой $$ I=2\pi i\sum\limits_^\infty \mboxf(z_k)=-2\pi i\mboxf(\infty). $$ Представим функцию в виде $$ \frac><4z^6\left(1+\cfrac1\right)^2z^ \left(1-\cfrac1\right)^3>= $$ $$ =\frac4\left(1-\frac1+\frac1-\dots\right)^2 \left(1+\frac1+\frac1\right)^3=\frac4-\frac1 +\dots\ . $$

Тогда $\mboxf(\infty)=\dfrac14$ и интеграл равен $-2\pi i\mboxf(\infty)=-\dfrac<\pi i>2$.

О т в е т: $-\dfrac<\pi i>2$.

Вычисление определенных интегралов с помощью вычетов

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

I. Интеграл вида $I=\int\limits_0^<2\pi>R(\cos,\sin)\,dx,$

где $R(u,v)$ - рациональная функция двух переменных.

Подстановка $z=e^$ даст для $$ \begin \cos\theta=\dfrac12\left(e^+e^\right) =\dfrac12\left(z+\dfrac1z\right), \\ \sin\theta=\dfrac1\left(e^-e^\right) =\dfrac2\left(z-\dfrac1z\right), \\ d\theta=\dfrac \end $$ и превратит вещественный интеграл в комплексный. При изменении $\theta$ от $0$ до $2\pi$ комплексная переменная пробегает замкнутый контур - окружность $|z|=1$ в положительном направлении. Окончательно интеграл примет вид $$ I=\frac1i\oint\limits_<|z|=1>F\left(z+\frac1z,z-\frac1z\right) \frac\,. $$

Вычислить интеграл $$ \int\limits_0^<2\pi>\frac,\quad a>1. $$

Р е ш е н и е.
Положим $e^=z$. При изменении $x$ от 0 до $2\pi$ переменная $z$ пробегает окружность $|z|=1$ в положительном направлении. Выразим $$ \cos x=\frac12\left(e^+e^\right)=\frac, $$ и $$ dz=ie^dx=izdx,\quad\hbox\quad dx=\frac. $$ Тогда $$ I=\oint\limits_<|z|=1>\frac =\frac2i\oint\limits_<|z|=1>\frac. $$

II. Несобственный интеграл от рациональной функции $I=\int\limits_<-\infty>^\infty R(x)\,dx=\int\limits_<-\infty>^\infty \frac\,dx$,

где $P_m(x)$ и $Q_n(x)$ — многочлены степеней $m$ и $n$ соответственно.

Если знаменатель $Q_n(x)$ не имеет нулей на действительной оси, и $n\geqslant m+2$, тогда \begin \int\limits_<-\infty>^\infty R(x)\,dx = 2\pi \mathbf i \sum\limits_^n \mboxR(z_k), \end где вычеты берутся во всех полюсах $z_k$ функции $R(z)$, расположенных в верхней полуплоскости $\mboxz>0$.

Вычислить интеграл $ I=\int\limits_<-\infty>^\infty\frac.$

Р е ш е н и е.
Аналитическое продолжение подынтегральной функции в верхнюю полуплоскость, а именно функция $$ f(z)=\frac1, $$ удовлетворяет всем условиям, относящимся к вычислению интегралов с помощью вычетов. Особыми точками функции в верхней полуплоскости являются точки $$ z_k=e^<\tfrac4(2k+1)>,\quad k=0,1, $$ причем обе эти точки - полюсы 1-го порядка. Поэтому $$ I=2\pi i\sum\limits_^1 \mboxf(z_k)=\frac<\pi\sqrt2>2. $$

III. Несобственные интегралы вида $I=\int\limits_<-\infty>^\infty R(x)\cos<\lambda x>\,dx, \,\, I=\int\limits_<-\infty>^\infty R(x)\sin<\lambda x>\,dx$,

где $R(x)=P_m(x)/Q_n(x)$ - правильная рациональная дробь, не имеющая особых точек на действительной оси. Тогда \begin \int\limits_<-\infty>^\infty R(x)\cos<\lambda x>\,dx = \mbox\left( 2\pi \mathbf i \sum\limits_ \mboxR(z_k)e^<\mathbf i \lambda z_k>\right), \end \begin \int\limits_<-\infty>^\infty R(x)\sin<\lambda x>\,dx = \mbox\left( 2\pi \mathbf i \sum\limits_ \mboxR(z_k)e^<\mathbf i \lambda z_k>\right), \end где вычеты берутся во всех полюсах $z_k$ функции $R(z)$, расположенных в верхней полуплоскости $\mboxz>0$.

Интегралы вычисляются с помощью леммы Жордана:

Лемма Жордана

Пусть функция $f(z)$ аналитична в полуплоскости $\mboxz>0$, за исключением конечного числа изолированных особых точек, и пусть $M(R)$ есть максимум модуля $f(z)$ на полуокружности $\gamma_=\: |z|=R, \mbox z >0 \>$.
Если $M(R)\to0$ при $R\to\infty$, то для любого действительного числа $\lambda>0$ $$ \int\limits_<\gamma_R>f(z)e^<\mathbf i \lambda z>\,dz\to0\quad\hbox\quad R\to\infty, $$

Вычислить интеграл $ I=\int\limits_<-\infty>^\infty\frac\,dx,\, a>0,\ \alpha>0$.

Р е ш е н и е.
Чтобы иметь возможность воспользоваться леммой Жордана, заметим, что в силу формулы Эйлера $$ I=\mboxI_1 =\mbox\int\limits_<-\infty>^\infty \frac> \,dx. $$

Аналитическое продолжение подынтегральной функции интеграла $I_1$ - функция $\dfrac>$ имеет в верхней полуплоскости единственную особую точку $z_1=ia$, являющуюся простым полюсом. Поэтому по основной теореме о вычетах $$ I_1=2\pi \mathbf i \mbox\left(\frac>\Big|_ \right)=\frac\pie^\quad\hbox\quad I=\frac\pie^. $$

Логарифмической производной функции $f(z)$ называется производная ее логарифма $\left(\ln \right)'= \frac$.

Пусть $z_0$ - нуль порядка $n$, $z_1$ - полюс порядка $p$. Запишем разложения в ряд Лорана логарифмической производной в окрестности нуля и полюса функции $f(z)$. $$ \left(\ln \right)'= \frac+b_1+b_2(z-z_0)+\dots \quad \Rightarrow $$ $n$-кратный нуль функции $f(z)$ является для логарифмической производной простым полюсом, причем вычет логарифмической производной в этой точке равен кратности нуля, то есть $n$. $$ \left(\ln \right)'= \frac+c_1+c_2(z-z_1)+\dots \quad \Rightarrow $$ $p$-кратный полюс функции $f(z)$ является для логарифмической производной простым полюсом, причем вычет логарифмической производной в этой точке равен порядку полюса, взятому с обратным знаком, то есть $-p$.

Логарифмическим вычетом функции $f(z)$ в точке $z=a$ называется вычет ее логарифмической производной $ \frac$ в этой точке, т.е. значение $$ \mbox\frac=\frac<2\pi \mathbf i>\oint\limits_ \fracdz, $$ где в качестве контура $L$ интегрирования можно взять любую окружность с центром в точке $z=a$, целиком лежащую в указанной проколотой окрестности этой точки.

Если $f(z)$ является аналитической функцией на замкнутом контуре $L$ и не имеет нулей на этом контуре, то значение $$ \mbox \frac=\frac<2\pi \mathbf i>\oint\limits_ \fracdz $$ называют логарифмическим вычетом функции $f(z)$ относительно контура $L$.

Теорема о логарифмическом вычете

Логарифмический вычет многочлена $P_n(z)$ степени $n$ относительно контура $L$, на котором нет нулей $P_n(z)$, равен числу нулей многочлена (с учетом их кратности) внутри контура.

Пусть непостоянная функция $f(z)$ аналитична всюду в односвязной области $D$ и на ее границе - кусочно-гладком контуре $L$, кроме, возможно, некоторого конечного числа полюсов. Пусть также функция имеет конечное число нулей, причем на контуре $L$ нет ни нулей, ни полюсов функции. Тогда приращение аргумента функции $f(z)$ при обходе в положительном направлении контура $L$ равно произведению $2\pi$ на разность числа нулей и полюсов функции $f(z)$, расположенных в области $D$, причем каждый нуль следует считать сколько раз, какова его кратность, а каждый полюс - каков его порядок. $$ \Delta_L\arg f(z)=2\pi(N-P), $$ $$ N=q_1+q_2+\ldots+q_m, \quad P=p_1+p_2+\ldots+p_k, $$ $q_i$ - кратность нуля $a_i$, $i=1,\ldots,m$, $p_j$ - кратность полюса $b_j$, $j=1,\ldots,k$.

Пусть функции $f(z)$ и $\varphi(z)$ являются аналитическими в замкнутой области $D$, причем на границе $C$ этой области имеет место неравенство: $|f(z)|_>|\varphi(z)|_$. Тогда полное число нулей (с учетом их кратности) в $D$ функции $F(z)=f(z)+\varphi(z)$ равно полному числу нулей (с учетом их кратности) функции $f(z)$.

Пусть $f(z)=-4z^5$, $\varphi(z)=z^8+z^2-1$. Граница $C$ заданной области - единичный круг $|z|=1$.

Выполнены все условия теоремы Руше. Функция $f(z)$ имеет корень $z=0$ кратности $5$, лежащий в $|z|

Найти число корней уравнения $z^4-8z+10=0$ в кольце 1<|z|<3

Пусть $F(z)=f(z)+\varphi(z)$, где $f(z)=10$, $\varphi(z)=z^4-8z$. На границе $C$ единичного круга имеем: $$ |z|=1: \,\, |f(z)|=10, |\varphi(z)|\leqslant|z|^4+8|z|=9\,\, \Rightarrow \,\, |f(z)>|\varphi(z)|. $$ Выполнены все условия теоремы Руше. Функция $f(z)$ в области $|z|

Лямбда-исчисление — это формальная система в математической логике для выражения подсчетов на основе абстракции и применения функций с использованием привязки и подстановки переменных. Это универсальная модель, которую можно применять для проектирования любой машины Тьюринга. Впервые введена лямбда-исчисления Черчем, известным математиком, в 1930-х годах.

Система состоит из построения лямбда-членов и выполнения над ними операций сокращения.

Пояснения и приложения

Греческая буква lambda (λ) используется в лямбда-выражениях и лямбда-терминах для обозначения связывания переменной в функции.

Лямбда-исчисление может быть нетипизировано или типизировано. В первом варианте функции могут быть применены только в том случае, если они способны принимать данные этого типа. Типизированные лямбда-исчисления слабее, могут выражать меньшее значение. Но, с другой стороны, они позволяют доказывать больше вещей.

Одной из причин того, что существует много разных типов — это желание ученых сделать больше, не отказываясь от возможности доказывать сильные теоремы лямбда-исчислений.

Система находит применение во многих различных областях математики, философии, лингвистики, и компьютерных наук. В первую очередь, лямбда-исчисления — это расчет, который сыграл важную роль в развитии теории языков программирования. Именно стили функционального создания реализуют системы. Они также являются актуальной темой исследований в теории этих категорий.

Для чайников

Лямбда-исчисление была введена математиком Алонзо Черчем в 1930-х годах в рамках исследования основ науки. Первоначальная система была показана как логически несовместимая в 1935 году, когда Стивен Клин и Дж. Б. Россер разработали парадокс Клини-Россера.

В последствии, в 1936 году Черч выделил и опубликовал только ту часть, которая имеет отношение к расчетам, то, что сейчас называется нетипизированным лямбда-исчислением. В 1940 он также представил более слабую, но логически непротиворечивую теорию, известную как система простого типа. В свое работе он объясняет всю теорию простым языком, поэтому, можно сказать, что Черч опубликовал лямбду исчисления для чайников.

До 1960-х годов, когда выяснилось его отношение к языкам программирования, λ стала лишь формализмом. Благодаря применениям Ричарда Монтегю и других лингвистов в семантике естественного языка, исчисление стало занимать почетное место как в лингвистике, так и в информатике.

Происхождение символа

Введение в лямбда исчисление

Система состоит из языка терминов, которые выбираются определенным формальным синтаксисом, и набора правил преобразования, которые позволяют манипулировать ими. Последний пункт можно рассматривать как эквациональную теорию или как операционное определение.

Все функции в лямбда-исчислении являются анонимными, то есть не имеющими имен. Они принимают только одну входную переменную, при этом каррирование используется для реализации графиков с несколькими непостоянными.

Лямбда-термины

Следующие три правила дают индуктивное определение, которое можно применять для построения всех синтаксически допустимых понятий:

Переменная x сама по себе является действительным лямбда-термином:

если T это ЛТ, и x непостоянная, то (lambda xt) называется абстракцией.
если T, а также s понятия, то (TS) называется приложением.

Ничто другое не является лямбда-термином. Таким образом, понятие действительно тогда и только тогда, когда оно может быть получено повторным применением этих трех правил. Тем не менее некоторые скобки могут быть опущены в соответствии с другими критериями.

Определение

Лямбда-выражения состоят из:

переменных v 1, v 2. v n.
символов абстракции 'λ' и точки '.'
скобок ().

Множество Λ, может быть определено индуктивно:

Если x переменная, то x ∈ Λ;
x непостоянная и M ∈ Λ, то (λx.M) ∈ Λ;
M, N ∈ Λ, то (MN) ∈ Λ.

Обозначение

Чтобы сохранить нотацию лямбда-выражений в незагроможденном виде, обычно применяются следующие соглашения:

Внешние скобки опущены: MN вместо (MN).
Предполагается, что приложения остаются ассоциативными: взамен ((MN) P) можно написать MNP.
Тело абстракции простирается дальше вправо: λx.MN означает λx. (MN), а не (λx.M) N.
Сокращается последовательность абстракций: λx.λy.λz.N можно λxyz.N.

Свободные и связанные переменные

Оператор λ соединяет свою непостоянную, где бы он ни находился в теле абстракции. Переменные, попадающие в область, называются связанными. В выражении λ x. М, часть λ х часто называют связующим. Как бы намекая, что переменные становятся группой с добавлением Х х к М. Все остальные неустойчивые называются свободными.

Множество свободных переменных M обозначается как FV (M) и определяется рекурсией по структуре терминов следующим образом:

FV (x) = , где x - переменная.
FV (λx.M) = FV (M) \ .
FV (MN) = FV (M) ∪ FV (N).

Формула, которая не содержит свободных переменных, называется закрытой. Замкнутые лямбда-выражения также известны как комбинаторы и эквивалентны терминам в комбинаторной логике.

Сокращение

Значение лямбда-выражений определяется тем, как они могут быть сокращены.

Существует три вида урезания:

α-преобразование: изменение связанных переменных (альфа).
β-редукция: применение функций к своим аргументам (бета).
η-преобразование: охватывает понятие экстенсиональности.

Здесь речь также идет о полученных эквивалентностях: два выражения являются β-эквивалентными, если они могут быть β-преобразованы в одно и то же составляющее, а α / η-эквивалентность определяется аналогично.

Термин redex, сокращение от приводимого оборота, относится к подтемам, которые могут быть сокращены одним из правил. Лямбда исчисление для чайников, примеры:

(λ x.M) N является бета-редексом в выражении замены N на x в M. Составляющее, к которому сводится редекс, называется его редуктом. Редукция (λ x.M) N есть M [x: = N].

Если x не является свободной в M, λ х. М х также ет-REDEX с регулятором М.

α-преобразование

Альфа-переименования позволяют изменять имена связанных переменных. Например, λ x. х может дать λ у. у. Термины, которые отличаются только альфа-преобразованием, называются α-эквивалентными. Часто при использовании лямбда-исчисления α-эквивалентные считаются взаимными.

Точные правила для альфа-преобразования не совсем тривиальны. Во-первых, при данной абстракции переименовываются только те переменные, которые связаны с одной и той же системой. Например, альфа-преобразование λ x.λ x. x может привести к λ y.λ x. х, но это может не ввергнуть к λy.λx.y Последний имеет иной смысл, чем оригинал. Это аналогично понятию программирования затенения переменных.

Во-вторых, альфа-преобразование невозможно, если оно приведет к захвату непостоянной другой абстракцией. Например, если заменить x на y в λ x.λ y. x, то можно получить λ y.λ y. у, что совсем не то же самое.

В языках программирования со статической областью видимости альфа-преобразование можно использовать для упрощения разрешения имен. При этом следя за тем, чтобы понятие переменной не маскировало обозначение в содержащей области.

В нотации индекса Де Брюйна любые два альфа-эквивалентных термина синтаксически идентичны.

Замена

Изменения, написанные Е [V: = R], представляют собой процесс замещения всех свободных вхождений переменной V в выражении Е с оборотом R. Подстановка в терминах λ определяется лямбдой исчисления рекурсии по структуре понятий следующим образом (примечание: x и y - только переменные, а M и N - любое λ-выражение).

y [x: = N] ≡ y, если x ≠ y

(M 1 M 2) [x: = N] ≡ (M 1 [x: = N]) (M 2 [x: = N])

(λ x.M) [x: = N] ≡ λ x.M

(λ y.M) [x: = N] y λ y. (M [x: = N]), если x ≠ y, при условии, что y ∉ FV (N).

Для подстановки в лямбда-абстракцию иногда необходимо α-преобразовать выражение. Например, неверно, чтобы (λ x. Y) [y: = x] приводило к (λ x. X), потому что замещенный x должен был быть свободным, но в итоге был связанным. Правильная замена в этом случае (λ z. X) с точностью до α-эквивалентности. Стоит обратить внимание, что замещение определяется однозначно с верностью до лямбды.

β-редукция

Бета-редукция отражает идею применения функции. Бета-восстановительный определяется в терминах замещения: ((X V. E) Е ') является Е [V: = Е'].

Например, предполагая некоторое кодирование 2, 7, ×, имеется следующее β-уменьшение: ((λ n. N × 2) 7) → 7 × 2.

Бета-редукция может рассматриваться как то же самое, что и концепция локальной сводимости при естественной дедукции через изоморфизм Карри – Ховарда.

η-преобразование

Эта-конверсия выражает идею экстенсиональности, которая в этом контексте заключается в том, что две функции равны тогда, когда они дают одинаковый результат для всех аргументов. Эта конвертация обменивает между λ x. (F x) и f всякий раз, когда x не кажется свободным в f.

Данное действие может рассматриваться как то же самое, что и концепция локальной полноты в естественной дедукции через изоморфизм Карри – Ховарда.

Нормальные формы и слияние

Для нетипизированного лямбда-исчисления β-редукция как правило переписывания не является ни сильно нормализующей, ни слабо.

Тем не менее можно показать, что β-редукция сливается при работе до α-преобразования (т. е. можно считать две нормальные формы равными, если возможно α-преобразование одной в другую).

Поэтому и сильно нормализующие члены, и слабо налаживающие понятия имеют единственную нормальную форму. Для первых терминов любая стратегия сокращения гарантированно приведет к типичной конфигурации. Тогда как для слабо нормализующих условий некоторые стратегии сокращения могут не найти ее.

Дополнительные методы программирования

Существует большое количество идиом создания для лямбда-исчисления. Многие из них были первоначально разработаны в контексте использования систем в качестве основы для семантики языка программирования, эффективно применяя их в качестве создания низкого уровня. Поскольку некоторые стили включают лямбда-исчисление (или что-то очень похожее) в качестве фрагмента, эти методы также находят применение в практическом создании, но затем могут восприниматься как неясные или чужие.

Именованные константы

В лямбда-исчислении библиотека принимает форму набора ранее определенных функций, в которой термины являются просто конкретными константами. Чистое исчисление не имеет понятия именованных неизменных, поскольку все атомные лямбда-термины являются переменными. Но их также можно имитировать, выделив непостоянную в качестве имени константы, используя лямбда-абстракцию для связывания этой изменчивой в основной части, и применить эту абстракцию к намеченному определению. Таким образом, если использовать f для обозначения M в N, можно сказать,

Авторы часто вводят синтаксическое понятие, такое как let, чтобы разрешить писать все в более интуитивном порядке.

Заметным ограничением этого let является то, что имя f не определено в M, поскольку M находится вне области привязки лямбда-абстракции f. Это означает, что атрибут рекурсивной функции не может использоваться как M с let. Более продвинутая синтаксическая конструкция letrec, которая позволяет писать рекурсивные определения функций в этом стиле, вместо этого дополнительно использует комбинаторы с фиксированной точкой.

Печатные аналоги

Данный тип является типизированным формализмом, который использует символ для обозначения анонимной функции абстракция. В этом контексте типы обычно являются объектами синтаксической природы, которые присваиваются лямбда-терминам. Точная натура зависит от рассматриваемого исчисления. С определенной точки зрения, типизированные ЛИ можно рассматривать как уточнения нетипизированного ЛИ. Но с другой стороны, их также можно считать более фундаментальной теорией, а нетипизированное лямбда-исчисление — особым случаем только с одним типом.

Типизированные ЛИ являются основополагающими языками программирования и основой функциональных, таких как ML и Haskell. И, более косвенно, императивных стилей создания. Типизированные лямбда-исчисления играют важную роль в разработке систем типов для языков программирования. Здесь типизируемость обычно захватывает желательные свойства программы, например, она не вызовет нарушения доступа к памяти.

Типизированные лямбда-исчисления тесно связаны с математической логикой и теорией доказательств через изоморфизм Карри – Говарда, и их можно рассматривать как внутренний язык классов категорий, например, который просто является стилем декартовых замкнутых.

В очередном опусе Итана Сигеля резанула фраза

Пронаблюдав за удалёнными сверхновыми и измерив, как Вселенная расширялась миллиарды лет, астрономы обнаружили нечто удивительное, загадочное и неожиданное.

By observing distant supernovae and measuring how the Universe had expanded over billions of years, astronomers discovered something remarkable, puzzling and entirely unexpected

О какой неожиданности может идти речь? Там ведь совершенно шикарная история длиной в 80 лет с яркими открытиями и закрытиями. История про то, как на самом деле делается настоящая наука. История скорее про физиков, чем про физику.

О чём вообще весь сыр-бор?

Первую версию Общей Теории Относительности (ОТО) Альберт Эйнштейн представил публике 25 ноября 1915 года. В оригинале уравнения ОТО Эйнштейна выглядели вот так:

или, в современной записи, вот так:

Для неумеющего в тензоры читателя понятнее уравнение (1) в оригинальной записи Эйнштейна. Там написано, что энергия-импульс материи G равен кривизне пространства R плюс тензор Риччи S. (Этот самый тензор Риччи тоже есть кривизна, только в более другой форме).
Сейчас, решая уравнение ОТО, энергию-импульс обычно считают известным, а ищут как раз кривизну. Поэтому в современной записи стороны уравнения поменяли местами. Заодно поменяли буковки: G → T, S → R_μν.

Откуда есть пошла лямбда

Но физика — это вам не математика. Здесь нельзя взять формулу и напихать в неё добавочных слагаемых просто так. Нужно иметь очень веские основания, и теоретические, и экспериментальные.

Хотя ниже вы увидите, насколько мало Эйнштейн знал о Вселенной в те годы, но тогда, в 1916, такие основания у него были. Альберт Германович точно знал, что звёзды не попадали друг на друга и совершенно не собираются этого делать в обозримом будущем. Однако, в ОТО-1915 было только притяжение, которое нужно было чем-то сбалансировать.

Первое физическое толкование смысла лямбды

В такой трактовке ненулевое значение Λ означает, что наша Вселенная искривлена сама по себе, в том числе и при отсутствии какой-либо гравитации. Ну, вот такой нам достался мир. Однако, большинство физиков в это не верят, и считают, что у наблюдаемого искривления должна быть какая-то внутренняя причина. Какая-то неведомая доселе фигня, которую можно открыть.

На сегодняшний день измеренная кривизна пространства Вселенной таки равна нулю, но с очень паршивой точностью, порядка 0.4%. И не очень-то видно способов эту точность улучшить.
С измерениями кривизны есть две концептуальные проблемы.

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

Допустим, у нас есть как-то измеренные координаты объектов, плюс пачка фотографий этих объектов в разных ракурсах (снятых из разных точек). Тогда мы можем вычислить кривизну пространства. Например, гравитация Солнца отклоняет пролетающий мимо свет далёких звёзд. Во время солнечных затмений это отклонение можно измерить экспериментально и сравнить с предсказаниями ОТО.

Теперь наоборот: допустим, мы знаем кривизну пространства, и у нас есть пачка фотографий. Тогда, если кривизна достаточно хорошая, без чёрных дыр и т.п. — мы можем вычислить координаты объектов на фото. Именно так работают наши глаза, точнее мозги, когда вычисляют расстояние до объектов по двум фоткам с разных точек.

Поэтому измерить кривизну наблюдаемой Вселенной в целом мы можем только из очень окольных соображений.

Вселенная Фридмана

Meanwhile in Russia, не смотря на войны и революции, над теорией ОТО бился прапорщик (и по совместительству профессор) Александр Александрович Фридман. Он рассмотрел все варианты лямбд и выяснил следующее:

При Λ < 0 имеют место лишь силы притяжения, как гравитационные, так и вызванные кривизной ~~впуклого~~вогнутого пространства. Рано или поздно звёзды и галактики в таком мире таки попадают друг на друга. Причём конец будет неожиданно быстрым и очень горячим.

Но самое интересное происходит при Λ = 0. Здесь всё зависит от начальных условий — т.е. координат и скоростей конкретных галактик. Возможны три варианта: большое сжатие, большой разлёт и стационарный вариант, когда галактики разлетаются, но с относительно небольшими скоростями и без ускорения.

Сегодня вышеописанные ситуации называются космологическими решениями Фридмана.

Статьи Фридмана 1922 и 1924 годов отменяли необходимость в лямбда-члене, из-за чего поначалу были приняты Эйнштейном в штыки.

За свою работу Фридман вполне мог претендовать на Нобелевку.

Летом 1925 он женился, поехал в свадебное путешествие в Крым, съел там немытую грушу, заразился тифом и в сентябре — умер.

И да, статья Итана про примерно такой график (конкретно на этом учтены данные на 2010 год):

Здесь по горизонтали отложено z — это красное смещение, по вертикали наблюдаемая яркость сверхновых особого типа Ia, которые всегда выделяют одно и то же количество энергии. Вообще, это два способа измерения одного и того же расстояния, но, так сказать, в разные моменты времени.

Серые палки — наблюдавшиеся события с их погрешностью измерений. Синим пунктиром отложено предсказание при Λ = 0, красной линией — аппроксимация фактически наблюдаемых значений. Отклонение красной линии от прямой означает, что Вселенная расширяется ускоренно. Но Эйнштейн об этом так и не узнал.

Вселенная Каптейна

Перейдём к экспериментальной части.

Голландский астроном Якобус Корнелиус Каптейн открыл звезду Каптейна в 1897, после чего приступил к opus magnum всей своей жизни. Объединяя огромное количество наблюдений разных обсерваторий, он попытался создать первую карту Вселенной. По его карте выходило, что вселенная имеет форму вращающегося (sic!) диска крышесносящего по тем временам размера 40000 световых лет, причём Солнце находится отнюдь не в центре, а вполне себе на задворках. Закончена и опубликована эта работа была только в 1922.

Для понимания уровня тогдашних знаний: то, что Каптейн считал невероятно огромной Вселенной, сегодня считается совершенно рядовой, ничем не примечательной среди миллиардов таких же… галактикой Млечный Путь. Тем не менее, заслуга Каптейна в том, что он открыл её вращение и приблизительно вычислил её центр.

Наблюдения Хаббла (астронома, а не телескопа)

Статью со своими открытиями, из которой следовало, что Вселенная значительно больше, чем наш Млечный путь, Хаббл представил американскому астрономическому обществу первого января 1925. За что и был освистан ~~страдающими от похмелья~~ коллегами, едва свыкшимися с расстояниями Каптейна.

Хаббл не унимался и прикрутил к телескопу ещё и спектрометр. Анализируя красное смещение галактик, он выяснил, что галактики разбегаются, а Вселенная, соответственно, расширяется. Заодно он открыл закон имени себя с константой имени себя (впрочем, закон был предсказан Леметром), и описал всё это в статьях к концу 20-ых годов. Согласно его наблюдениям, оказалась верна модель Фридмана для Λ = 0.

Это выбило из-под лямбды теперь уже и экспериментальные основания её существования.

Здесь ещё нужно упомянуть, что первоначальные оценки Хаббла были очень уж неточными и показывали возраст Вселенной порядка 2 миллиардов лет. Позднее это войдёт в противоречие с данными геофизиков, которые при помощи радиоизотопного анализа оценят возраст Земли в несколько миллиардов лет, и десятилетиями будет сильнейшей головной болью для физиков-космологов.

Стационарная Вселенная Хойла

С начала 30-ых годов вопрос с лямбдой считался решённым, и из мейнстримных физиков ей никто толком не занимался. Одним из редких исключений, рискнувших попереть супротив самого Эйнштейна, стал британец Фред Хойл.

Речь пойдёт о гелии. Этот элемент феноменально инертен и не хочет ни с чем реагировать. Причём не только химически, но и физически тоже, если мы говорим про гелий-4. Его ядро — альфа частица — имеет пиковую энергию связи на нуклон в своей области. см. рис из какого-то реферата:

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

Возникал резонный вопрос: а откуда, собственно, взялись химические элементы тяжелее гелия?

Ближайшее ядро, в которое может превращаться гелий-4, это углерод-12. Но для этого нужно объединить три альфа-частицы.

Проблема в том, что вероятность столкновения трёх альфа-частиц одновременно слишком мала. А двухшаговый процесс (сначала сталкиваются две частицы, потом очень быстро, пока они не разлетелись обратно на две альфа-частицы, в них врезается ещё одна), в принципе, возможен, но расчёты Эдвина Солпитера показывали, что такой процесс идёт слишком вяло, чтобы производить существенные количества углерода.

Однако, по расчётам Хойла выходило, что при наличии такого уровня в три-альфа процессе наступает резонанс, и звёзды — красные гиганты производят достаточно много углерода для нашего существования.

Удивительно, но американцы решили провести небольшой эксперимент на своём ускорителе. И да — триумфально нашли нужный энергетический уровень на 7.65 МэВ, который физики-ядерщики всего мира почему-то проглядели во всех предыдущих экспериментах.

Сегодня такое возбуждённое состояние углерода-12, когда три альфа-частицы фактически выстраиваются по линии, называется хойловским. Соответствующая статья Хойла, Фаулера и супругов-астрономов Джефри и Маргерит Бёрбиджей является краеугольным камнем современных теорий звёздного нуклеосинтеза и настолько часто цитируется, что обозначается просто B²FH, без ссылок и расшифровок.

И — да, на сегодня это чуть ли не единственное известное успешное предсказание на основе антропного принципа.

Однако, из квантовых флуктуаций постоянно рождается новое вещество, причём так, что средняя плотность материи остаётся одинаковой. Расчёты показывают, что в одном кубическом километре пространства должен рождаться всего-навсего один протон раз в 300000 лет (а так же один электрон или что-то типа того для сохранения электрического заряда). Прекрасное число, чтобы исключить любую возможность какой-либо экспериментальной проверки!

Теория стационарной Вселенной серьёзно рассматривалась как альтернатива теории Большого Взрыва в 50-х и начале 60-х. Но экспериментальное открытие в 1964 году предсказанного ТББ реликтового излучения поставило на ней крест.

За статью B²FH дали Нобелевку. Но только Фаулеру, который распорядился провести десятидневный эксперимент. Ни супругам Бёрбиджам, проводившим длительные астрономические наблюдения и собственно написавшим статью, ни автору идеи Хойлу нобелевку не дали — за упорствование в космологической ереси.

Квантовая лямбда

Вернёмся к уравнению ОТО.

Слева (в современной записи) стоит кривизна пространства, сиречь гравитация по ОТО. Справа — тензор энергии-импульса. Под этим тензором стоит жутко сложный матан, но суть в следующем: там учтена вся-вся-вся материя Вселенной во всех видах и состояниях. И обычное вещество, и всякие хитрые частицы, и все виды излучений (кроме гравитации, которая слева).

Теперь мысленно перенесём лямбду вправо. В такой записи это будет не дополнительная кривизна, а какая-то неучтённая энергия (замечу, отрицательная, раз уж мы считаем лямбду положительной). И здесь просматриваются две возможности.

Первая гипотеза состоит в том, что лямбда — это энергия собственно вакуума. Звучит диковато, но на самом деле вполне согласуется с квантовой механикой. Возьмём кусок пространства и уберём из него всё, что хотя бы в принципе можно убрать. Уберём всё вещество, все частицы и все волны, независимо от их природы. Останутся только физические поля в невозмущённом состоянии. Полный штиль.

Так вот, у некоторых полей (например, Хиггсовских) в пустоте ненулевое значение. И теоретически у них есть некоторая энергия. Кроме того, в силу принципа неопределённости у любых полей есть квантовые флуктуации — и они тоже имеют некоторую энергию.

Вместо заключения

Читайте также: