Pytania otagowane jako lo.logic

Logika obliczeniowa i matematyczna.

1
Naturalne twierdzenia udowodnione tylko „z dużym prawdopodobieństwem”?
Istnieje wiele sytuacji, w których zrandomizowany „dowód” jest znacznie łatwiejszy niż dowód deterministyczny, którego kanonicznym przykładem jest testowanie tożsamości wielomianowej. Pytanie : Czy istnieją jakieś naturalne „twierdzenia” matematyczne, w których znany jest dowód losowy, ale dowód deterministyczny nie? Przez „losowy dowód” stwierdzenia rozumiem toPPP Istnieje algorytm randomizowany, który przyjmuje dane …
1
Czy MALL + nieograniczone typy rekurencyjne Turing jest kompletne?
Jeśli spojrzysz na rekurencyjne kombinatory w nierozpisanym rachunku lambda, takie jak kombinator Y lub kombinator omega: ωY==(λx.xx)(λx.xx)λf.(λx.f(xx))(λx.f(xx))ω=(λx.xx)(λx.xx)Y=λf.(λx.f(xx))(λx.f(xx)) \begin{array}{lcl} \omega & = & (\lambda x.\,x\;x)\;(\lambda x.\,x\;x)\\ Y & = & \lambda f.\,(\lambda x.\,f\;(x\;x))\; (\lambda x.\,f\;(x\;x)) \\ \end{array} Oczywiste jest, że wszystkie te kombinatory kończą kopiowanie gdzieś w swojej definicji. Co więcej, …
2
Czy rozstrzyganie propozycji jest kompletnym systemem dowodowym?
To pytanie dotyczy logiki zdań i wszystkie wystąpienia „rozstrzygania” należy interpretować jako „rozstrzyganie zdań”. To pytanie jest bardzo proste, ale od dłuższego czasu mnie niepokoi. Widzę, że ludzie twierdzą, że rozwiązanie zdań jest kompletne, ale widzę też, że ludzie twierdzą, że rozwiązanie jest niepełne. Rozumiem sens niepełnej rozdzielczości. Rozumiem również, …
1
Jak pokazać, że typ w systemie z typami zależnymi nie jest zamieszkały (tj. Formuła nie do udowodnienia)?
W przypadku systemów bez typów zależnych, takich jak system typu Hindley-Milner, typy odpowiadają formułom logiki intuicyjnej. Nie wiemy, że modele algebrami Heytinga, a w szczególności do zbicia wzór, można ograniczyć do jednego Heytinga Algebra gdzie każdy wzór jest reprezentowany przez otwarte podzestawu .RR\mathbb{R} Na przykład, jeśli chcemy pokazać, że nie …
1
Co możemy udowodnić za pomocą nieskończonych wykresów, że bez nich nie możemy udowodnić?
Jest to kontynuacja pytanie na ten temat nieskończonych wykresach. Odpowiedzi i komentarze do tego pytania zawierają listę obiektów i sytuacji, które są naturalnie modelowane przez nieskończone wykresy. Ale istnieją również liczne twierdzenia o grafach nieskończonych (patrz rozdział 8 w książce Diestela), z których na przykład bardzo popularny jest nieskończony lemat …
4
Jedność parametryczna a parametryczność binarna
Ostatnio zainteresowałem się parametrownością po obejrzeniu artykułu LICS Bernardy'ego i Moulina z 2012 r. ( Https://dl.acm.org/citation.cfm?id=2359499 ). W tym artykule internalizują one jednoargumentową parametryczność w systemie czystego typu z typami zależnymi i podpowiadają, w jaki sposób można rozszerzyć konstrukcję na dowolne arie. Wcześniej widziałem tylko parametr binarny. Moje pytanie brzmi: …
1
Utrzymanie porządku na liście w w Czas
Problem z utrzymaniem porządku (lub „utrzymaniem porządku na liście”) polega na obsłudze operacji: singleton: tworzy listę z jednym elementem, zwraca do niej wskaźnik insertAfter: dany wskaźnik do elementu wstawia nowy element po nim, zwracając wskaźnik do nowego elementu delete: dany wskaźnik do elementu usuwa go z listy minPointer: biorąc pod …
2
Teoria dowodowa produktów dwubiegowych?
Kategoria ma dwuprodukty, gdy te same obiekty są zarówno produktami, jak i koproduktami. Czy ktoś badał teorię kategorii produktów dwubiegunowych? Być może najbardziej znanym przykładem jest kategoria przestrzeni wektorowych, w których bezpośrednia suma i bezpośrednie konstrukcje produktu dają tę samą przestrzeń wektorową. Oznacza to, że przestrzenie wektorowe i mapy liniowe …
1
Szukasz artykułów i artykułów na temat Tarskian Möglichkeit
Pewne tło: logika wielowartościowa Łukasiewicza miała być logiką modalną, a Łukasiewicz podał ekstensywną definicję operatora modalnego: ◊ A =ree f¬ A → A◊ZA=remifa¬ZA→ZA\Diamond A =_{def} \neg A \to A (który przypisuje Tarskiemu). Daje to dziwną logikę modalną, z pewnymi paradoksalnymi, jeśli nie pozornie absurdalnymi twierdzeniami, w szczególności . Zastępca ¬ …
1
Stałe twierdzenia punktowe dla konstruktywnych przestrzeni metrycznych?
Twierdzenie Banacha o punkcie stałym mówi, że jeśli mamy niepustą pełną przestrzeń metryczną AZAA , wówczas każda jednorodnie kurcząca się funkcja ma unikalny punkt stały . Jednak dowód tego twierdzenia wymaga aksjomatu wyboru - musimy wybrać dowolny element aby rozpocząć iterację , aby uzyskać sekwencję Cauchyego . μ ( f …
3
Teorie charakteryzujące klasy złożoności obliczeniowej
Czytając artykuł „ Teoria aplikacyjna dla FPH ”, można natknąć się na następujący fragment: Biorąc pod uwagę teorie charakteryzujące klasy złożoności obliczeniowej, istnieją trzy różne podejścia: w jednym funkcje, które można zdefiniować w teorii, są „automatycznie” w ramach pewnej klasy złożoności. Na takim koncie należy ograniczyć składnię, aby zagwarantować, że …
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.