Pytania otagowane jako lo.logic

Logika obliczeniowa i matematyczna.

2
Czy istnieją pośrednie teorie eta dla rachunku lambda?
Istnieją dwie główne, zbadane teorie rachunku lambda, teorii beta i jej rozwinięcia post-zupełnego, teorii beta-eta. Czy te dwie teorie mają pośrednią, rodzaj pośredniej reguły eta, która daje spójną teorię przepisywania? Czy istnieje jakieś interesujące pojęcie częściowej ekstensywności, któremu ono odpowiada? Jest to drugie pytanie, które zadałem w ramach pośredniej eta, …
3
Sprawdzenie wzorów dwa kwantyfikatorów (
Solwery SAT dają potężny sposób na sprawdzenie poprawności formuły logicznej za pomocą jednego kwantyfikatora. Na przykład, aby sprawdzić poprawność , możemy użyć solwera SAT, aby ustalić, czy φ ( x ) jest zadowalające. Aby sprawdzić ważność ∀ x . φ ( x ) , możemy użyć solwera SAT do ustalenia, …
1
Logiczne reakcje na system impredykatywny w predykatywnej metateorii
Relacje logiczne dla języków impredykatywnych, takich jak System F, wydają się krytycznie opierać na impredykatywności logiki otoczenia. W szczególności interpretacja typu forall zostanie zdefiniowana w kategoriach wszystkich relacji typowanych. W systemie impredykatywnym (jak CiC / Coq) jest w porządku, ale wydaje się to niemożliwe w systemie predykcyjnym (jak Agda). Jak …
1
Porównanie złożoności teorii Kołmogorowa
Twierdzenie Chaitina o niekompletności mówi, że żadna wystarczająco silna teoria arytmetyki nie może udowodnić, że gdzie K ( s ) to złożoność Kołmogorowa ciągów s, a L jest wystarczająco dużą stałą. L jest wystarczająco duży, jeśli jest większy niż rozmiar w bitach maszyny sprawdzającej proof (PCM). PCM dla teorii T …
1
Czy potrafimy rozróżnić metody ściśle składniowe i semantyczne w języku programowania?
Chociaż dyskusje dowodzą silnych dowodów na normalizację, komentarz ten kontrastuje „model form normalnych” z „metodami czysto składniowymi”. To sprowadza mnie z powrotem do bardziej podstawowego pytania: czy nadal możemy dokładnie rozróżniać konstrukcje składniowe i semantyczne w obliczu modeli opartych na składni? Co z modelami terminów dla algeb, modelami Henkina dla …
4
Czy eta-równoważność funkcji jest zgodna z sekwencją Haskella?
Lemat: Zakładając, że równoważność eta istnieje (\x -> ⊥) = ⊥ :: A -> B. Dowód: ⊥ = (\x -> ⊥ x)przez eta-równoważność i (\x -> ⊥ x) = (\x -> ⊥)redukcję pod lambda. Raport Haskell 2010, rozdział 6.2 określa seqfunkcję na podstawie dwóch równań: seq :: a -> b …
1
Matematyczny (kategoryczny) opis klas typów
Język funkcjonalny można postrzegać jako kategorię, w której jego obiektami są typy, a między nimi funkcjonują morfizmy. Jak pasują klasy w tym modelu? Zakładam, że powinniśmy brać pod uwagę tylko te implementacje, które spełniają ograniczenie większości klas typów, ale które nie są wyrażone w języku Haskell. Na przykład powinniśmy brać …
3
Jak trudno jest zredukować terminację do częściowej poprawności?
Jeśli jesteś zaznajomiony z weryfikacją programu, prawdopodobnie wolisz przeczytać pytanie przed tłem . Jeśli nie jesteś zaznajomiony z weryfikacją programu, być może nadal będziesz w stanie odpowiedzieć na to pytanie, ale prawdopodobnie wolisz najpierw przeczytać tło . tło Często mówi się, że sprawdzenie częściowej poprawności jest nierozstrzygalne. Dla celów dyskusji …
1
Wnioski z odwrotnej siły matematycznej twierdzenia graf moll
Załóżmy, że mamy właściwość grafu, którą można sprawdzić w niedeterministycznym czasie wielomianowym, oraz dowód w słabym systemie formalnym (powiedzmy RCA 0 ), że właściwość jest nieznacznie zamknięta. Czy możemy powiedzieć coś o sile systemu formalnego, który jest w stanie udowodnić, że dany skończony zestaw wykluczonych nieletnich charakteryzuje daną właściwość graficzną? …
1
Dlaczego Martin-Löf potrzebował stworzyć intuicyjną teorię typów?
Czytałem o Intuitionistic Type Theory (ITT) i to ma sens. Ale staram się zrozumieć, dlaczego „dlaczego” zostało stworzone? Intuicyjna logika (IL) i prosty typ rachunek (STLC) i teoria typów ogólnie poprzedzają samo istnienie samego Martina-Löfa! Wydaje się, że w STLC można zrobić wszystko, co jest możliwe w ITT (mogę się …
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.