Pytania otagowane jako lo.logic

Logika obliczeniowa i matematyczna.

4
Jakie są różnice między relacjami logicznymi a symulacjami?
Jestem początkującym pracującym nad metodami potwierdzającymi równoważność programu. Przeczytałem kilka artykułów na temat definiowania relacji logicznych lub symulacji, aby udowodnić, że dwa programy są równoważne. Ale jestem dość zdezorientowany co do tych dwóch technik. Wiem tylko, że relacje logiczne są definiowane indukcyjnie, podczas gdy symulacje oparte są na koindukcji. Dlaczego …
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 istnieje rozsądny zautomatyzowany system dowodowy dla twierdzeń TCS?
Załóżmy, że chciałem sformalizować dowód Turinga dotyczący problemu zatrzymania, aby maszyna mogła to sprawdzić. Niektóre ze znanych automatycznych systemów dowodzenia twierdzeń obejmują Mizar, Coq i HOL4. Pobrałem i eksperymentowałem z Coq, ale nie ma biblioteki dla maszyn Turinga. Sam pomyślałem o kodowaniu jednego, ale brakowało tego samouczka, a język był …
4
Twierdzenie Kościoła i twierdzenia o niekompletności Gödla
Niedawno czytałem o niektórych pomysłach i historii przełomowej pracy wykonanej przez różnych logików i matematyków w zakresie obliczeń. Podczas gdy poszczególne koncepcje są dla mnie dość jasne, staram się dobrze zrozumieć wzajemne relacje i abstrakcyjny poziom, na którym wszystkie są ze sobą powiązane. Wiemy, że twierdzenie Kościoła (a raczej niezależne …
6
Dobrze znane klasy wzorów boolowskich, które wymagają wykładniczo długich prób rozdzielczości
W solverach SAT często można znaleźć metody płaszczyzny cięcia, zmienną propagację, odgałęzienie i wiązanie, uczenie się klauzul, inteligentne cofanie, a nawet ręcznie tkaną ludzką heurystykę. Jednak przez dziesięciolecia najlepsze solwery SAT polegały w dużej mierze na technikach sprawdzania rozdzielczości i używają kombinacji innych rzeczy po prostu do pomocy i do …
1
Interesujące algorytmy w formalizacji twierdzenia Feit-Thompson?
Wygląda na to, że George Gonthier i jego współpracownicy zakończyli formalizację Twierdzenia o nieparzystym porządku . We wcześniejszej pracy nad twierdzeniem o czterech kolorach Gonthier wynalazł szereg nowych algorytmów (głównie wariantów BDD i algorytmów grafowych), które były szczególnie podatne na formalną weryfikację. Ponieważ powiedział, że nadal stosuje ten weryfikacyjny styl …
5
Jaka jest różnica między dowodami a programami (lub między propozycjami i typami)?
To pytanie zostało przeniesione z przepełnienia stosu, ponieważ można na nie odpowiedzieć na teoretycznej wymianie stosu komputerów. Migrował 8 lat temu . Biorąc pod uwagę, że Korespondencja Curry-Howarda jest tak szeroko rozpowszechniona / rozszerzona, czy istnieje jakaś różnica między dowodami a programami (lub między propozycjami i typami)? Czy naprawdę możemy …
3
Tłumaczenie SAT z HornSAT
Czy można przetłumaczyć wzór B logiczny na równoważną kombinację klauzul Horna? Artykuł w Wikipedii na temat HornSAT wydaje się sugerować, że tak, ale nie byłem w stanie ścigać żadnego odniesienia. Zauważ, że nie mam na myśli „w czasie wielomianowym”, ale raczej „w ogóle”.
5
Czy istnieją adnotowane formalne systemy weryfikacji dla czysto funkcjonalnych języków programowania?
ACSL (Ansi C Specification Language), to specyfikacja kodu C, opatrzona specjalnymi komentarzami, która pozwala na formalną weryfikację kodu C. Nie przyjrzałem się temu, ale wyobrażam sobie, że metody formalne stosowane w weryfikatorach ACSL byłyby podobne do Hoare Logic. Jednak w przypadku czysto funkcjonalnych języków, takich jak Haskell, nie mogę sobie …
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 …
4
Dlaczego potrzebujemy formalnej semantyki dla logiki predykatów?
Rozważ to pytanie rozwiązane. Nie wybiorę najlepszej odpowiedzi, ponieważ wszystkie one przyczyniły się do mojego zrozumienia tego tematu. Nie jestem pewien, jakie korzyści przyniesie nam formalne zdefiniowanie semantyki logiki predykatów. Ale widzę wartość posiadania formalnego rachunku próbnego. Chodzi mi o to, że nie potrzebowalibyśmy formalnej semantyki, aby uzasadnić reguły wnioskowania …
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.