"Pedido aplicável" e "Pedido normal" no cálculo lambda

Ordem aplicável : sempre avalie totalmente os argumentos de uma função antes de avaliar a própria função, como -

$(\lambda x. x^2(\lambda x.(x+1) \ \ 2))) \rightarrow (\lambda x. x^2(2+1))\rightarrow \ (\lambda x. x^2(3)) \rightarrow \ 3^2 \ \rightarrow \ 9$

Ordem normal: a expressão seria reduzida de fora para dentro, como -

$(\lambda x.x^2 (\lambda x.(x+1) \ 2)) \rightarrow \ (\lambda x.(x+1) \ \ \ 2)^ 2 \rightarrow\ (2+1)^2 \ \rightarrow 3^2 \ \rightarrow \ 9$

Seja $M = (\lambda x.y \ (\lambda x.(x \ \ x) \ \lambda x.(x \ \ x)))$

Por que é que, na ordem do aplicativo, loop infinito, mas na ordem normal, M → y ?$M \rightarrow$
$M \rightarrow y$

é um loop infinito porque λ x . ( x x ) λ x . ( x x ) → λ x . ( x x ) λ x . ( x x ) Observe que λ x . ( $(\lambda x.y \ (\lambda x.(x \ \ x) \ \lambda x.(x \ \ x)))$

O termo que você está reduzindo é onde K y é a função constante λ x . y (sempre retorna y , ignorando seu argumento) e Ω = ( λ x . ( $(K_y \Omega)$$K_y$$\lambda x. y$$y$ é um termo que não termina. Em certo sentido, Ω é o termo não terminante final: ele se reduz beta a si próprio, ou seja, Ω → Ω . (Certifique-se de elaborá-lo em papel pelo menos uma vez na vida.)$\Omega = (\lambda x. (x \, x) \: \lambda x. (x \, x))$$\Omega$$\Omega \to \Omega$

A redução de pedido aplicável deve reduzir o argumento da função para uma forma normal, antes de poder avaliar o redex de nível superior. Como o argumento não tem forma normal, a redução da ordem do aplicativo é executada em loop infinitamente. Mais geralmente, para qualquer termo M , M Ω → M Ω , e essa é a redução escolhida pela estratégia de ordem aplicativa.$\Omega$$M$$M \Omega \to M \Omega$

$K_y$$K_y$$(K_y \Omega) \to y$$K_y N \to y$$N$

Este caso ilustra um fenômeno mais geral: a redução da ordem aplicativa somente encontra uma forma normal se o termo estiver normalizando fortemente, enquanto a redução normal da ordem sempre encontra a forma normal se houver uma. Isso acontece porque a ordem do aplicativo sempre avalia os argumentos completos primeiro e, portanto, perde a oportunidade de um argumento não ser utilizado; enquanto a ordem normal avalia os argumentos o mais tarde possível e, portanto, sempre vence se o argumento não for utilizado.

(O lado oposto é que a ordem do aplicativo tende a ser mais rápida na prática, porque é relativamente raro um argumento não ser usado; ao passo que é comum que um argumento seja usado várias vezes e, na ordem do aplicativo, o argumento é avaliado apenas uma vez. Normal order avalia o argumento quantas vezes for usado, seja 0, 1 ou várias vezes.)