Pytania otagowane jako logic

Pytania dotyczące logiki matematycznej i jej zastosowania w informatyce

5
Czy istnieje jakikolwiek konkretny związek między twierdzeniem o niekompletności Gödla, problemem zatrzymania a uniwersalnymi maszynami Turinga?
Zawsze myślałem niejasno, że odpowiedź na powyższe pytanie była twierdząca w następujący sposób. Twierdzenie Gödela o niekompletności i nierozstrzygalność problemu zatrzymania są zarówno negatywnymi wynikami rozstrzygalności, jak i ustalonymi na podstawie przekątnych argumentów (w latach 30. XX wieku), więc muszą być jakoś dwoma sposobami spojrzenia na te same sprawy. Pomyślałem, …
2
Co to jest koindukcja?
Słyszałem o indukcji (strukturalnej). Pozwala budować struktury skończone z mniejszych i zapewnia zasady dowodowe dla uzasadnienia takich struktur. Pomysł jest wystarczająco jasny. A co z koindukcją? Jak to działa? Jak można powiedzieć coś rozstrzygającego o nieskończonej strukturze? Są (przynajmniej) dwa kąty, którymi należy się zająć, a mianowicie koindukcja jako sposób …
3
Czym dokładnie jest logika?
Być może należałoby przeprosić za zadanie kolejnego pytania na temat warunków wstępnych, ale byłem zdezorientowany co do punktów wyjścia. Spotkałem różne terminy, takie jak „logika modalna”, „logika czasowa”, „logika pierwszego rzędu”, „logika drugiego rzędu” i „logika wyższego rzędu”. Co dokładnie oznacza „logika” w tym kontekście? Jak rygorystycznie definiujemy słowo „logika”? …
3
Wprowadzenie do teorii typów Martina-Löfa
Jakie byłoby najlepsze wprowadzenie do pomysłów Per Martina-Löfsa na temat teorii typów? Obejrzałem niektóre wykłady ze szkoły letniej w Oregon PL, ale nadal jestem zdziwiony następującym pytaniem: Jaki jest typ Wiem, co to jest zestaw, ponieważ można je zdefiniować za pomocą zwykłych aksjomatów ZF i mają one bardzo intuicyjny konkretny …
2
Charakterystyka terminów lambda, które mają typy związków
Wiele podręczników obejmuje typy przecięć w rachunku lambda. Reguły pisania dla przecięcia można zdefiniować w następujący sposób (na górze zwykłego rachunku lambda z podtypami): Γ⊢M:T1Γ⊢M:T2Γ⊢M:T1∧T2(∧I)Γ⊢M:⊤(⊤I)Γ⊢M.:T.1Γ⊢M.:T.2)Γ⊢M.:T.1∧T.2)(∧ja)Γ⊢M.:⊤(⊤ja) \dfrac{\Gamma \vdash M : T_1 \quad \Gamma \vdash M : T_2} {\Gamma \vdash M : T_1 \wedge T_2} (\wedge I) \qquad\qquad \dfrac{} {\Gamma \vdash M …
2
Dlaczego typ pustki C nie jest analogiczny do typu pusta / dolna?
Wikipedia, jak również inne źródła, które znalazłem, wskazują voidtyp C jako typ jednostki, a nie typ pusty. Uważam to za mylące, ponieważ wydaje mi się, że voidlepiej pasuje do definicji typu pustego / dolnego. voidO ile wiem, nie zamieszkują żadnych wartości . Funkcja z typem zwracanym void określa, że ​​funkcja …
28 type-theory  c  logic  modal-logic  coq  equality  coinduction  artificial-intelligence  computer-architecture  compilers  asymptotics  formal-languages  asymptotics  landau-notation  asymptotics  turing-machines  optimization  decision-problem  rice-theorem  algorithms  arithmetic  floating-point  automata  finite-automata  data-structures  search-trees  balanced-search-trees  complexity-theory  asymptotics  amortized-analysis  complexity-theory  graphs  np-complete  reductions  np-hard  algorithms  string-metrics  computability  artificial-intelligence  halting-problem  turing-machines  computation-models  graph-theory  terminology  complexity-theory  decision-problem  polynomial-time  algorithms  algorithm-analysis  optimization  runtime-analysis  loops  turing-machines  computation-models  recurrence-relation  master-theorem  complexity-theory  asymptotics  parallel-computing  landau-notation  terminology  optimization  decision-problem  complexity-theory  polynomial-time  counting  coding-theory  permutations  encoding-scheme  error-correcting-codes  machine-learning  natural-language-processing  algorithms  graphs  social-networks  network-analysis  relational-algebra  constraint-satisfaction  polymorphisms  algorithms  graphs  trees 
4
Czyste, intuicyjne wyprowadzenie kombinatora stałoprzecinkowego (kombinator Y)?
Kombinator stałoprzecinkowy FIX (znany również jako kombinator Y) w (niepoprawnym) rachunku lambda ( ) jest zdefiniowany jako:λλ\lambda FIX≜λf.(λx.f (λy.x x y)) (λx.f (λy.x x y))≜λf.(λx.f (λy.x x y)) (λx.f (λy.x x y))\triangleq \lambda f.(\lambda x. f~(\lambda y. x~x~y))~(\lambda x. f~(\lambda y. x~x~y)) Rozumiem jego cel i doskonale mogę śledzić wykonanie …
6
Generowanie kombinacji z zestawu par bez powtarzania elementów
Mam zestaw par. Każda para ma taką postać (x, y), że x, y należą do liczb całkowitych z zakresu [0,n). Jeśli więc n wynosi 4, to mam następujące pary: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) Mam już pary. Teraz muszę zbudować kombinację za pomocą n/2par, tak aby żadna liczba całkowita …
7
Dlaczego A oznacza, że ​​B jest prawdziwe, jeśli A jest fałszywe, a B jest fałszywe?
Wydaje mi się, że „implikacja” w języku angielskim nie oznacza tego samego, co operator logiczny „implikuje”, podobnie jak słowo „LUB” w większości przypadków oznacza „Wyłączne OR” w naszym codziennym użyciu języka. Weźmy dwa przykłady: Jeśli dzisiaj jest poniedziałek, jutro jest wtorek. To prawda . Ale jeśli powiemy: Jeśli słońce jest …
4
Czy w logice konstruktywistycznej istnieją niezdecydowane języki?
Logika konstruktywistyczna to system, który usuwa Prawo Akceptowanego Środka, a także Podwójną Negację, jako aksjomaty. Jest opisany na Wikipedii tutaj i tutaj . W szczególności system nie dopuszcza dowodu sprzeczności. Zastanawiam się, czy ktoś wie, jak to wpływa na wyniki dotyczące maszyn Turinga i języków formalnych? Zauważam, że prawie każdy …
5
rachunek z odbiciem
Szukam prostego rachunku, który obsługuje rozumowanie na temat refleksji , a mianowicie introspekcji i manipulacji uruchomionymi programami. Czy istnieje nietypowe rozszerzenie -calculus, które umożliwia konwersję -terms do postaci, którą można manipulować składniowo, a następnie oceniać?λλλ\lambdaλλ\lambda Wyobrażam sobie, że rachunek składa się z dwóch głównych dodatkowych terminów: r e f l …
11
Dlaczego
Chciałbym wiedzieć, czy istnieje zasada, aby to udowodnić. Na przykład, jeśli użyję prawa dystrybucyjnego, dostanę tylko (A∨A)∧(A∨¬B)(ZA∨ZA)∧(ZA∨¬b)(A \lor A) \land (A \lor \neg B) .
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.