Para questões sobre sistemas lógicos definidos por meio da aplicação e reescrita de termos de combinadores. Esses sistemas costumam ter uma conexão estreita com o cálculo lambda.
Na página da Wikipedia para Combinadores de ponto fixo, está escrito o texto bastante misterioso O combinador Y é um exemplo do que torna o cálculo Lambda inconsistente. Portanto, deve ser encarado com desconfiança. No entanto, é seguro considerar o combinador Y quando definido apenas na lógica...
O combinador de ponto fixo FIX (também conhecido como combinador Y) no cálculo lambda (sem tipo) ( ) é definido como:λλ\lambda FIXF λ f. ( λ x . f ( λ y. x x y ) ) ( λ x . f ( λ y. x x y ) ))≜λf.(λx.f (λy.x x y)) (λx.f (λy.x x y))\triangleq \lambda f.(\lambda x. f~(\lambda y. x~x~y))~(\lambda...
Muitos de nós sabemos a correspondência entre lógica combinatória e cálculo lambda . Mas nunca vi (talvez não tenha examinado o suficiente) o equivalente a "combinadores digitados", correspondendo ao cálculo lambda simplesmente digitado. Existe algo assim? Onde alguém poderia encontrar informações...
É sabido que os combinadores S e K formam um conjunto básico para o cálculo do combinador, no sentido de que todos os outros combinadores podem ser expressos em termos deles. Há também a base B, C, K, W de Curry, que possui a mesma propriedade. Deve haver um número infinito de tais bases, mas não...
O combinador Y tem o tipo . Pela correspondência de Curry-Howard, como o tipo é habitado, ele deve corresponder a um verdadeiro teorema. No entanto, é sempre verdadeiro, portanto parece que o tipo do combinador Y corresponde ao teorema , o que nem sempre é verdadeiro. Como isso pode ser?( a → a ) →...
Uma expressão combinadora (digamos na base SK) pode ser pensada como uma função que mapeia expressões de cálculo combinador para expressões de cálculo combinador. Ou seja, pode-se pensar em uma expressão XXX como uma função X: L → LX:eu→euX:L \to L , onde eueuL é o conjunto de todas as expressões...
De acordo com Peter Selinger , O cálculo lambda é algébrico (PDF). No início deste artigo, ele diz: Sabe-se que a interpretação combinatória do cálculo lambda é imperfeita, pois não satisfaz a regra ξξξ : sob a interpretação, M= NM=NM = N não implica λ x . M= λ x . Nλx.M=λx.N\lambda x.M =...
Especificamente, se eu definisse um novo K2K2K_2 como K2= λ x . ( λ y. y)K2=λx.(λy.y)K_2 = \lambda x. (\lambda y. y) vez de K= λ x . ( λ y. x )K=λx.(λy.x)K = \lambda x. (\lambda y. x) o { S, K2, I}{S,K2,I}\{S, K_2,I\} -calculus ser uma base competir? Meu palpite é "não", apenas porque parece...
Portanto, existe um algoritmo para converter termos de cálculo lambda em lógica combinatória usando combinadores SK. Produz coisas que explodem de tamanho. Eu gostaria de saber mais sobre essa explosão de tamanho. No entanto, não consigo pensar em um algoritmo melhor. Eu ouvi falar de linguagens...
No artigo de Chris Okasaki, " Achatando Combinadores: Sobrevivendo Sem Parênteses ", ele mostra que dois combinadores são suficientes e necessários como base para codificar expressões completas de Turing sem a necessidade de um operador de aplicativo ou parênteses. Comparado às codificações de...
Como existe um cálculo lambda sem tipo e um cálculo lambda com tipo simples (como descrito, por exemplo, no livro Tipos e linguagens de programação de Benjamin Pierce), existe uma lógica combinatória de tipo simples? Por exemplo, parece que os tipos naturais para os combinadores S, K e eu...
Eu entendo o que é, mas não vejo como isso serve para algoritmos ou algo assim. Talvez esteja faltando alguma coisa. Preciso que alguém me dê um exemplo de como ele pode ser usado para que eu possa entender
Estou tentando entender os combinadores Y. Poderia explicar por que os seguintes itens são equivalentes (Y (f ∘ g)) (f (Y (g ∘ f))) (Y é uma combinação de pontos