Informatyka

Pytania i odpowiedzi dla studentów, naukowców i praktyków informatyki

3
Dlaczego problem zatrzymania jest rozstrzygalny dla LBA?
Czytałem w Wikipedii i innych tekstach, które Problem zatrzymania jest [...] rozstrzygalny dla automatów z ograniczeniami liniowymi (LBA) [i] deterministycznych maszyn ze skończoną pamięcią. Ale wcześniej napisano, że problem zatrzymania jest problemem nierozstrzygalnym, a zatem TM nie może go rozwiązać! Ponieważ LBA są zdefiniowane jako rodzaj bazy TM, czy to …
1
Środowisko wykonawcze ogranicza się do algorytmów NP całkowitych problemów przy założeniu P ≠ NP
Załóżmy, że .P≠NPP≠NPP\neq NP Co możemy powiedzieć o granicach czasu działania wszystkich problemów związanych z NP-zupełnością? tj. jakie są najostrzejsze funkcje dla których możemy zagwarantować, że optymalny algorytm dla dowolnego problemu z NP zakończony będzie w czasie co najmniej i co najwyżej na wejściu o długości ? ω ( L …
3
Quine w rachunku różnym lambda
Chciałbym przykład quine w czystym rachunku lambda . Byłem dość zaskoczony, że nie znalazłem go przez google. Strona quine zawiera listę quinów dla wielu „prawdziwych” języków, ale nie dla rachunku lambda. Oczywiście oznacza to zdefiniowanie, co mam na myśli przez quine w rachunku lambda, co robię poniżej. (Proszę o coś …
4
Twierdzenia mostkowe dla teorii grup i języków formalnych
Czy istnieje jakiś naturalny lub znaczący sposób na powiązanie lub połączenie grup matematycznych i języków formalnych CS lub jakieś inne podstawowe pojęcie CS, np. Maszyny Turinga? Szukam referencji / aplikacji. Zauważ jednak, że jestem świadomy związku między półgrupami a językami CS (mianowicie za pośrednictwem automatów skończonych ). (Czy ta literatura …
1
Znalezienie maksymalnej faktoryzacji zwykłych języków
Niech język będzie regularny.L⊆Σ∗L⊆Σ∗\mathcal{L} \subseteq \Sigma^* Rozkład na czynniki to maksymalna para zestawów słów z ( X , Y )LL\mathcal{L}(X,Y)(X,Y)(X,Y) X⋅Y⊆LX⋅Y⊆LX \cdot Y \subseteq \mathcal{L} X≠∅≠YX≠∅≠YX \neq \emptyset \neq Y , gdzie | .x ∈ X , y ∈ Y }X⋅Y={xyX⋅Y={xyX \cdot Y = \{xyx∈X,y∈Y}x∈X,y∈Y}x \in X, y \in Y\} …
5
Czym różni się brak jednoznaczności od determinizmu?
Próbuję zrozumieć, co należy rozumieć przez „deterministyczny” w wyrażeniach takich jak „deterministyczna gramatyka bezkontekstowa”. (W tej dziedzinie są bardziej deterministyczne „rzeczy”). Byłbym wdzięczny za przykład bardziej niż najbardziej wyszukane wyjaśnienie! Jeśli to możliwe. Moje główne źródło zamieszania polega na tym, że nie jestem w stanie powiedzieć, w jaki sposób ta …
3
Kto potrzebuje linearyzowalności?
Czytałem o różnicach między serializacją a linearyzacją , które są kryteriami spójności dla replikowanych systemów, takich jak replikowane bazy danych. Nie wiem jednak, w jakich przypadkach konieczna byłaby linearyzowalność, nawet jeśli jest silniejsza niż serializowalność. Czy mógłbyś wymyślić scenariusze, w których tak silna własność byłaby rzeczywiście konieczna?
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.