Неразрешимость задачи вывода типов в языке с зависимыми типами

[math]\lambda\Pi[/math]-исчисление

Определение:

Множество термов (англ. term) рекурсивно определяется следующей грамматикой: [math]\displaystyle T ::= \mathrm{Type} \mid \mathrm{Kind} \mid x \mid \left(T\ T\right) \mid \lambda x : T . T \mid \Pi x : T . T[/math]. Термы [math]\mathrm{Type}[/math] и [math]\mathrm{Kind}[/math] называются сортами (англ. sorts), [math]x[/math] — переменными (англ. variables), [math](t\ t')[/math] — применениями (англ. applications), [math]\lambda x : t . t'[/math] — абстракциями (англ. abstractions), [math]\Pi x : t . t'[/math] — произведениями (англ. products). Обозначение [math]t \rightarrow t'[/math] используется вместо [math]\Pi x : t . t'[/math], если [math]x[/math] не входит свободно в [math]t'[/math].

Пусть есть термы [math]t[/math] и [math]t'[/math] и переменная [math]x[/math]. Записью [math]t\left[x \leftarrow t'\right][/math] обозначается терм, полученный заменой [math]t'[/math] на [math]t[/math] в [math]x[/math]. Запись [math]t =_\beta t'[/math] означает, что термы [math]t[/math] и [math]t'[/math] [math]\beta[/math]-эквивалентны.

Определение:

Контекст (англ. context) это список пар [math]x : T[/math], где [math]x[/math] — переменная, [math]T[/math] — терм.

Определение:

