szczególny rodzaj techniki opartej na matematyce do specyfikacji, rozwoju i weryfikacji systemów oprogramowania i sprzętu.
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ą...
To pytanie zostało przeniesione z Teoretycznej informatyki stosu wymiany, ponieważ można na nie odpowiedzieć w sprawie informatyki stosu wymiany. Migrował 7 lat temu . „Alan Turing udowodnił w 1936 r., Że nie może istnieć ogólny algorytm rozwiązania problemu zatrzymania...
Często zdarza się, że studenci rozpoczynają doktoraty z ograniczonym doświadczeniem w matematyce i formalnych aspektach informatyki. Oczywiście takim studentom bardzo trudno będzie zostać teoretycznym informatykiem, ale dobrze by było, gdyby mogli się zorientować w stosowaniu metod formalnych i...
Biorąc pod uwagę oznaczony system przejścia , gdzie jest zbiorem stanów, jest zbiorem etykiet, a jest relacją trójskładnikową. Jak zwykle napisz dla . Oznaczone przejście oznacza, że system w stanie zmienia stan na z etykietą , co oznacza, że to pewne obserwowalne działanie, które powoduje zmianę...
Problemu zatrzymania nie można rozwiązać w ogólnym przypadku. Można wymyślić zdefiniowane reguły, które ograniczają dozwolone dane wejściowe i czy problem zatrzymania można rozwiązać w tym szczególnym przypadku? Na przykład wydaje się prawdopodobne, że język, który nie dopuszcza na przykład pętli,...
Jak sprawdzisz, czy dwa algorytmy (powiedzmy: Sortuj i Naiwne) zwracają ten sam wynik dla dowolnego wejścia, gdy zestaw wszystkich danych wejściowych jest nieskończony? Aktualizacja: Dziękuję Ben za opisanie, w jaki sposób niemożliwe jest algorytmiczne wykonanie tego przypadku w ogólnym przypadku....
W artykule „Bezkonfliktowy zreplikowany typ danych JSON” napotkałem ten zapis do formalnego definiowania „reguł”: Jak nazywa się ten zapis? Jak to czytać? Na przykład: DOCreguła nie ma nic w „liczniku” - dlaczego nie? te EXECi GETzasady wydają się mieć dwa oddzielne terminy powyżej linii, co...
Z Wikipedii: W informatyce teoretycznej poprawność algorytmu jest stwierdzana, gdy mówi się, że algorytm jest poprawny w odniesieniu do specyfikacji. Problem polega jednak na tym, że uzyskanie „właściwej” specyfikacji nie jest trywialnym zadaniem i nie ma 100% poprawnej metody (o ile wiem), aby...
OK, oto pytanie z poprzedniego testu w mojej klasie teorii obliczeń: Stan bezużyteczny w bazie TM to taki, który nigdy nie jest wprowadzany w żadnym ciągu wejściowym. Niech Udowodnij, że U S E L E S S T M jest nierozstrzygalny.U S E L E S ST M= { ⟨ M, q⟩ ∣ q jest bezużytecznym stanem w M}...
Próbuję nauczyć się różnych podejść do weryfikacji oprogramowania. Przeczytałem kilka artykułów. O ile się dowiedziałem, logika zdaniowa z temporalnym na ogół wykorzystuje sprawdzanie modelu za pomocą solverów SAT (w systemach trwających - reaktywnych), ale co z logiką pierwszego rzędu z...
Zwykle widzę, że w strukturalnej reprezentacji operacyjnej semantyki dla pętli while stan programu nie zmienia się: (whileBdoS,σ)→(ifBthenS;(whileBdoS)elseSKIP,σ)(whileBdoS,σ)→(ifBthenS;(whileBdoS)elseSKIP,σ)(while \> B \> do \>S, \sigma) \rightarrow (if \>B \> then \>S; (while \> B \> do \>S) \>...