Pytania otagowane jako lo.logic

Logika obliczeniowa i matematyczna.

7
Solidne zastosowania teorii kategorii w TCS?
Nauczyłem się kilku fragmentów teorii kategorii. Z pewnością jest to inny sposób patrzenia na rzeczy. (Bardzo ogólne podsumowanie dla tych, którzy go nie widzieli: teoria kategorii daje sposoby wyrażania wszelkiego rodzaju zachowań matematycznych wyłącznie w kategoriach funkcjonalnych związków między obiektami. Na przykład rzeczy takie jak iloczyn kartezjański dwóch zbiorów są …
5
Techniki odwracania porządku kwantyfikatorów
Dobrze wiadomo, że ogólnie nie można odwrócić kolejności uniwersalnych i egzystencjalnych kwantyfikatorów. Innymi słowy, dla logicznego ogólnym wzorze ,ϕ(⋅,⋅)ϕ(⋅,⋅)\phi(\cdot,\cdot) (∀x)(∃y)ϕ(x,y)⇎(∃y)(∀x)ϕ(x,y)(∀x)(∃y)ϕ(x,y)⇎(∃y)(∀x)ϕ(x,y)(\forall x)(\exists y) \phi(x,y) \quad \not\Leftrightarrow \quad (\exists y)(\forall x) \phi(x,y) Z drugiej strony wiemy, że prawa strona jest bardziej restrykcyjna niż lewa; czyli (∃y)(∀x)ϕ(x,y)⇒(∀x)(∃y)ϕ(x,y)(∃y)(∀x)ϕ(x,y)⇒(∀x)(∃y)ϕ(x,y)(\exists y)(\forall x) \phi(x,y) \Rightarrow (\forall x)(\exists …
7
Jakie interesujące twierdzenia w TCS opierają się na Axiom of Choice? (Lub alternatywnie, aksjomat determinacji?)
Matematycy czasem martwią się o aksjomat wyboru (AC) i aksjomat determinacji (AD). Aksjomat wyboru : Biorąc pod uwagę dowolny zbiór z niepustych zestawach jest funkcja , które, biorąc pod uwagę zestaw w , zwraca element z .CC{\cal C}fffSSSCC{\cal C}SSS Aksjomat Determinacji : Niech będzie zbiorem nieskończenie długich ciągów bitów. Alice …
8
Czy istnieją dowody istnienia niekonstruktywnego algorytmu?
Pamiętam, że mogłem spotkać odniesienia do problemów, które zostały udowodnione, że można je rozwiązać ze szczególną złożonością, ale bez znanego algorytmu, który by faktycznie osiągnął tę złożoność. Walczę z tym, jak to się dzieje; jak wyglądałby niekonstruktywny dowód na istnienie algorytmu. Czy rzeczywiście istnieją takie problemy? Czy mają dużą wartość …
3
Płytkie kontra głębokie osadzanie
Podczas kodowania logiki w asystencie dowodu, takim jak Coq lub Isabelle, należy dokonać wyboru między użyciem płytkiego a głębokiego osadzenia. W płytkim osadzaniu formuły logiczne są zapisywane bezpośrednio w logice twierdzenia twierdzącego, podczas gdy w głębokim osadzaniu formuły logiczne są reprezentowane jako typ danych. Jakie są zalety i ograniczenia różnych …
5
Jakiej najbardziej intuicyjnej teorii typów zależnych mógłbym się nauczyć?
Jestem zainteresowany uzyskaniem naprawdę solidnego zrozumienia zależnego pisania. Przeczytałem większość TaPL i przeczytałem (jeśli nie w pełni zaabsorbowane) „Typy zależne” w ATTaPL . Przeczytałem również i przejrzałem kilka artykułów na temat pisania zależnego. Wiele dyskusji na temat teorii typów wydaje się koncentrować na dodawaniu funkcji przyrostowych do poprzednich systemów typów, …
3
Jak działają „taktyki” w asystentach dowodowych?
Pytanie: Jak działają „taktyki” w asystentach dowodowych? Wydają się być sposobami na określenie, jak przepisać termin na równoważny (dla pewnej definicji „równoważnego”). Przypuszczalnie istnieją formalne zasady dotyczące tego, w jaki sposób mogę dowiedzieć się, czym one są i jak działają? Czy wiążą się one z czymś więcej niż tylko wyborem …
2
Wyjaśnienie funktora aplikacyjnego w kategoriach kategorycznych - funktory monoidalne
Chciałbym zrozumieć Applicativew kategoriach teorii kategorii. Dokumentacja dla Applicativetwierdzi, że jest to silny funktor LAX monoidal . Po pierwsze, strona Wikipedii o funktorach monoidalnych mówi, że funktor monoidalny jest luźny lub silny . Wydaje mi się więc, że jedno ze źródeł jest niepoprawne lub używają terminów inaczej. Czy ktoś może …
4
Czy są jakieś dowody na nierozstrzygalność problemu zatrzymania, który nie zależy od samoreferencji lub diagonalizacji?
To pytanie jest z tym związane . Po wielu rozmowach po raz kolejny, w znacznie prostszej formie, wydawało się, że to zupełnie inne pytanie. Klasyczny dowód nierozstrzygalności problemu zatrzymania zależy od wykazania sprzeczności przy próbie nałożenia na siebie hipotetycznego decydenta HALT. Myślę, że oznacza to po prostu niemożność posiadania decydenta …
5
Czy istnieje logika bez indukcji, która wychwytuje dużą część P?
Twierdzenie Immermana- Vardiego stwierdza, że ​​PTIME (lub P) to właśnie klasa języków, którą można opisać zdaniem logiki pierwszego rzędu wraz z operatorem punktu stałego, nad klasą uporządkowanych struktur. Operator punktu stałego może być albo najmniejszym punktem stałym (według Immermana i Vardiego), albo inflacyjnym punktem stałym. (Stephan Kreutzer, Ekspresyjna równoważność logiki …
5
Wyniki w teoretycznej CS niezależnej od ZFC
Zadam dość niejasne pytanie, ponieważ granica między informatyką teoretyczną a matematyką nie zawsze jest łatwa do rozróżnienia. PYTANIE: Czy znasz jakieś interesujące wyniki w CS, które są albo niezależne od ZFC (tj. Standardowa teoria zbiorów), albo które zostały pierwotnie udowodnione w ZFC (+ niektóre inne aksjomaty), a dopiero później udowodnione …
2
Aksjomaty niezbędne w informatyce teoretycznej
To pytanie jest inspirowane podobnym pytaniem o matematykę stosowaną w matematycznym przepływie i ta dokuczliwa myśl, że ważne pytania TCS, takie jak P vs. NP, mogą być niezależne od ZFC (lub innych systemów). Jako małe tło, matematyka odwrotna to projekt znalezienia aksjomatów niezbędnych do udowodnienia pewnych ważnych twierdzeń. Innymi słowy, …
3
Rozszerzona teza kościelna
Jednym z najczęściej dyskutowanych pytań na stronie było to, co oznaczałoby obalenie tezy Kościoła . Wynika to częściowo z faktu, że Dershowitz i Gurevich opublikowali w 2008 r. Dowód, że teza Kościoła to Biuletyn Symboliki Logicznej. - bezwstydna autopromocja - napisałem wpis na blogu ). To pytanie dotyczy rozszerzonej tezy …
4
Zgodność między klasami złożoności a logiką
Raz wziąłem klasę na temat obliczalności i logiki. Materiał zawiera korelację między klasami złożoności / obliczalności (R, RE, co-RE, P, NP, Logspace, ...) i Logiką (rachunek predykatów, logika pierwszego rzędu, ...). Korelacja obejmowała kilka wyników w jednym polu, które zostały uzyskane przy użyciu technik z drugiego pola. Przypuszczano, że P! …
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.