Правила вывода для нашего исчисления: [math] \displaystyle \frac{}{\left[ \right] \in \mathrm{WF}} \text{,} \vspace{3mm} \\ \frac{\Gamma \vdash T : s}{\Gamma\left[x : T\right] \in \mathrm{WF}} \text{,} \vspace{3mm} \\ \frac{\Gamma \in \mathrm{WF}}{\Gamma \vdash \mathrm{Type} : \mathrm{Kind}} \text{,} \vspace{3mm} \\ \frac{\Gamma \in \mathrm{WF} \qquad x : T \in \Gamma}{\Gamma \vdash x : T} \text{,} \vspace{3mm} \\ \frac{\Gamma \vdash T : \mathrm{Type} \qquad \Gamma\left[x : T\right] \vdash T' : x}{\Gamma \vdash \Pi x : T . T' : s} \text{,} \vspace{3mm} \\ \frac{\Gamma \vdash \Pi x : T . T' : s \qquad \Gamma\left[x : T\right] \vdash t : T'}{\Gamma \vdash \lambda x : T . t : \Pi x : T . T'} \text{,} \vspace{3mm} \\ \frac{\Gamma \vdash t : \Pi x : T . T' \qquad \Gamma \vdash t' : T}{\Gamma \vdash \left(t\ t'\right) : T'\left[x \leftarrow t'\right]} \text{,} \vspace{3mm} \\ \frac{\Gamma \vdash T : s \qquad \Gamma \vdash T' : s \qquad \Gamma \vdash t : T \qquad T =_\beta T'}{\Gamma \vdash t : T'} \text{;} [/math] где [math]s ::= \mathrm{Type} \mid \mathrm{Kind}[/math], а [math]\mathrm{WF}[/math] — множество корректных грамматик. Терм [math]t[/math] типизируется (англ. well-typed) в контексте [math]\Gamma[/math], если существует такой терм [math]T[/math], что [math]\Gamma \vdash t : T[/math].

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

Типизируемый в контексте [math]\Gamma[/math] терм [math]t[/math] имеет единственный тип с точностью до эквивалентности.

Определение:

Нормальный терм [math]t[/math], типизируемый в контекте [math]\Gamma[/math], имеет либо вид [math]\displaystyle t = \lambda x_1 : T_1 \ldots \lambda x_n : T_n . \left(x\ c_1\ \ldots\ c_n\right)[/math], где [math]x[/math] это переменная или сорт, либо вид [math]\displaystyle t = \lambda x_1 : T_1 \ldots \lambda x_n : T_n . \Pi x : P . Q\text{.}[/math] Согласимся первым символом (англ. head symbol) [math]t[/math] называть [math]x[/math] в первом случае, и [math]\Pi[/math] во втором. Первыми переменными (англ. top variables) [math]t[/math] будем называть переменные [math]x_1, \ldots, x_n[/math].

Задача вывода типов в [math]\lambda\Pi[/math]-исчислении

Определение:

Терм [math]t[/math] типа [math]T[/math] в контексте [math]G[/math] называется объектом в [math]\Gamma[/math], если [math]\Gamma \vdash T : \mathrm{Type}[/math].

Утверждение:

Если терм [math]t[/math] является объёктом в контексте [math]\Gamma[/math], то он является либо переменной, либо применением, либо абстракцией. Если он является применением [math]t=(u\ v)[/math], тогда оба терма [math]u[/math] и [math]v[/math] являются объектами в [math]\Gamma[/math], если он является абстракцией [math]t=\lambda x : U . u[/math], то тогда терм [math]u[/math] является объектом в контексте [math]\Gamma\left[x : U\right][/math].

Определение:

Множество чистых термов определяется грамматикой [math]T ::= x \mid \left(T\ T\right) \mid \lambda x . T[/math].

Определение:

Пусть [math]t[/math] — объект в контексте [math]\Gamma[/math]. Содержимое [math]t[/math] ([math]\left|t\right|[/math]) — это рекурсивно определённый чистый терм: [math]\left|x\right| = x[/math]; [math]\left|\left(t\ t'\right)\right| = \left(\left|t\right|\left|t'\right|\right) [/math]; [math]\left|\lambda x : U . t\right| = \lambda x . \left|t\right|[/math].

Определение:

Чистый терм [math]t[/math] называется типизируемым в контексте [math]\Gamma[/math], если существует терм [math]t'[/math], типизируемый в неком [math]\Gamma\Delta[/math], являющимся расширением [math]\Gamma[/math], что [math]t'[/math] является объектом в [math]\Gamma\Delta[/math] и [math]t=\left|t'\right|[/math].

Типизация чистого терма в контексте [math]\Gamma[/math] это присвоение типов связанным переменным и некоторым свободным переменным, типов которых нет в [math]\Gamma[/math]. Если же контекст [math]\Gamma[/math] пустой, то типизация терма в нём будет являться присваиванием типов и связанным и свободным переменным.

Утверждение:

Задача вывода типов в пустом контексте разрешима в [math]\lambda\Pi[/math]-исчислении.

[math]\triangleright[/math]

Типизируемые в пустом контексте чистые термы [math]\lambda\Pi[/math] исчисления совпадают с типизируемыми выражениями просто типизированного [math]\lambda[/math]-исчисления, а задача вывода типов в просто типизированном [math]\lambda[/math]-исчислении разрешима.

[math]\triangleleft[/math]

Неразрешимость задачи вывода типов в [math]\lambda\Pi[/math]-исчислении

Рассмотрим контекст [math]\Gamma=\left[T : \mathrm{Type}; a : T \rightarrow T; b : T \rightarrow T; c : T; d : T; P : T \rightarrow \mathrm{Type}; F : \Pi x : T.\left(\left(P\ x\right) \rightarrow T\right)\right][/math].

Определение:

Пусть [math]\varphi[/math] — слово двухсимвольного алфавита [math]\left\{A, B\right\}[/math]. Определим [math]\hat{\varphi}[/math] и [math]\tilde{\varphi}[/math] следующим образом: [math]\hat{\varepsilon} = \lambda y : T . y[/math]; [math]\hat{A\ \varphi} = \lambda y : T.\left(a\ \left(\hat{\varphi}\ y\right)\right)[/math]; [math]\hat{B\ \varphi} = \lambda y : T.\left(b\ \left(\hat{\varphi}\ y\right)\right)[/math]; [math]\tilde{\varphi}=\left|\hat{\varphi}\right|[/math].

Утверждение:

Рассмотрим проблему соответствий Поста для списков слов над двухсимвольным алфавитом [math]\left(\varphi_1, \ldots, \varphi_n\right)[/math] и [math]\left(\psi_1, \ldots, \psi_n\right)[/math]. Непустая последовательность [math]\left(i_1,\ldots,i_p\right)[/math] является её решением тогда и только тогда, когда [math](\hat{\varphi_{i_1}}\ (\ldots (\hat{\varphi_{i_p}}\ c)\ldots)) =_\beta (\hat{\psi_{i_1}}\ (\ldots (\hat{\psi_{i_p}}\ c)\ldots))[/math].

Утверждение:

Если [math]g[/math] это такой терм, что терм [math](g a \ldots a)[/math] ([math]a[/math] повторяется [math]n[/math] раз) типизируемый, и он является объектом в неком [math]\Gamma\Delta[/math], то тогда терм [math]g[/math] типизируется в контексте [math]\Gamma\Delta[/math], и его тип эквивалентен терму [math]\Pi x_1 : T \rightarrow T \ldots \Pi x_n : T \rightarrow T . (\beta x_1 \ldots x_n)[/math] для какого-то терма [math]\beta[/math] типа [math](T \rightarrow T) \rightarrow \ldots \rightarrow (T \rightarrow T) \rightarrow \mathrm{Type}[/math] в контексте [math]\Gamma\Delta[/math].

[math]\triangleright[/math]

Индукция по [math]n[/math].

[math]\triangleleft[/math]

Утверждение:

Пусть [math]t,u_1,\ldots,u_n,v[/math] — такие нормальные термы, что [math](t\ u_1\ldots u_n)[/math] — типизируемый терм, и его нормальная форма это [math]v[/math]. Тогда первый символ [math]t[/math] это либо первый символ [math]v[/math], либо первая переменная [math]t[/math].

[math]\triangleright[/math]

Пусть [math]x[/math] — первый символ [math]t[/math]. Если [math]x[/math] не является первой переменной [math]t[/math], то первый символ нормальной формы [math](t\ u_1 \ldots u_n)[/math] это тоже [math]x[/math], значит, [math]x[/math] это первый символ [math]v[/math].

[math]\triangleleft[/math]

Утверждение:

Пусть [math]t[/math] — такой нормальный терм типа [math](T \rightarrow T) \rightarrow \ldots \rightarrow (T \rightarrow T) \rightarrow T[/math] в контексте [math]\Gamma[/math], что нормальная форма [math](t\ \lambda y : T.y \ldots \lambda y : T.y)[/math] равна [math]c[/math]. Тогда терм [math]t[/math] является термом вида [math]t=\lambda x_1 : T \rightarrow T \ldots \lambda x_n : T \rightarrow T . (x_{i_1}\ (\ldots (x_{i_p}\ c)\ldots))[/math] для некой последовательности [math]i_1,\ldots,i_p[/math].

[math]\triangleright[/math]

Индукция по числу переменных в [math]t[/math].

[math]\triangleleft[/math]

Теорема:

Задача проверки типизируемости чистого терма в заданном контексте неразрешима.

Доказательство:

[math]\triangleright[/math]

Рассмотрим проблему соответствий Поста для списков слов над двухсимвольным алфавитом [math]\left(\varphi_1, \ldots, \varphi_n\right)[/math] и [math]\left(\psi_1, \ldots, \psi_n\right)[/math]. Построим такой чистый терм [math]t[/math], что [math]t[/math] типизируем в [math]\Gamma[/math] тогда и только тогда, когда проблема соответствий поста имеет решение. [math] \begin{aligned} t = \lambda f . \lambda g . \lambda h . (f\ &(g\ a \ldots a)\\ &(h\ (g\ \tilde{\varphi_1} \ldots \tilde{\varphi_n}))\\ &(h\ (g\ \tilde{\psi_1} \ldots \tilde{\psi_n}))\\ &(F\ c\ (g\ \lambda y.y \ldots \lambda y.y))\\ &(F\ d\ (g\ \lambda y.d \ldots \lambda y.d)))\text{.} \end{aligned} [/math] Предположим, что этот терм типизируем, и обозначим тип [math]g[/math] как [math]\alpha[/math]. Терм [math](g\ a \ldots a)[/math] типизируется и является объектом в [math]\Gamma\Delta[/math], значит, [math]\alpha =_\beta \Pi x_1 : T \rightarrow T \ldots \Pi x_n : T \rightarrow T . (\beta\ x_1 \ldots x_n)[/math], где [math]\beta[/math] это терм типа [math](T \rightarrow T) \rightarrow \ldots \rightarrow (T \rightarrow T) \rightarrow \mathrm{Type}[/math] в [math]\Gamma\Delta[/math]. Тогда все переменные [math]y[/math], связанные в термах [math]\hat{\varphi_i}[/math], [math]\tilde{\psi_i}[/math], [math]\lambda y.y[/math] и [math]\lambda y.d[/math], имеют тип [math]T[/math]. Терм [math](g \ \hat{\varphi_1} \ \ldots\ \hat{\varphi_n})[/math] имеет тип [math](\beta\ \hat{\varphi_1} \ \ldots\ \hat{\varphi_n})[/math], тогда из типизируемости терма [math](h\ (g \ \hat{\varphi_1} \ \ldots\ \hat{\varphi_n}))[/math] мы получаем, что тип переменной [math]h[/math] имеет вид [math]\Pi x : \gamma : \gamma'[/math], и [math]y =_\beta (\beta\ \hat{\varphi_1} \ \ldots\ \hat{\varphi_n})[/math]. Точно так же, из типизируемости терма [math](h\ (g \ \hat{\psi_1} \ \ldots\ \hat{\psi_n}))[/math] получаем, что [math]y =_\beta (\beta\ \hat{\psi_1} \ \ldots\ \hat{\psi_n})[/math], значит, [math](\beta\ \hat{\varphi_1} \ \ldots\ \hat{\varphi_n}) =_\beta (\beta\ \hat{\psi_1} \ \ldots\ \hat{\psi_n})[/math]. Из типизируемости терма [math](F\ c\ (g\ \lambda y : T.y\ldots \lambda y : T . y))[/math] получаем [math](\beta\ \lambda y:T.y \ldots \lambda y:T.y) =_\beta (P\ c)[/math]. Наконец, из типизируемости терма [math](F\ d\ (g\ \lambda y : T.d\ldots \lambda y : T . d))[/math] получаем [math](\beta\ \lambda y:T.d \ldots \lambda y:T.d) =_\beta (P\ d)[/math]. Поскольку терм [math]\beta[/math] имеет тип [math](T \rightarrow T) \rightarrow \ldots \rightarrow (T \rightarrow T) \rightarrow \mathrm{Type}[/math], первый символ нормальной формы терма [math]\beta[/math] не может быть первой переменной [math]\beta[/math], значит, это переменная [math]P[/math], и мы получаем, что [math]\beta =_\beta \lambda x_1 : T \rightarrow T \ldots \lambda x_n : T \rightarrow T.(P\ (\delta\ x_1 \ldots x_n))[/math], где [math]\delta[/math] — некий терм типа [math](T \rightarrow T) \rightarrow \ldots \rightarrow (T \rightarrow T) \rightarrow T[/math]. Получаем, что [math] (\delta\ \hat{\varphi_1} \ldots \hat{\varphi_n}) =_\beta (\delta\ \hat{\psi_1} \ldots \hat{\psi_n})\text{,} \\ (\delta\ \lambda y:T.y \ldots \lambda y:T.y) =_\beta c \text{,}\\ (\delta\ \lambda y:T.d \ldots \lambda y:T.d) =_\beta d \text{.} [/math] Вторая эквивалентность показывает, что нормальная форма [math]\delta[/math] имеет вид [math]\lambda x_1:T \rightarrow T \ldots \lambda x_n : T \rightarrow T . (x_{i_1}\ (\ldots(x_{i_p}\ c)\ldots))[/math] для некоторой последовательности [math]i_1,\ldots,i_p[/math]. Третья эквивалентность показывает, что [math]p\gt 0[/math], и первая — что [math](\hat{\varphi_{i_1}}\ (\ldots(\hat{\varphi_{i_p}\ c})\ldots)) =_\beta (\hat{\psi_{i_1}}\ (\ldots(\hat{\psi_{i_p}\ c})\ldots))[/math], то есть последовательность [math]i_1,\ldots,i_p[/math] является решением проблемы Поста. И наоборот, если предположить, что проблема Поста имеет решение [math]i_1,\ldots,i_p[/math], то можно задать типы переменным [math]f[/math], [math]g[/math] и [math]h[/math]: [math] f : (P\ (a\ (\ldots(a\ c)\ldots))) \rightarrow T \rightarrow T \rightarrow T \rightarrow T \rightarrow T \text{,}\\ g : \Pi x_1 : T \rightarrow T \ldots \Pi x_n : T \rightarrow T.(P\ (x_{i_1}\ (\ldots(x_{i_p}\ c)\ldots))) \text{,}\\ h : (P\ (\hat{\varphi_{i_1}}\ (\ldots(\hat{\varphi_{i_p}}\ c)\ldots))) \rightarrow T \text{;} [/math] и тип [math]T[/math] всем остальным переменным терма [math]t[/math], и получить такой типизируемый в [math]\Gamma[/math] терм [math]t'[/math], который является объектом и [math]t = \left|t'\right|[/math].

[math]\triangleleft[/math]

См. также

Лямбда-исчисление

Источники информации

• Gilles Dowek, The undecidability of typability in the Lambda-Pi-calculus