Wiadomo, że język słów o równej liczbie 0 i 1 nie jest regularny, podczas gdy język słów o równej liczbie 001 i 100 jest regularny ( patrz tutaj ). Biorąc pod uwagę dwa słowa , czy jest rozstrzygalne, czy język słów zawierający taką samą liczbę i jest regularny?w 1 w...
Wiele „znanych” nierozstrzygalnych problemów jest jednak co najmniej w połowie nierozstrzygalnych, a ich dopełnienie jest nierozstrzygalne. Jednym z przykładów może być przede wszystkim problem zatrzymania i jego uzupełnienie. Czy ktoś może jednak podać przykład, w którym zarówno problem, jak i...
Zastanawiam się, czy decydowanie o rozstrzygalności problemu jest problemem rozstrzygalnym. Chyba nie, ale po wstępnych poszukiwaniach nie mogę znaleźć literatury na ten
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...
Czy istnieją nierozstrzygalne języki, tak że ich związek / język przecięcia / konkatenacji jest rozstrzygalny? Jaka jest fizyczna interpretacja takiego przykładu, ponieważ ogólnie nierozstrzygalne języki nie są zamknięte w ramach tych operacji? Co możemy powiedzieć o zamknięciu kleene? Czy mamy...
Przeglądałem definicję języka kontekstowego w Wikipedii i znalazłem to: Każda kategoria języków jest odpowiednim podzbiorem kategorii bezpośrednio nad nią. Każdy automat i gramatyka w każdej kategorii ma równoważny automat lub gramatykę w kategorii bezpośrednio nad nią. Widziałem, że automat...
Czytałem odpowiedź na ostatnie pytanie i przyszło mi do głowy coś dziwnego, efemerycznego. Moje pytanie może zdradzić, że moim teoretycznym kotletom poważnie brakuje (głównie prawdy) lub że jest zbyt wcześnie, aby przeczytać tę stronę. Teraz, gdy wyłączenie odpowiedzialności jest na drodze...
W pracy miałem za zadanie wnioskować o pewnych typach informacji o dynamicznym języku. Przepisuję sekwencje instrukcji na letwyrażenia zagnieżdżone , tak jak poniżej: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then { T;...
Czy istnienie nierozwiązywalnych problemów natychmiast implikuje nieprzewidywalność układów fizycznych? Rozważmy problem zatrzymania, najpierw konstruujemy fizyczny UTM, powiedzmy, używając zwykłej konstrukcji opartej na obwodach. Wtedy nie może istnieć rozstrzygalna teoria fizyczna, która mogłaby...
Jedna z definicji zestawu wyliczalnego (ce, równoważnego rekurencyjnie wyliczalnemu, równoważnego semidecidable) jest następująca: A⊆Σ∗A⊆Σ∗A \subseteq \Sigma^* oznacza, że istnieje rozstrzygalny językV⊆Σ∗V⊆Σ∗V\subseteq \Sigma^* (zwany weryfikatorem) st dla wszystkichx∈Σ∗x∈Σ∗x\in \Sigma^* ,...
Rozumiem, że większość problemów jest trywialna, jeśli dostępna jest wyrocznia zatrzymująca (lub, moim zdaniem, hiper-obliczenia). Jednak zastosowanie argumentu, który pokazuje, że problem zatrzymania jest niemożliwy dla maszyny Turinga, pokazuje również, że wyrocznia Turinga + nie może zdecydować...
Przykro mi, jeśli na to pytanie ma jakąś trywialną odpowiedź, której mi brakuje. Ilekroć badam jakiś problem, który okazał się nierozstrzygalny, zauważam, że dowód polega na zmniejszeniu do innego problemu, który okazał się nierozstrzygalny. Rozumiem, że tworzy to pewien porządek na poziomie...
Niech Czy istnieje maszyna Turinga R, która decyduje (nie mam na myśli rozpoznać) język L ∅ ?L∅={⟨M⟩ ∣ M. jest maszyną Turinga i L ( M) = ∅ } .L∅={⟨M⟩∣M is a Turing Machine and L(M)=∅}.L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and...
Czy istnieje algorytm dla następującego problemu: Biorąc pod uwagę maszynę Turinga która decyduje o języku L , czy istnieje maszyna Turinga M 2 decydująca L, tak że t 2 ( n ) = o ( t 1 ( n ) ) ?M.1M1M_1L.LLM.2)M2M_2L.LLt2)( n ) = o ( t1( n ) )t2(n)=o(t1(n))t_2(n) = o(t_1(n)) Funkcje i t 2...
Natknąłem się na następujący interesujący problem: niech będą wielomianami na polu liczb rzeczywistych i załóżmy, że wszystkie ich współczynniki są liczbami całkowitymi (tzn. Istnieje dokładna reprezentacja tych wielomianów). W razie potrzeby możemy założyć, że stopień obu wielomianów jest równy....
W przypadku problemu zatrzymania jesteśmy zainteresowani, czy istnieje maszyna Turinga T.TT która może stwierdzić, czy dana maszyna Turinga M.MM zatrzymuje się, czy nie na danym wejściu . Zwykle dowód zaczyna zakładać, że taki istnieje. Następnie rozważamy przypadek, w którym ograniczamy do samego...
Czy istnieje potrzeba, aby L⊆Σ∗L⊆Σ∗L\subseteq \Sigma^* była nieskończona, aby była nierozstrzygalna? Chodzi mi o to, że jeśli wybierzemy język L′L′L' jako ograniczoną skończoną wersję L⊆Σ∗L⊆Σ∗L\subseteq \Sigma^* , to znaczy |L′|≤N|L′|≤N|L'|\leq N ( N∈NN∈NN \in \mathbb{N} ), a L′⊂LL′⊂LL' \subset L...
Czy zaakceptowanie oznacza, że TM odczyta i rozpozna znak z komórki, z której obecnie czyta? I czy tak się dzieje, że TM zatrzymuje się, jeśli dane wejściowe są
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}...
Jedno stwierdzenie twierdzenia Rice'a znajduje się na stronie 35 „Złożoności obliczeniowej: nowoczesne podejście” (Arora-Barak): Funkcja częściowa od do to funkcja, która niekoniecznie jest zdefiniowana na wszystkich jej wejściach. Mówimy, że TM oblicza funkcję cząstkową jeżeli dla każdego na...