Cálculo Lambda sem variáveis livres é tão forte como o cálculo lambda?

Question

Primeira pergunta:Como é que iria provar que removendo livre (independente) variáveis do cálculo lambda, e permitindo que apenas variī aveis, o seu poder não é reduzida (ainda é Turing-completa) ?

Segunda pergunta:É a proposição dada acima realmente verdade?É cálculo lambda sans variáveis livres realmente Turing-completa?

Answer 1

Eu estou supondo que você está se referindo ao untyped cálculo lambda.

Se assim for, escrever $ ewcommand{ um}[1]{\ulcorner #1 \urcorner} um{n}$ para a Igreja numeral natural unmber $n$.

É conhecido que existe um fechado prazo (isto é, sem variáveis livres) $TM$ de tal forma que $$ TM\ um{i}\ um{n}\ =_{\beta\eta}\ um{m} $$ se, e somente se, a $i$-ésima máquina de Turing (em algum padrão de enumeração) executado com entrada $n\in\mathbb N$ (codificado como de costume) pára de voltar $m$ como saída.

De fato, a escrita $TM$ é um padrão de "programação" de exercício no cálculo lambda.Para isso, pode-se representar a fita como um par-ou-pares-de-pares-de...(AKA uma lista de contras) de símbolos.Em seguida, um "pisar" sub-rotina para avançar a fita e o TM, o estado pode ser escrito.Finalmente, o nível de sub-rotina é chamada, até parar estado é atingido.Esta última etapa pode ser realizada através de um ponto fixo combinator, tais como $Y$.

Desde que nós podemos simular qualquer máquina de Turing, temos de Turing integralidade.

---

Prova alternativa, que é (na minha opinião) mais fácil de realizar em todos os detalhes:provar que qualquer função recursiva pode ser $\lambda$-definidas usando uma fechada lambda prazo.Para isso, proceder por indução sobre a definição geral de função recursiva.

Na verdade, mesmo se você não apontar para o fechado termos, no presente exercício de programação você vai obter uma fechada de uma forma natural.Afinal, quando a programação nunca se precisa de uma variável que não foi declarado de antemão.

Desde o geral de funções recursivas são exatamente aqueles que podem ser computada por uma máquina de Turing, temos de Turing completude para o fechado cálculo lambda.