Pytania otagowane jako lambda-calculus

System formalny Kościoła używany w obliczeniach, językach programowania i teorii dowodów do reprezentowania skutecznych funkcji, programów i ich obliczeń oraz dowodów.

1
W jaki sposób nieterminalne
Myślałem o tych pytaniach: Czy istnieje typowany rachunek lambda, który jest spójny i kompletny Turinga? /cs/65003/if-%CE%BB-xxx-has-a-type-then-is-the-type-system-inconsistent i już teraz istnieją trudne odpowiedzi na powiązane pytania w nietypowym otoczeniu! Mówiąc dokładniej, jestem ciekawy, czy możemy odzyskać kompletność Turinga po rozwiązaniu umowy w następujący sposób: Pytanie: Biorąc pod uwagę (czysty) λλ\lambda term …
1
η-konwersja vs rozciągliwość w rozszerzeniach rachunku lambda
Często myli mnie związek między konwersją η a ekstensywnością. Edytuj: Według komentarzy wydaje mi się, że jestem również zdezorientowany co do związku między równoważnością ekstensywną a równoważnością obserwacyjną. Ale przynajmniej w Agdzie z ekstensywną równością funkcji (jako postulat) i dla prostego rachunku lambda (który ma w pełni abstrakcyjną semantykę, jeśli …
3
Jakie są negatywne konsekwencje rozszerzenia CIC o aksjomaty?
Czy to prawda, że ​​dodanie aksjomatów do CIC może mieć negatywny wpływ na zawartość obliczeniową definicji i twierdzeń? I zrozumieć, że w normalnych zachowań teoria, wszelkie zamknięte termin zostanie zredukowany do kanonicznej normalnej postaci, na przykład w przypadku jest prawdziwy, wówczas n może obniżać się okres postaci ( s U …
2
Własność Churcha-Rossera dla rachunku lambda zależnie wpisanego?
Powszechnie wiadomo, że właściwość Church-Rosser obejmuje redukcję w prostym typie rachunku lambda. Oznacza to, że rachunek różniczkowy jest spójny w tym sensie, że nie wszystkie równania obejmujące terms można wyprowadzić: na przykład K I , ponieważ nie mają one tej samej postaci normalnej.λ ≠βηβη\beta \etaλλ\lambda≠≠\neq Wiadomo również, że wynik można …
1
Terminy Lambda-Calculus, które redukują się do siebie
W mojej ciągłej próbie nauki rachunku różniczkowego lambda, „Lambda-Calculus and Combinators an Introduction” Hindleya i Seldina wymienia następujący artykuł (autorstwa Bruce'a Lerchera), który dowodzi, że jedynym redukowalnym wyrażeniem jest to samo (konwersja modulo alfa) to: .( λ x . x x ) ( λ x . x x )(λx.xx)(λx.xx)(\lambda x.xx)(\lambda …
2
Jakie są prawa równań dla typów zerowych?
Oświadczenie : chociaż dbam o teorię typów, nie uważam się za eksperta w dziedzinie teorii typów. W prostym typie rachunku lambda typ zerowy nie ma konstruktorów i unikalnego eliminatora: Γ⊢M:0Γ⊢initial(M):AΓ⊢M:0Γ⊢initial(M):A\frac{\Gamma \vdash M \colon 0}{\Gamma \vdash initial (M) \colon A} Z denotacyjnego punktu widzenia równanie initial(M1)=initial(M2)initial(M1)=initial(M2)initial (M_1) = initial(M_2) jest oczywiste …
1
Czy call / cc Scheme może implementować wszystkie znane struktury przepływu sterowania?
Strona „Advanced Scheme: Some Naughty Bits” stanowi: Kontynuacje są potężnym konstruktem sterowania przepływem, z którego można wyprowadzić prawie każdą inną strukturę przepływu sterowania [...]. Myślałem, że Scheme call/cc, związane (*) z operatorem J Petera Landina, może być wykorzystane do wdrożenia dowolnej znanej struktury przepływu sterowania? W „strukturze kontroli przepływu” szczególnie …
2
Jak dokładnie rachunek lambda uwzględnia intuicyjne pojęcie obliczalności?
Próbowałem owinąć głowę wokół tego, co, dlaczego i jak rachunek, ale nie jestem w stanie poradzić sobie z „dlaczego to działa”?λλ\lambda „Intuicyjnie” dostaję model obliczeniowy Turing Machines (TM). Ale ta abstrakcja wprawia mnie w zakłopotanie.λλ\lambda Załóżmy, że bazy danych nie istnieją - jak więc można „intuicyjnie” przekonać się o zdolności …
6
Funkcje, które wpisały rachunek lambda, nie mogą być obliczane
Chciałbym tylko poznać kilka przykładów funkcji, które można obliczyć za pomocą niepisanego rachunku lambda, ale nie za pomocą wpisanego rachunku lambda. Jako że jestem początkującym, doceniłbym powtórzenie podstawowych informacji. Dzięki. Edycja: za pomocą kalkulatora lambda, miałem zamiar wiedzieć o systemie F i rachunku lambda po prostu. Przez funkcję rozumiem dowolną …
1
Dowód Barendregta na redukcję podmiotu dla
Znalazłem problem w dowodzie Barendregta na redukcję podmiotu (Thm 4.2.5 rachunku Lambda z typami ). Ostatni krok dowodu (strona 60) mówi: „a zatem przez Lemma 4.1.19 (1), Γ,x:ρ⊢P:σ′Γ,x:ρ⊢P:σ′\quad\Gamma,x:\rho\vdash P:\sigma' . ” Jednak zgodnie z Lemmą 4.1.19 (1) powinno to być Γ[α⃗ :=τ⃗ ],x:ρ⊢P:σ′Γ[α→:=τ→],x:ρ⊢P:σ′\Gamma[\vec{\alpha}:=\vec{\tau}],x:\rho\vdash P:\sigma' , ponieważ podstawienie następuje w całym …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.