Como os termos-

Eu estive pensando sobre estas perguntas:

Existe um cálculo lambda digitado que seja consistente e Turing completo?

/cs/65003/if-%CE%BB-xxx-has-a-type-then-is-the-type-system-inconsistent

e já existem algumas questões difíceis de responder relacionadas na configuração sem tipo! Mais especificamente, estou curioso para saber se podemos recuperar a integridade de Turing da não terminação da seguinte maneira:

Pergunta: Dado um (puro) $\lambda$ -termo $t$ com nenhuma forma normal cabeça fraca, não existe sempre existir um elemento de combinação de ponto fixo $Y_t$ de tal forma que

$$Y_t\ (\lambda x.x) = t$$

Todas as igualdade são tomadas no módulo $\beta\eta$ .

Na verdade, eu suspeito que esta versão da pergunta seja falsa , para que se possa relaxar a questão para combinadores em loop , em que um combinador em loop $Y$ é definido como um termo tal que para cada $f$

$$Y\ f=f\ (Y'\ f)$$ onde $Y'$ é novamente necessário que seja um combinador de loop. Isso é suficiente para definir funções recursivas como de costume, é claro.

De maneira mais geral, estou interessado em encontrar maneiras "naturais" de passar de um sem terminação $t$para um combinador de loop, mesmo que a equação acima não seja satisfeita.

Eu também estou interessado em versões mais fracos da pergunta acima, por exemplo, $t$ pode ser considerado como sendo uma aplicação $t\equiv t_1\ t_2\ldots t_n$ a cada $t_i$ na forma normal (embora eu não tenho certeza de que realmente ajuda).

---

Até agora: a abordagem natural é aplicar $t$ "pimenta" de $f$ todo o processo, por exemplo

$$\Omega:=(\lambda x.x\ x)(\lambda x.x\ x)$$

torna-se o habitual

$$Y_\Omega:= \lambda f.(\lambda x. f\ (x\ x))\ (\lambda x.f\ (x\ x))$$

A idéia é reduzir a cabeça de $t$ para um aplicativo lambda $\lambda x. t'$ e substitua-o por $\lambda x.f\ t'$ , mas o próximo passo não é claro (e eu sou cético quanto a isso poder levar a qualquer coisa).

Não tenho certeza eu entendo o suficiente sobre árvores Böhm para ver se eles têm alguma coisa a dizer, mas eu duvido muito, desde $\Omega$ Böhm árvore 's é simplesmente $\bot$ , que parece em nada com a pessoa certa para $Y_\Omega$ : uma árvore infinita de abstrações.

---

Edit : Um amigo meu observou que esta abordagem ingênua não funciona com o termo:

$$(\lambda x.x\ x\ x)(\lambda x.x\ x\ x)$$ A abordagem ingênua daria $$(\lambda x.f\ (x\ x\ x))(\lambda x.f\ (x\ x\ x))$$ Mas este não é um combinador de pontos fixos! Isso pode ser corrigido substituindo a segunda aplicação de $f$ por , mas então f ↦ eu não dá ao termo original. Não está claro se esse termo é um contra-exemplo para a pergunta original (e certamente não é um contra-exemplo para a mais geral).$\lambda y z.f\ y$$f\mapsto \mathrm{I}$

Existem vários aspectos para essa pergunta muito legal, portanto estruturarei esta resposta de acordo. $\newcommand{\setof}[1]{\{#1\}}$ $\newcommand{\thra}{\twoheadrightarrow}$ $\newcommand{\codeof}[1]{\lceil #1 \rceil}$

1. A resposta para a pergunta em caixa é não . Os termo sugerido pelo seu amigo é realmente um contra-exemplo.$\Omega_3 = (\lambda x.xxx)(\lambda x.xxx)$

Foi observado anteriormente nos comentários que se tem contra-exemplos como o "ogro" , até que a questão seja restrita a termos sem forma normal de cabeça fraca. Tais termos são conhecidos comotermos zero. Estes são termos que nunca se reduzem a um lambda, sob qualquer substituição.$K^\infty=Y K$

Para qualquer combinador de ponto fixo (fpc) ,$Y$ é o chamadotermomudo(AKA "root-active"): cada redução do mesmo reduz-se ainda mais a um redex.$Y I$

não é mudo; nem é Ω 3 - como é manifestado pela inspeção de seu conjunto de redutos, que é { Ω 3 ( λ x . x x x ) ⋯ ( λ x . x x x ) ⏟ k$K^\infty$$\Omega_3$ $-$

$$\setof{\Omega_3 \underbrace{(\lambda x. xxx) \cdots (\lambda x. xxx)}_k \mid k \in \mathbb{N}}$$

Em vez de apresentar um argumento preciso por que é mudo para todos os fpcs $Y I$$Y$ (de fato, para qualquer combinador de loop) que pode ser trabalhoso, mas esperançosamente claro o suficiente - , tratarei a generalização óbvia de sua pergunta, restringindo também os termos mudos.$-$$-$

Termos mudos são uma subclasse de termos zero que são uma subclasse de termos insolúveis. Juntas, essas são talvez as escolhas mais populares para o conceito de "sem sentido" ou "indefinido" no cálculo lambda, correspondendo às árvores triviais de Berarducci, Levy-Longo e B \ ohm, respectivamente. A estrutura de noções de termos sem sentido foi analisada em detalhes por Paula Severi e Fer-Jan de Vries. [1] Os termos mudos constituem o elemento inferior dessa treliça, ou seja, a noção mais restritiva de "indefinido".

2. Seja um termo mudo e Y seja um combinador de loop com a propriedade que $M$$Y$ .$YI = M$

Primeiro, argumentamos que, para uma variável nova , Y z se parece muito com o Y M que você descreveu, obtido por "aspersão $z$$Yz$$Y_M$$z$ em torno de" alguns reduct de .$M$

Por Church-Rosser, e M têm um reduto comum, M ′ . Faça uma redução padrão R : Y I ' s M ' . Todo subtermo de M ′ corresponde a um subtermo único de Y I ≡ Y z [ z : = I ] sob esta redução. Para qualquer subtermo C [ N ] = M ′ , fatores R como N 0 ] ↠ $YI$$M$$M'$$R : YI \thra_s M'$$M'$$YI\equiv Yz[z:=I]$$C[N]=M'$$R$, em que a perna do meio é uma redução de cabeça fraca (e etapa final é interna). Né "guardado" por umzse esta segunda etapa contrair algum redexIP, comIum descendente da substituição[z:=I].$YI \thra C[N_0] \thra_{wh} C[N_1] \thra_i C[N]$$N$$z$$I P$$I$$[z:=I]$

Obviamente, tem que guardar alguns subtermos de M , caso contrário seria mudo também. Por outro lado, deve-se ter cuidado para não guardar os subtermos necessários para a não terminação, pois, caso contrário, não poderá desenvolver a árvore B \ "ohm infinita de um combinador em loop.$Y$$M$

Assim, basta encontrar um termo mudo no qual todo subtermo, de cada redução, é necessário para a não normalização, no sentido de que colocar uma variável na frente desse subtermo produz um termo normalizador.

Considere , onde W = λ w . w eu w w . É como Ω , mas a cada iteração, verificamos que a ocorrência de W na posição do argumento não é "bloqueada" por uma variável head, alimentando-a com uma identidade. Colocar um z na frente de qualquer subtermo resultará em uma forma normal de forma z P 1 ⋯ P k , onde cada P i é I , W ou a " $\Psi = W W$$W = \lambda w. w I w w$$\Omega$$W$$z$$zP_1\cdots P_k$$P_i$$I$$W$$z$ borrão " deles. Então $\Psi$ é um contra-exemplo para a questão generalizada.

TEOREMA. Não existe um combinador de loop tal que Y I $Y$ .$YI = \Psi$

PROVA. O conjunto de todas as redutos de é { W W , W I W W , I I I I W W , I I I W W , I I W W , I W W } . Para ser conversível com Ψ , Y devo reduzir a um deles. O argumento é idêntico em todos os casos; para concreção, suponhamos que Y I ↠ I I W W .$\Psi$$\setof{WW,WIWW,IIIIWW,IIIWW,IIWW,IWW}$$\Psi$$YI$$YI \thra IIWW$

Qualquer redução padrão pode ser tomada como Y I ↠ w P N 4 , P ↠ W Q N 3 , Q ↠ w N 1 N 2 , assim  Y I ↠ w N 1 N 2 N 3 N 4 N 1 ↠ I , N 2 ↠ I , N $YI \thra_s IIWW$

$$\begin{align*} YI \thra_w P N_4, P \thra_w Q N_3, Q \thra_w N_1 N_2, \text{thus } YI \thra_w N_1 N_2 N_3 N_4\\ N_1 \thra I, N_2 \thra I, N_3 \thra W, N_4 \thra W \end{align*}$$

Vamos nos referir à redução como R 0 , e as reduções a partir de N i como R $YI \thra_w N_1 N_2 N_3 N_4$$R_0$$N_i$$R_i$ .

Estas reduções podem ser levantado através da substituição para produzir R z 0 : Y z ↠ z k ( M 1 M 2 M 3 M 4 ) N i ≡ H i [ z : = I ] de modo a que R 0 é a composição Y I R z 0 [ z : = I ] ↠$[z:=I]$

$$\begin{align*} R^z_0 : Yz \thra z^k(M_1 M_2 M_3 M_4)\\ N_i \equiv M_i[z:=I] \end{align*}$$ $R_0$$YI \stackrel{R^z_0[z:=I]}{\thra} I^k(N_1 \cdots N_4) \thra^k_w N_1 \cdots N_4$

$R_i : N_i \thra N \in \setof{I,W}$

$$\begin{align*} R^z_i : M_i \thra N^z_i\\ R_i : N_i \stackrel{R^z_i[z:=I]}{\thra} N^z_i[z:=I] \thra_I N \end{align*}$$

$R_i$$I$$N^z_i[z:=I]$$N$$N^z_i$

$N^z_i$$z$$N$$z$$N$$N \in \setof{I,W}$$N^z_i$

$$\begin{align*} &z^{k_1}(\lambda x. z^{k_2}(x))\\ &z^{k_1}(\lambda w. z^{k_2}( z^{k_3}( z^{k_5}( z^{k_7}(w) z^{k_8}(\lambda x. z^{k_9}(x)) ) z^{k_6}(w) ) z^{k_4}(w) )) \end{align*}$$

$M_1 M_2 M_3 M_4 \thra N^z_1 N^z_2 N^z_3 N^z_4$$N^z_i$$z$$I$$i =1,2$$W$$i=3,4$

Ao mesmo tempo, o termo $N^z_1 N^z_2 N^z_3 N^z_4$ ainda deve reduzir para produzir a infinita fpc Bohm tree $z(z(z(\cdots)))$. Portanto, deve haver uma "aspersão"$z^{k_j}$ em um dos $N^z_i$ que chega infinitamente frequentemente à cabeça do termo, mas não bloqueia reduções adicionais dele.

E agora terminamos. Inspecionando cada$N^z_i$, para $i \le 4$e cada valor possível de $k_j$, para $j \le 2+7\lfloor \frac{i-1}{2} \rfloor$, descobrimos que não existe tal aspersão.

Por exemplo, se modificarmos o último $W$ dentro $IIWW$ Como $W^z = \lambda w. z(wIww)$, obtemos a redução de normalização

$$IIWW^z \to I W W^z \to WW^z \to W^z I W^z W^z \to z (I I I I) W^z W^z \thra z I W^z W^z$$

(Notar que $\Omega$admite tal aspersão precisamente porque um certo subtermo dele pode ser "protegido" sem afetar a não normalização. A variável vem na posição principal, mas redexes suficientes permanecem abaixo.)

3. A "transformação por aspersão" tem outros usos. Por exemplo, colocando$z$ na frente de cada redex em $M$, obtemos um termo $N = \lambda z. M_z$ que é uma forma normal, mas satisfaz a equação $N I = M$. Isso foi usado por Statman em [2], por exemplo.

4. Como alternativa, se você relaxar o requisito de que $Y I = M$, você pode encontrar vários fpcs (fracos) $Y$ que simulam a redução de $M$, enquanto produz uma cadeia de $z$s ao longo do caminho. Não tenho certeza se isso responderia à sua pergunta geral, mas certamente há várias transformações (computáveis)$M \mapsto Y_M$ que produzem combinadores de loop para cada mudo $M$, de tal maneira que o gráfico de redução de $Y_M$ é estruturalmente semelhante ao de $M$. Por exemplo, pode-se escrever

$$Y \codeof{M} z = \begin{cases} z (Y \codeof{P[x:=Q]} z) &M\equiv (\lambda x.P)Q\\ Y \codeof{N} z &M \text{ is not a redex and }M \to_{wh} N \end{cases}$$

[1] Severi P., de Vries FJ. (2011) Decompondo a Malha de Conjuntos Sem Significado no Cálculo Infinitário de Lambda. In: Beklemishev LD, de Queiroz R. (eds) Lógica, Linguagem, Informação e Computação. WoLLIC 2011. Notas de aula em Ciência da Computação, vol 6642.

[2] Richard Statman. Não há combinador hiper-recorrente S, K. Relatório de Pesquisa 91–133, Departamento de Matemática, Universidade Carnegie Mellon, Pittsburgh, PA, 1991.