Equivalência de duas expressões lambda para NOT

Eu vi duas expressões lambda diferentes para a função lógica NOT.
Um deles apenas aplica seu parâmetro a constantes truee falseinternamente em uma ordem inversa:

$NOT \;\;=\;\; \lambda x.\; x \; \mbox{false}\; \mbox{true} \;\;=\;\; \lambda x. \; x \; (\lambda t.\lambda f.f) \; (\lambda t. \lambda f. t )$

e o outro que captura mais dois parâmetros em vez de passá-los para a função retornada externamente e aplica a eles na ordem inversa também: $x$

$NOT \;\;=\;\; \lambda x. \; \lambda t.\lambda f.xft$

dos quais o outro parece um pouco mais simples (e também é mais simples quando codificado em binário).

Portanto, minha pergunta é a seguinte:
existe alguma transformação que possa me levar de uma dessas representações para a outra?

Vejo que eles são equivalentes "extensionalmente", isto é, ambos produzem os mesmos resultados. Mas eu gostaria de "provar" de alguma forma por transformações algébricas, como as das conversões alfa, beta e eta. Infelizmente, nada disso pode me ajudar neste caso: Alpha é apenas para renomear. Beta funciona apenas para chamadas de função, mas não temos aqui nenhuma chamada de função que possa ser reduzida, pois $x$ é livre no corpo da função (embora não seja toda a expressão) em todas essas expressões até que realmente invoquemos NOTalgo. O mais próximo parece ser o eta, que está relacionado à equivalência extensional e aos parâmetros de encaminhamento, mas quando os parâmetros estão sendo revertidos, não é mais um encaminhamento simples e o eta parece não se aplicar aqui.

Há mais alguma regra de conversão em falta?
(Bem, acho que eles não vão pular duas letras gregas sem motivo específico, não é?)

PS: Esta questão é na verdade um modelo, uma vez que existem muitas outras definições para outras funções que têm várias formas diferentes que parecem ser extensionalmente equivalentes, mas completamente diferentes em relação às regras de redução conhecidas. Eu escolhi o exemplo mais simples deste problema.

Editar:
para esclarecer melhor o que eu gostaria de saber, aqui está um diagrama mostrando as etapas de redução para as duas versões da notfunção: http://sasq.comyr.com/Stuff/Lambda/Not.png

Como você pode ver, eles realmente reduzem os mesmos resultados (ao contrário do que Jonathan Gallagher estava dizendo abaixo). Isto é o que eu já sei: eles são confluentes e, portanto, são equivalentes a Church-Rosser. O que eu não sei, no entanto, é se existe alguma regra de conversão (semelhante a alfa, beta e eta) que possa me permitir transformar uma forma de notoutra. Isso me permitiria, pelo menos, garantir que algumas outras funções (mais complicadas que essas duas aqui) também sejam equivalentes, o que pode ser difícil quando elas podem reduzir para mais do que apenas duas respostas possíveis. Gostaria de saber se existe alguma regra de conversão que permita converter uma definição intensional em outra quandoduas funções já são extensionalmente equivalentes (ou seja, fornecem os mesmos resultados para os mesmos parâmetros). Ou (o que seria melhor) se alguma função puder ser convertida de alguma forma na outra, mesmo que eu não saiba se elas são extensionalmente equivalentes.

lambda-calculus SasQ
fonte

Você não poderá provar nada apenas nessas duas codificações de NOT, mas o resultado que poderá querer provar seria algo como: dado

f

$f$ um termo lambda booleano,

N O T f t r u e f a l s e

$NOT\ f\ true\ false$ deve reduzir para a mesma forma normal, independentemente da codificação de NÃO escolhida.

Tpecatte

Humm, muuuito ... você sugere usar o teorema de Church-Rosser para mostrar confluência de ambas as reduções? Mas isso não sugere que possa haver alguma transformação envolvida? (talvez alguns que ainda não foi descoberto)

