Pytania otagowane jako lo.logic

Logika obliczeniowa i matematyczna.

1
Równowaga w grze w postój
Rozważ następującą grę 2-osobową: Natura losowo wybiera program Każdy gracz gra liczbę w [0, nieskończoność] włącznie w odpowiedzi na ruch natury Weź minimalną liczbę graczy i uruchom program dla (maksymalnie) tak wielu kroków (chyba że obaj gracze wybiorą nieskończoność) Jeśli program się zatrzyma, gracz, który zagrał minimalną liczbę, otrzymuje 1 …
1
Niekompletna podstawa kombinacji
Jest to inspirowane tym pytaniem. Niech będzie zbiorem wszystkich kombinacji, które mają tylko dwie powiązane zmienne. Czy kombinatorycznie kompletny?C.dodo\mathcal{C}dodo\mathcal{C} Uważam, że odpowiedź jest przecząca, jednak nie udało mi się znaleźć odniesienia do tego. Byłbym również zainteresowany referencjami na dowody kombinatorycznej niekompletności zestawów kombinatorów (rozumiem, dlaczego zestaw składający się z kombinatorów …
1
Czy w teorii typów istnieje dobre pojęcie o braku terminacji i zatrzymaniu dowodów?
Konstruktywna teoria typów z jej podstawową interpretacją w ramach korespondencji curry-howard składa się wyłącznie z całkowitych, obliczalnych funkcji. W literaturze niektórzy mówili o stosowaniu „teorii typów obliczeniowych” w celu przedstawienia nieterminacji w programach funkcjonalnych, ale w artykułach, na które się natknąłem, nie wydaje się to być główną motywacją dla teorii …
1
Czy `sort 'można pisać na elementarnej logice afinicznej?
Następujący termin λ, tutaj w formie normalnej: sort = (λabc.(a(λdefg.(f(d(λhij.(j(λkl.(k(λmn.(mhi))l)) (h(λkl.l)i)))(λhi.(i(λjk.(bd(jhk)))(bd(h(λjk.(j (λlm.m)k))c)))))e))(λde.e)(λde.(d(λfg.g)e))c)) Implementuje algorytm sortowania dla list zakodowanych w kościele. Oznacza to, że wynik: sort (λ c n . (c 3 (c 1 (c 2 n)))) β→ (λ c n . (c 1 (c 2 (c 3 n)))) Podobnie, sort_below …
1
Odniesienie do faktu, że (0 = 1) oznacza fałsz, wymaga wszechświata w MLTT
Jest to dość dobrze znany fakt, że wywodzenie sprzeczności z nierówności (na przykład ) w teorii typu Martina-Loefa wymaga wszechświata.(0=1)→⊥(0=1)→⊥(0=1) \to \bot Dowód jest również dość prosty - w przypadku braku wszechświatów możemy usunąć zależności od dowolnego typu zależnego, aby uzyskać prosty typ jako jego kształt, a więc udowodnienie, że …
1
Teoria typów homotopii i twierdzenia o niekompletności Gödla
Twierdzenia Kurta Gödela o niekompletności ustanawiają „nieodłączne ograniczenia wszystkich oprócz najbardziej trywialnych systemów aksomatycznych zdolnych do wykonywania arytmetyki”. Teoria typów homotopii stanowi alternatywną podstawę dla matematyki, podstawę jednoznaczną opartą na wyższych typach indukcyjnych i aksjomat jedności . Książka HoTT wyjaśnia, że typy są wyższe groupoids funkcje są funktory, rodziny typu …
1
Dowody w
W przemówieniu Razborowa opublikowano dziwne oświadczenie. Jeśli FACTORING jest trudny, to małe twierdzenie Fermata nie jest możliwe do udowodnienia w S12S21S_{2}^{1} . Co to jest S12S21S_{2}^{1} i dlaczego aktualnych dowodów nie ma w S12S21S_{2}^{1} ?
1
Bilansowanie formuł boolowskich w
Szukam referencji na temat złożoności problemu równoważenia formuł logicznych . W szczególności, Czy było wiadomo, że formuły logiczne można wyważyć w AC0AC0\mathsf{AC^0} ? Czy istnieje prosty dowód na to, że równoważenie boolowskiej formuły jest w AC0AC0\mathsf{AC^0} ? Przez „proste” mam na myśli dowód prostsze niż ten wspominam poniżej, w szczególności …
2
O Inverse 3-SAT
Kontekst : Kavvadias i Sideri wykazali, że odwrotny problem 3-SAT jest coNP zakończony: Biorąc pod uwagę ϕϕ\phi zestaw modeli nnn zmiennych, czy istnieje wzór 3-CNF taki, że ϕϕ\phi jest jego dokładnym zestawem modeli? Powstaje formuła bezpośredniego kandydata, która jest połączeniem wszystkich 3-klauzul spełnionych przez wszystkie modele w ϕϕ\phi . Ponieważ …
1
Twierdzenie o bezpośredniej sumie dla złożoności przestrzeni klauzuli rozdzielczości?
Rozwiązanie to program mający na celu wykazanie niezadowalającej wartości CNF. Dowodem na rozwiązanie jest logiczne odjęcie pustej klauzuli dla klauzul początkowych w CNF. W szczególności każdy punkt początkowy można wywnioskować, i dwóch punktach ∨ x i B ∨ Kontakty x klauzula ∨ B można wywnioskować, jak również. Odrzucenie jest sekwencją …
1
Obliczeniowe konsekwencje twierdzenia Friedmana (nie do udowodnienia) na temat przesunięcia górnego o stałym punkcie?
Harvey Friedman wykazał, że istnieje dokładny wynik punktu stałego, którego nie można udowodnić w ZFC (zwykła teoria mnogości Zermelo-Frankela z Axiom of Choice). Wiele współczesnych układów logicznych opiera się na operatorach stałoprzecinkowych, więc zastanawiałem się: czy są znane konsekwencje twierdzenia o przesunięciu górnego przesunięcia dla teoretycznej informatyki? Nie do udowodnienia …
1
Jakie jest odniesienie do pierwszego twierdzenia Gödela o niekompletności opartego na nierozstrzygalności problemu zatrzymania?
Słabsza forma pierwszego twierdzenia Gödela o niekompletności, którego bezpośrednie dowody są w sposób Gödela długotrwałe, zaangażowane, aw niektórych miejscach raczej sprzeczne z intuicją, ma prosty i intuicyjny dowód oparty na nierozstrzygalności problemu zatrzymania - patrz na przykład https: / /en.wikipedia.org/wiki/Halting_problem#Sketch_of_proof Kto pierwszy zaproponował ten dowód iw jakim artykule lub książce …
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.