Pytania otagowane jako lo.logic

Logika obliczeniowa i matematyczna.

3
Jakie algorytmy są znane z obliczania interpolantów Craiga?
Czy istnieje przegląd algorytmów obliczania interpolantów? Co z artykułami na temat tylko jednego algorytmu? Najbardziej interesuje mnie przypadek i C = q plus ograniczenie, że interpolant jest tak mały, jak to możliwe. (Znam pracę McMillana z 2005 roku , która opisuje, jak uzyskać interpolanty, unikając kwantyfikatorów.)A=¬p∧qA=¬p∧qA=\lnot p\land qC=qC=qC=q Tło: Interpolacja …
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 …
5
Czy można sprawdzić, czy liczba obliczalna jest wymierna czy całkowita?
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane z faktem, że nie można sprawdzić, czy dwie …
18 computability  computing-over-reals  lambda-calculus  graph-theory  co.combinatorics  cc.complexity-theory  reference-request  graph-theory  proofs  np-complete  cc.complexity-theory  machine-learning  boolean-functions  combinatory-logic  boolean-formulas  reference-request  approximation-algorithms  optimization  cc.complexity-theory  co.combinatorics  permutations  cc.complexity-theory  cc.complexity-theory  ai.artificial-intel  p-vs-np  relativization  co.combinatorics  permutations  ds.algorithms  algebra  automata-theory  dfa  lo.logic  temporal-logic  linear-temporal-logic  circuit-complexity  lower-bounds  permanent  arithmetic-circuits  determinant  dc.parallel-comp  asymptotics  ds.algorithms  graph-theory  planar-graphs  physics  max-flow  max-flow-min-cut  fl.formal-languages  automata-theory  finite-model-theory  dfa  language-design  soft-question  machine-learning  linear-algebra  db.databases  arithmetic-circuits  ds.algorithms  machine-learning  ds.data-structures  tree  soft-question  security  project-topic  approximation-algorithms  linear-programming  primal-dual  reference-request  graph-theory  graph-algorithms  cr.crypto-security  quantum-computing  gr.group-theory  graph-theory  time-complexity  lower-bounds  matrices  sorting  asymptotics  approximation-algorithms  linear-algebra  matrices  max-cut  graph-theory  graph-algorithms  time-complexity  circuit-complexity  regular-language  graph-algorithms  approximation-algorithms  set-cover  clique  graph-theory  graph-algorithms  approximation-algorithms  clustering  partition-problem  time-complexity  turing-machines  term-rewriting-systems  cc.complexity-theory  time-complexity  nondeterminism 
2
Czy można zdecydować równoważność w Systemie F (lub innym typowym rachunku λ)?
Wiem, że nie można zdecydować równoważności dla niepoprawnego rachunku lambda. Cytując Barendregt, HP Rachunek lambda: jego składnia i semantyka. Północna Holandia, Amsterdam (1984). :ββ\beta Jeśli A i B są rozłączne, niepuste zbiory terminów lambda, które są zamknięte na zasadzie równości, to A i B są rekurencyjnie nierozdzielne. Wynika z tego, …
3
Reguła ramki jako preserver zmian?
Reguła rama , jak ten podany poniżej, oddaje ideę, że, biorąc pod uwagę program cz warunkiem p, że posiada zanim skończy i postcondition qktóra posiada potem jakiś warunek rozłączne rpowinny utrzymać zarówno przed jak i po cserii. ( *Łącznik wymaga, aby jego argumenty były rozłączne.) Często warunki wstępne i końcowe …
4
Jaki jest sens konwersji
Myślę, że tego nie rozumiem, ale konwersja wygląda na mnie jako konwersja β , która nic nie robi, szczególny przypadek konwersji β, w której wynikiem jest tylko termin z abstrakcji lambda, ponieważ nie ma nic do zrobienia, rodzaj bezcelowej konwersji β .ηη\etaββ\betaββ\betaββ\beta Może więc konwersja jest czymś naprawdę głębokim i …
3
Klasyfikacja typowych / nietypowych rodzajów Lambda Calculi
Czy ktoś może krótko wyjaśnić (jeśli to możliwe!) Lub odesłać mnie do referencji, podsumowującej różnice między niepisanym rachunkiem lambda i bardziej popularnym typem rachunku lambda? Szczególnie szukam stwierdzeń o ich mocy ekspresyjnej, równoważności z systemami logicznymi / arytmetycznymi lub metodami obliczeniowymi oraz, w stosownych przypadkach, analogii do języków programowania. Chociaż …
1
Udowodnić nieistotność dowodu w Coq?
Czy istnieje sposób na udowodnienie następującego twierdzenia w Coq? Theorem bool_pirrel : forall (b : bool) (p1 p2 : b = true), p1 = p2. EDYCJA : Próba krótkiego wyjaśnienia „czym jest nieistotność dowodu” (popraw mnie, jeśli się mylę lub nieścisłość) Podstawowym założeniem jest to, że w świecie propozycja (lub …
1
Techniki wykazywania nieprzekraczalności w logice i innych formalnych systemach dowodowych
W systemach dowodowych dla klasycznej logiki zdań, jeśli chce się wykazać, że pewna formuła nie jest pochodna, po prostu pokazuje, że można uzyskać (chociaż z pewnością możliwe są inne techniki). Brak możliwości wyprowadzenia wynika zasadniczo z prawidłowości i kompletności systemu dowodowego.ψψ\psi¬ ψ¬ψ\neg\psi Niestety w przypadku nieklasycznej logiki i bardziej egzotycznych …
18 lo.logic 
1
Przestrzeń topologiczna związana z SAT: czy jest zwarta?
Spełnialności problemem jest to, oczywiście, podstawowym problemem teoretycznym CS. Bawiłem się jedną wersją problemu z nieskończenie wieloma zmiennymi. \newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}} Podstawowe ustawienia. Niech będzie niepustym i prawdopodobnie nieskończonym zestawem zmiennych . Dosłowność to albo zmienna albo jej negacja . Klauzula jest rozróżnieniem skończonej liczby literałów . Na koniec definiujemy formułę …
1
Czy niemożność obliczenia złożoności Kołmogorowa wynika z twierdzenia Lawpowa o punkcie stałym?
Wiele twierdzeń i „paradoksów” - przekątna Cantora, nierozstrzygalność nienawiści, nierozstrzygalność złożoności Kołmogorowa, niekompletność Gödela, niekompletność Chaitina, paradoks Russella itp. - wszystkie mają w zasadzie ten sam dowód po przekątnej (zauważ, że jest to bardziej specyficzne niż to, że mogą wszystko to można udowodnić za pomocą diagonalizacji; wydaje się raczej, że …
2
Najmniejszy możliwy uniwersalny kombinator
Szukam najmniejszego możliwego uniwersalnego kombinatora , mierzonego liczbą abstrakcji i aplikacji wymaganych do określenia takiego kombinatora w rachunku lambda . Przykłady uniwersalnych kombinatorów obejmują: rozmiar 23: λf.f (fS (KKKI)) K. rozmiar 18: λf.f (fS (KK)) K. rozmiar 14: λf.fKSK rozmiar 12: λf.fS (λxyz.x) rozmiar 11: λf.fSK gdzie S = λxyz.xz …
1
Jaka jest kategoryczna semantyka podtypów?
Począwszy od Curry-Howarda-Lambka, pojawiła się niezła trójca typów teorii, logiki i kategorii. Jestem ciekawy, jaką semantyczną kategorię uzyskujesz, gdy dodajesz (przymus) podtyp do teorii typów - wygląda na to, że nie zostało to zbytnio zbadane, jeśli w ogóle. Ogólnie rzecz biorąc, dodanie przymusowego podtypu do teorii typów nie rujnuje jego …
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.