SasQ

Não tenho certeza de que haja alguma transformação envolvida, a confluência apenas significa que a escolha de não realmente não importa. É o mesmo que número inteiro da Igreja, você pode trocar os dois parâmetros para definir números inteiros, e ambos são válidos e são equivalentes de alguma forma quando "avaliados", mas não equivalentes usando transformações.

Tpecatte

Respostas:

Para provar que as duas formas NOT geralmente não são equivalentes, tudo o que você precisa fazer é encontrar um termo que, quando cada uma for aplicada, retorne um resultado diferente, como:

$NOT1 \; \lambda x.\; x \; \;\;=\;\; (\lambda x. \; x \; (\lambda t.\lambda f.f) \; (\lambda t. \lambda f. t )) \; \lambda x.\; x \;\; =\;\; \lambda x. \; x \;$

$NOT2 \; \lambda x.\; x \; \;\;=\;\; (\lambda x.\lambda t.\lambda f.xft) \; \lambda x.\; x\;\; =\;\; \lambda t.\lambda f. ft \;$

dansalmo
fonte

-3

Que o primeiro não seja chamado de not1 e o segundo não2. Então você tem o seguinte:

n o t 1 M \to_{β} M f a l s e t r u e

$\mathsf{not1} \, M \to_\beta M \, \mathsf{false} \, \mathsf{true}$ e

n o t 2 M \to_{β} λ t f . M f t \to_{η} λ t . M t \to_{η} M

$\mathsf{not2} \, M \to_\beta \lambda t \, f . M \, f \, t \to_\eta \lambda t . M \, t \to_\eta M$

Agora, se supusermos que

M = t r u e

$M = \mathsf{true}$ então a redução superior nos daria falsa, enquanto a redução inferior nos daria verdadeira - de modo que fazer a identificação pareceria dar um resultado estranho.

Jonathan Gallagher
fonte

Isso porque você cometeu um erro. Tanto quanto eu sei, você não pode reduzir esse caminho.

n o t 2 M \to_{β} λ t f . M f t

$\mathsf{not2} \, M \to_\beta \lambda t \, f . M \, f \, t$ está OK e esta é a forma normal correta até você saber

M

$M$ . Mas isso não é:

λ t f . M f t \to_{η} λ t . M t

$\lambda t \, f . M \, f \, t \to_\eta \lambda t . M \, t$ ; você não pode se livrar de

λ f

$\lambda f$ porque não é o último parâmetro no aplicativo de função subordinada. Se você chamar a função reduzida dessa maneira com os mesmos parâmetros, ela retornará

M t

$M t$ , que por sua vez será chamado no outro parâmetro (anteriormente

f

$f$ ), que dá

M t f

$M t f$ , não

M f t

$M f t$ .

SasQ 17/09/13

Eu acredito que você está incorreto. Eta é uma reescrita, portanto deve ser uma congruência - fechada sob substituição e contexto. Isso deve permitir a redução dada. Eu também posso fazer o contrário, se você quiser. Conjunto

S = λ f . M f)

$S = \lambda f . M f)$ . Então

λ t . S t \to^{η} S

$\lambda t . S t \to^{\eta} S$ e então novamente,

λ f . M f \to^{η} M

$\lambda f . M f \to^{\eta} M$ .

Jonathan Gallagher

@JonathanGallagher:

λ t f . M f t

$\lambda t f . M f t$ deve ser lido como

λ t . λ f . ((M f) t)

$\lambda t . \lambda f . ((M f) t)$ e não tão

λ t . (λ f . (M f)) t

$\lambda t. (\lambda f . (M f)) t$ . Você entendeu errado suas parênteses, e é por isso que acha que pode executar o

η

$\eta$ -redução.

Andrej Bauer

Ah Eu vejo. Obrigado pelo esclarecimento. Minha resposta está incorreta.

Jonathan Gallagher