Pytania otagowane jako automated-theorem-proving

Automatyczne dowodzenie twierdzeń to dowodzenie twierdzeń matematycznych przez program komputerowy.

2
Jeśli P = NP, czy moglibyśmy uzyskać dowody hipotezy Goldbacha itp.?
To naiwne pytanie z mojej wiedzy; z góry przeprasza. Hipoteza Goldbacha i wiele innych nierozwiązanych pytań w matematyce można zapisać jako krótkie formuły w rachunku predykatów. Na przykład artykuł Cooka „Czy komputery mogą rutynowo odkrywać dowody matematyczne?” formułuje tę hipotezę jako ∀ n [ ( n > 2 ∧ 2 …
1
Czy istnieje rozsądny zautomatyzowany system dowodowy dla twierdzeń TCS?
Załóżmy, że chciałem sformalizować dowód Turinga dotyczący problemu zatrzymania, aby maszyna mogła to sprawdzić. Niektóre ze znanych automatycznych systemów dowodzenia twierdzeń obejmują Mizar, Coq i HOL4. Pobrałem i eksperymentowałem z Coq, ale nie ma biblioteki dla maszyn Turinga. Sam pomyślałem o kodowaniu jednego, ale brakowało tego samouczka, a język był …
2
Dlaczego komputerowi tak trudno jest coś udowodnić?
To może być uznane za głupie pytanie. Nie jestem informatyką (i jeszcze nie jestem matematyką), więc przepraszam, jeśli uważasz, że poniższe pytania zawierają pewne błędne założenia. Chociaż istnieją plany sformalizowania ostatniego twierdzenia Fermata (patrz ta prezentacja ), nigdy nie czytałem ani nie słyszałem, że komputer może udowodnić nawet „proste” twierdzenie …
1
Jak ustalić, czy dowód wymaga „technik wnioskowania wyższego rzędu”?
Pytanie: Załóżmy, że mam specyfikację problemu składającego się z aksjomatów i celu (tj. Powiązanym problemem dowodowym jest to, czy cel jest zadowalający, biorąc pod uwagę wszystkie aksjomaty). Załóżmy również, że problem nie zawiera żadnych niespójności / sprzeczności między aksjomatami. Czy istnieje sposób na wcześniejsze ustalenie (tj. Bez uprzedniego zbudowania pełnego …
1
Logiczne reakcje na system impredykatywny w predykatywnej metateorii
Relacje logiczne dla języków impredykatywnych, takich jak System F, wydają się krytycznie opierać na impredykatywności logiki otoczenia. W szczególności interpretacja typu forall zostanie zdefiniowana w kategoriach wszystkich relacji typowanych. W systemie impredykatywnym (jak CiC / Coq) jest w porządku, ale wydaje się to niemożliwe w systemie predykcyjnym (jak Agda). Jak …
6
Jakie są praktycznie obliczalne właściwości znakowanych układów przejściowych?
Znalazłem systemy przejściowe oznaczone jako dobry model dla mojej aplikacji, a mianowicie jest artykuł na temat modelowania przypadków użycia przy użyciu LTS. Pytanie brzmi: co można łatwo udowodnić w LTS? Chciałbym ponownie wykorzystać istniejące rozwiązania, aby sprawdzić, czy są one przydatne w mojej aplikacji. Chciałbym wiedzieć, jakie właściwości LTS (i …
2
Najnowocześniejszy w klasie Monadic?
Monadyczna logika pierwszego rzędu, znana również jako monadyczna klasa problemu decyzyjnego, jest miejscem, w którym wszystkie predykaty biorą jeden argument. Został rozstrzygnięty przez Ackermanna i jest NEXPTIME-complete . Jednak problemy takie jak SAT i SMT mają szybkie algorytmy do ich rozwiązania, pomimo teoretycznych ograniczeń. Zastanawiam się, czy istnieją badania analogiczne …
2
Jaki paradygmat automatycznego dowodzenia twierdzeń jest odpowiedni dla formalizacji w stylu Principia Mathematica?
Posiadam książkę, która zainspirowana Principia Mathematica (PM) Russella i logicznym pozytywizmem próbuje sformalizować konkretną dziedzinę, określając aksjomaty i wydając z nich twierdzenia. Krótko mówiąc, próbuje zrobić dla swojej dziedziny to, co PM próbował zrobić dla matematyki. Podobnie jak PM, został napisany, zanim możliwe było automatyczne udowodnienie twierdzenia (ATP). Próbuję przedstawić …
3
Dowody znalezione przez komputer
W 1996 r. Długotrwały otwarty problem został rozwiązany przez komputer; mianowicie, że algebra Robbinsa i algebra Boole'a są takie same. Dowód został znaleziony przez automatyczną powiedzonkę twierdzeń. Ponadto znany dowód twierdzenia o czterech kolorach zawiera generowane komputerowo komponenty. Celem tego pytania jest wykazanie dowodów, które zostały (całkowicie lub częściowo) znalezione …
1
Dlaczego Proof Checker jest wymagany w Proof Carry Code?
W klasycznym dokumencie PLDI'98 autorstwa Neculi „Projekt i implementacja kompilatora certyfikującego” weryfikator wysokiego poziomu wykorzystuje: VCGen generuje warunki weryfikacji (prognozy bezpieczeństwa) Dowódca logiki twierdzenia pierwszego rzędu, aby udowodnić warunki Kontroler sprawdzania LF, aby sprawdzić dowód od kroku (2) Jestem trochę zdezorientowany krokiem (3). Dlaczego w ogóle jest to wymagane? Czy …
1
Zgodność pierwszego rzędu bez modeli skończonych
Wiemy z twierdzenia Kościoła, że ​​określenie satysfakcji pierwszego rzędu jest ogólnie nierozstrzygalne, ale istnieje kilka technik, które można zastosować do ustalenia satysfakcji pierwszego rzędu. Najbardziej oczywiste jest poszukiwanie modelu skończonego. Istnieje jednak szereg instrukcji w logice pierwszego rzędu, które możemy wykazać, że nie mają modeli skończonych. Na przykład każda dziedzina, …
1
Czy teoria typów Martina-Löfa przyczyni się do większej zdolności do pisania poprawnego kodu, który da się udowodnić
Ten post odnosi się do izomorfizmu Curry'ego-Howarda i teorii typów Martina-Löfa . W postie stwierdza się o przyszłym „zjednoczeniu” języka opisu matematyki z językiem programowania komputerowego opartym na operacjach. Moje pytania to: Czy te pomysły doprowadzą do lepszej zdolności (poprzez języki) do pisania możliwego do udowodnienia poprawnego kodu? Czy pełne …
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.