Pytania otagowane jako lo.logic

Logika obliczeniowa i matematyczna.

4
Rozpoczęcie pracy z rozwiązaniami SAT
Chcę zrobić pierwszy solver SAT. Znam konkurs SAT i konferencję SAT i jest tak wiele artykułów na ten temat. Jestem starterem, przytłoczonym starterem. Od czego powinienem zacząć W końcu chcę wprowadzić najnowocześniejsze rozwiązania. Chcę porady ekspertów, jak zacząć, żeby nie marnować czasu na rzeczy nieistotne zbyt wcześnie. Wielkie dzięki.
2
Czy typy zależne dają ci wszystko, co robi podtyp?
Typy i języki programowania skupiają się dość mocno na subtypowaniu, ale o ile wiem, subtyping nie wydaje się szczególnie fundamentalny. Czy podtypowanie daje coś więcej niż typy zależne? Praca z typami zależnymi z pewnością będzie wymagała więcej pracy, więc rozumiem, dlaczego podtypy mogą być przydatne w praktyce. Jednak bardziej interesuje …
4
Kiedy (lub powinna) Teoretyczna CS dba o intuicyjne dowody?
Z tego, co rozumiem (co jest bardzo mało, więc proszę popraw mnie tam, gdzie się mylę!), Teoria języków programowania często dotyczy dowodów „intuicyjnych”. W mojej własnej interpretacji podejście to wymaga od nas poważnego potraktowania konsekwencji obliczeń dla logiki i sprawdzalności. Dowód nie może istnieć, chyba że istnieje algorytm konstruujący konsekwencje …
2
Jaki był pierwotny zamiar stworzenia rachunku Lambda?
Czytałem, że początkowo Kościół zaproponował -calculus jako część swoich postulatów z logiki (co jest gęstym odczytem). Ale Kleene udowodnił, że jego „system” jest niespójny, po czym Church wyodrębnił odpowiednie rzeczy do swojej pracy nad „skutecznym obliczeniem” i porzucił wcześniejsze prace nad logiką.λλ\lambda Tak jak ja rozumiem, -system i jego oznaczenia …
1
Zjednoczenie i eliminacja Gaussa
Czy ktoś zna odniesienia, które precyzyjnie określają związek między algorytmem unifikacji a eliminacją Gaussa? Szczególnie interesuje mnie związek między podstawieniami trójkątnymi a rozkładami LU. Wayne Snyder i Jean Gallier wspominają o tej analogii, przekazując w swojej pracy, Revisited Unification Higher Order: Complete Set of Transformations .
6
Program: Logiczne / formalne metody bezpieczeństwa
Obecnie prowadzę mały kurs (cztery dwugodzinne wykłady na poziomie magisterskim) na temat metod logicznych w zakresie bezpieczeństwa , chociaż tytuł Formalne metody w zakresie bezpieczeństwa może być bardziej trafny. Obejmuje krótko następujące tematy (wraz z powiązanymi metodami logicznymi): Cyfrowe zarządzanie prawami i egzekwowanie zasad (ogólna formalizacja, logika modalna, egzekwowanie za …
2
Obwody dolne granice i złożoność Kołmogorowa
Rozważ następujące uzasadnienie: Niech oznacza złożoność Kołmogorowa ciągu . Twierdzenie Chaitina o niekompletności tak mówiK(x)K(x)K(x)xxx dla jakiejkolwiek spójnej i wystarczająco silny system formalny , istnieje stała (zależnie tylko od formalnego systemu i jego języka) tak, że dla każdej struny , nie może udowodnić, że .SSSTTTxxxSSSK(x)≥TK(x)≥TK(x) \geq T Niech będzie funkcją …
1
Gdzie jest dowód, że Coq + Wykluczone Środek jest spójny
Widziałem (i słyszałem), że twierdził, że można bezpiecznie dodać klasyczny aksjomat wykluczonego środka do Coq, ale nie mogę znaleźć dokumentu potwierdzającego to twierdzenie. Artykuły, które widzę na liście na wiki Coq o wykluczonym środku, wykazują niespójność z impredykatywnym Setem. Rzeczywiście wydaje się, że Coquand stwierdza, że ​​dodanie Wykluczonego Środka (mieszkańca …
7
Skąd możemy wiedzieć, że metody formalne działają?
Ważnym celem metod formalnych jest udowodnienie poprawności systemów, za pomocą środków automatycznych lub kierowanych przez człowieka. Wydaje się jednak, że nawet jeśli podasz dowód poprawności, NIE będziesz w stanie zagwarantować, że system nie zawiedzie. Na przykład: Specyfikacja może niepoprawnie modelować system lub system produkcyjny może być zbyt skomplikowany, aby modelować, …
3
Czy możliwe są rekurencyjne formy wypowiedzi Godela?
Samoreferencyjność problemu P / NP była czasem podkreślana jako bariera dla jego rozwiązania, patrz na przykład artykuł Scotta Aaronsona, czy P vs. NP jest formalnie niezależny ? Jednym z wielu możliwych rozwiązań P / NP byłby dowód, że problem jest formalnie niezależny od ZFC lub prawdziwy, ale niemożliwy do udowodnienia. …
1
Niewielkie zamknięte właściwości, które są wyraźnie wyrażalne przez MSO
Poniżej MSO oznacza monadyczną logikę drugiego rzędu grafów z kwantyfikacjami zbioru wierzchołków i zbocza. Niech będzie niewielką zamkniętą rodziną grafów. Z teorii drugorzędnej grafu Robertsona i Seymour wynika, że charakteryzuje się skończoną listą zakazanych nieletnich. Innymi słowy, dla każdego wykresu mamy, że należy do wtedy i tylko wtedy, gdy wyklucza …
1
Stochastyczne obliczenia lambda Scotta
Ostatnio Dana Scott zaproponowała stochastyczny rachunek lambda, próbę wprowadzenia elementów probabilistycznych do (nietypowego) rachunku lambda w oparciu o semantykę zwaną modelem grafowym. Jego slajdy można znaleźć na przykład w Internecie , a jego artykuł w Journal of Applied Logic , t. 12 (2014). Jednak po szybkim przeszukaniu Internetu znalazłem podobne …
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.