Pytania otagowane jako lo.logic

Logika obliczeniowa i matematyczna.

1
Zrozumienie dowodu silnej normalizacji rachunku konstrukcji
Mam trudności ze zrozumieniem dowodu silnej normalizacji dla rachunku konstrukcji. Staram się podążać za dowodem zawartym w pracy Hermana Geuversa „Krótki i elastyczny dowód silnej normalizacji dla rachunku konstrukcji”. Potrafię dobrze podążać za główną linią rozumowania. Konstrukcje Geuvers dla każdego typuTTT interpretacja [[T]]ξ[[T]]ξ[\![T]\!]_\xi na podstawie pewnej oceny zmiennych typu ξ(α)ξ(α)\xi(\alpha). …
1
Sprzeczność między drugim twierdzeniem Gödela o niekompletności a własnością Church-Rosser CIC?
Z jednej strony drugie twierdzenie Gödela o niekompletności stwierdza, że ​​żadna spójna teoria formalna, która jest wystarczająco silna, aby wyrazić dowolne podstawowe stwierdzenia arytmetyczne, nie może udowodnić swojej spójności. Z drugiej strony właściwość Churcha-Rossera systemu formalnego (przepisywania) mówi nam, że jest on spójny w tym sensie, że nie wszystkie równania …
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, …
3
Czy klasa prymitywnych funkcjonałów rekurencyjnych jest równoważna z klasą funkcji, które płód kończy?
Płód, jeśli o nim nie słyszałeś, możesz przeczytać tutaj . Wykorzystuje system „macierzy wywołań” i „grafów wywołań”, aby znaleźć wszystkie „zachowania rekurencyjne” wywołań rekurencyjnych w funkcji. Pokazanie, że funkcja się kończy, pokazuje, że wszystkie zachowania rekurencyjne wywołań rekurencyjnych wykonanych do funkcji są zgodne z pewnym „porządkiem leksykograficznym”. Jego sprawdzanie zakończenia …
1
Hyperdoktryny i monadyczna logika drugiego rzędu
To pytanie jest zasadniczo pytaniem, które zadałem na Mathoverflow. Monadyczna logika drugiego rzędu (MSO) to logika drugiego rzędu z kwantyfikacją w stosunku do pojedynczych predykatów. Oznacza to kwantyfikację zbiorów. Istnieje kilka logiki MSO, które są fundamentalne dla struktur badanych w informatyce. Pytanie 1. Czy istnieje kategoryczna semantyka dla logiki Monadic …
3
Złożoność SMT z jedną alternatywą
Szukam złożoności spełniania formuły ∀y1,…,yn,∃x1,…,xm,ϕ∀y1,…,yn,∃x1,…,xm,ϕ\forall y_1, \dots,y_n, \exists x_1,\dots,x_m, \phi lub o wzorze ∃x1,…,xm∀y1,…,yn,ϕ∃x1,…,xm∀y1,…,yn,ϕ \exists x_1,\dots,x_m \forall y_1, \dots,y_n,\phi gdzie ϕϕ\phi jest formuła formularza: ϕ:=ϕ∧ϕ | ¬ϕ | ϕ→ϕ | ψϕ:=ϕ∧ϕ | ¬ϕ | ϕ→ϕ | ψ\phi:= \phi \wedge\phi ~| ~\neg \phi ~| ~ \phi\to \phi~| ~\psi ψ:=t>t | t=tψ:=t>t …
2
Jaka jest korzyść z zapisu Krivine?
Widziałem, jak niektórzy ludzie używają notacji Krivine'a do aplikacji funkcji podczas prezentacji składni dla -calculus. Na przykład -term (z normalną konwencją, że aplikacja funkcji kojarzy się z lewą stroną, więc w rzeczywistości oznacza to ) jest napisane (z podobną konwencją, że w rzeczywistości oznacza ). Nie widzę sensu posiadania kolejnej …
2
Jak możemy wyrazić „
Zamknięte. To pytanie jest nie na temat . Obecnie nie przyjmuje odpowiedzi. Chcesz poprawić to pytanie? Zaktualizuj pytanie, aby było tematem wymiany stosów teoretycznych w informatyce. Zamknięte 7 lat temu . Jak możemy wyrazić „ ” jako formułę pierwszego rzędu?P.= PS.P.A C.miP=PSPACEP=PSPACE Który poziom hierarchii arytmetycznej zawiera tę formułę (i …
1
CTL * i rachunek różniczkowy
dobrze wiadomo, że modal -calculusμμ\mu jest jedną z najbardziej ekspresyjnych logik czasowych do wyrażania właściwości drzew / grafów, i że CTL * jest ściśle mniej ekspresyjny niż -calculus.μμ\mu W tym miejscu chciałbym poprosić o przykład formuły calculus, tak prostej, jak to możliwe, która nie jest wyrażalna w CTL *, i …
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 …
1
Prosty dowód, że rozstrzygalność typowalności w systemie F ( ) implikuje rozstrzygalność sprawdzania typu?
Załóżmy, że nie znamy wyniku Joe B. Wellsa z 1994 roku, że zarówno typowość, jak i sprawdzanie typów są nierozstrzygalne w Systemie F (AKA ). W rachunku Lambda z typami Barendregta (1992) znalazłem dowód z powodu Maleckiego 1989, że sprawdzanie typów implikuje typowość. To dlatego, żeλ 2λ2)\lambda 2 istnieje taki, …
2
Intuicja za systemami dowodowymi
Próbuję zrozumieć artykuł na temat p-Optimal Proof Systems and Logic for PTIME . W artykule jest pojęcie nazywane systemami dowodowymi i nie rozumiem intencji: Σ = { 0 , 1 }Σ={0,1}\Sigma = \{0,1\} ... Identyfikujemy problemy z podzbiorami w .QQQΣ∗Σ∗\Sigma^* Myślę, że intencją jest to, że kodujemy pewną strukturę w …
2
Proste zamykania dla typów indukcyjnych ze spacjami funkcyjnymi
Funkcje zbudowane z produktów i sum skończonych mają porządek zamknięcia ωω\omega, ładnie wyszczególnione w tym manuskrypcie Francoisa Metayera. tzn. możemy osiągnąć typ indukcyjnynat:=μX.1+Xnat:=μX.1+Xnat := \mu X. 1 + X przez iterację funktora 1+X1+X1 + X, który osiąga swój stały punkt po ωω\omega iteracje. Ale kiedy pozwolimy na stałe potęgowanie, takie …
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.