Pytania otagowane jako proof-theory

Pytania dotyczące analizy dowodów w teoriach

3
Curry-Howard i programy z niekonstruktywnych dowodów
To jest kolejne pytanie do Jaka jest różnica między dowodami a programami (lub między propozycjami i typami)? Jaki program odpowiadałby niekonstruktywnemu (klasycznemu) dowodowi formy ? (Załóżmy, że jest interesującą zależnością rozstrzygalną, np. ta TM nie zatrzymuje się w krokach ).∀k T(e,k)∨¬∀k T(e,k)∀k T.(mi,k)∨¬∀k T.(mi,k)\forall k \ T(e,k) \lor \lnot \forall …
1
Typy indukcyjne dla dużych policzalnych notacji porządkowych.
Chcę budować notacje dla dużych policzalnych porządków w „naturalny sposób”. Przez „naturalny sposób” rozumiem, że biorąc pod uwagę typ danych indukcyjnych X, równość ta powinna być zwykłą rekurencyjną równością (ta sama, deriving Eqktórą wytworzyłby Haskell), a kolejność powinna być zwykłym rekurencyjnym porządkiem leksykograficznym (tym samym, co deriving Ordw Haskell dałby …
1
Czy są typy typów? (Jakie są dokładnie typy?)
Dużo czytałem o systemach typów i takie i rozumiem z grubsza, dlaczego zostały wprowadzone (w celu rozwiązania paradoksu Russela). Rozumiem też z grubsza ich praktyczne znaczenie w językach programowania i systemach sprawdzających. Nie jestem jednak do końca pewien, czy moje intuicyjne wyobrażenie o typie jest prawidłowe. Moje pytanie brzmi: czy …
3
podświetlany i polaryzujący typy Pi
W ostatnim wątku na liście mailingowej Agdy pojawiło się pytanie o prawa ηη\eta , w których Peter Hancock wypowiedział się prowokująco . Rozumiem, że prawa ηη\eta mają typy negatywne, tj. łączniki, których zasady wprowadzania są odwracalne. Aby wyłączyć ηη\eta dla funkcji, Hank sugeruje użycie niestandardowego eliminatora, funsplit , zamiast zwykłej …
3
Czy możemy udowodnić słabą normalizację dla Systemu F poprzez indukcję na transfinite porządkowej
Słabą normalizację dla prostego rachunku lambda o typie można udowodnić (Turinga) przez indukcję na . Rozszerzony rachunek lambda z rekursorami na liczbach naturalnych (Gentzen) ma słabą strategię normalizacji przez indukcję na ϵ 0 .ω2ω2\omega^2ϵ0ϵ0\epsilon_0 Co z systemem F (lub słabszym)? Czy w tym stylu jest słaby dowód normalizacji? Jeśli nie, …
2
Czy rozstrzyganie propozycji jest kompletnym systemem dowodowym?
To pytanie dotyczy logiki zdań i wszystkie wystąpienia „rozstrzygania” należy interpretować jako „rozstrzyganie zdań”. To pytanie jest bardzo proste, ale od dłuższego czasu mnie niepokoi. Widzę, że ludzie twierdzą, że rozwiązanie zdań jest kompletne, ale widzę też, że ludzie twierdzą, że rozwiązanie jest niepełne. Rozumiem sens niepełnej rozdzielczości. Rozumiem również, …
1
Szukasz artykułów i artykułów na temat Tarskian Möglichkeit
Pewne tło: logika wielowartościowa Łukasiewicza miała być logiką modalną, a Łukasiewicz podał ekstensywną definicję operatora modalnego: ◊ A =ree f¬ A → A◊ZA=remifa¬ZA→ZA\Diamond A =_{def} \neg A \to A (który przypisuje Tarskiemu). Daje to dziwną logikę modalną, z pewnymi paradoksalnymi, jeśli nie pozornie absurdalnymi twierdzeniami, w szczególności . Zastępca ¬ …
1
Względna spójność PA i niektórych teorii typów
Dla teorii typów przez spójność rozumiem, że ma typ, który nie jest zamieszkany. Z silnej normalizacji sześcianu lambda wynika, że ​​układ FFF i układ FωFωF_\omega są spójne. Typy indukcyjne MLTT + mają również dowód normalizacji. Jednak wszystkie powinny być wystarczająco mocne, aby zbudować model PA, co dowodzi, że PA jest …
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 …
2
Odniesienia do języków programowania opartych na logice warunkowej
Logiki warunkowe to logiki, które rozszerzają tradycyjną implikację logiczną za pomocą operatorów modalnych odpowiadających innym pojęciom warunku (na przykład przyczynowy warunkowy brzmi „ powoduje„ B ”lub warunkowanie probabilistyczne „ ”, które brzmi „ dany B ”).A A | B AA□→BA◻→BA\; \square\!\!\!\!\to BAAAA|BA|BA|BAAABBB Zazwyczaj logiki te są badane teoretycznie modelowo, ale …
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.