Przygotowuję się do wykładu skierowanego do studentów kierunków matematycznych, w ramach których rozważam omówienie koncepcji rozstrzygalności. Chcę podać przykład problemu, o którym obecnie nie wiemy, że jest rozstrzygalny lub nierozstrzygalny. Istnieje wiele takich problemów, ale jak dotąd żaden...
Jeśli ograniczy się maszyny Turinga do skończonej taśmy (tj. Do zastosowania ograniczonej przestrzeni ), wówczas problem zatrzymania jest rozstrzygalny, zasadniczo dlatego, że po kilku etapach (które można obliczyć na podstawie liczby stanów i oraz rozmiar alfabetu), konfigurację należy...
Wiem, że nierozstrzygalne jest ustalenie, czy zestaw kafelków może kafelkować płaszczyznę, w wyniku Bergera korzystającego z kafelków Wanga . Moje pytanie brzmi: czy wiadomo również, że nierozstrzygalne jest ustalenie, czy pojedyncza dana płytka może ułożyć płytkę, monoedryczną płytkę. Jeśli to...
Dobrze wiadomo, że problem równoważności jest nierozstrzygalny dla ogólnych języków bezkontekstowych. Jednak wszystkie dowody tego faktu, o których jestem świadomy, wydają się obejmować pewne niejednoznaczne gramatyki bezkontekstowe. Z tego powodu chciałbym zapytać, czy wiadomo, czy problem...
Jestem zainteresowany następującym problemem: podano całkowitą macierze 1 , 2 , ... , k zdecydować, czy każdy nieskończony iloczyn tych macierzy ostatecznie równa macierzy zerowej.ZA1, A2), … , AkA1,A2,…,AkA_1,A_2, \ldots, A_k Oznacza to dokładnie to, co myślisz: powiemy, że zestaw macierzy { A1,...
To dobrze znany wynik, że pytanie Czy gramatyka bezkontekstowa generuje zwykły język? jest nierozstrzygalny. Jednak staje się to rozstrzygalne na podstawie jednoznacznego alfabetu, po prostu dlatego, że w tym przypadku klasy języków bezkontekstowych i zwykłych pokrywają się. Moje pytanie...
Wiem, że nie można zdecydować równoważności dla niepoprawnego rachunku lambda. Cytując Barendregt, HP Rachunek lambda: jego składnia i semantyka. Północna Holandia, Amsterdam (1984). :ββ\beta Jeśli A i B są rozłączne, niepuste zbiory terminów lambda, które są zamknięte na zasadzie równości, to A...
Próbuję rozwiązać konkretny problem i pomyślałem, że mogę go rozwiązać za pomocą teorii automatów. Zastanawiam się, jakie modele automatów mają rozstrzygające rozstrzyganie w czasie wielomianowym? tzn. jeśli masz maszyny M.1, M2)M.1,M.2)M_1, M_2 , możesz sprawdzić, czy wydajnie.L ( M1) ⊆ L (...
Problemem zatrzymania maszyn Turinga jest być może kanoniczny nierozstrzygalny zestaw. Niemniej jednak dowodzimy, że istnieje algorytm decydujący o prawie wszystkich jego wystąpieniach. Problem zatrzymania należy zatem do rosnącej liczby osób wykazujących zjawisko teorii złożoności „czarnej...
Odpowiedź: nieznana. Zadawane pytania są naturalne, otwarte i pozornie trudne; pytanie jest teraz wiki społeczności. Przegląd Pytanie ma na celu podzielenie języków należących do klasy złożoności - wraz z maszynami decyzyjnymi Turinga (TM), które akceptują te języki - na dwie uzupełniające się...
Wiadomo, że wiele problemów logicznych (np. Problemy satysfakcji kilku logik modalnych) nie są rozstrzygalne. Istnieje również wiele nierozstrzygalnych problemów w teorii algorytmów, np. W optymalizacji kombinatorycznej. Ale w praktyce heurystyki i algorytmy przybliżone działają dobrze w przypadku...
Jakie są znane granice rozstrzygalności porównania szybkości wzrostu funkcji z ? Mam na myśli rozstrzygalność pytań takich jak „Czy x x ∼ 2 ⌊ x lg ( x + 2 ) ⌋ ?” lub „Czy 2 lg ∗ x ∈ O ( lg lg x ) ?”.N→NN→N\mathbb{N} \to \mathbb{N}xx∼2⌊xlg(x+2)⌋xx∼2⌊xlg(x+2)⌋x^x \sim 2^{\lfloor x \lg (x+2)...
Jaki jest najprostszy model obliczeniowy, dla którego problem pustki jest nierozstrzygalny? Problem pustki dla modelu obliczeniowego (np. Automat skończony, automat przemienny, automat kwantowy z ograniczeniem błędu z licznikiem, deterministyczny LBA itp.) Polega na ustaleniu, czy dla danej takiej...
System dodawania wektorów (VAS) to skończony zestaw działań . jest zbiorem oznaczeń . Trasa jest niepusty słowo oznaczenia st . Jeśli takie słowo istnieje, mówimy, że jest osiągalne z .A⊂ZdA⊂ZdA \subset \mathbb{Z}^dm 0 m 1 … m n ∀ i ∈ { 0 , … , n - 1 } , m i + 1 - m i ∈ A m n m...
Odpowiedź: nieznana Ogromne podziękowania dla wszystkich, którzy pomogli dopracować to pytanie i związane z nim definicje. Definicje tej wiki stanowiły punkt wyjścia dla najnowszej wiki TCS „ Czy P zawiera języki, których istnienie jest niezależne od PA lub ZFC? (Wiki społeczności TCS) ”....
„Nazwa największej gry liczbowej” wymaga od dwóch graczy potajemnego zapisania numeru, a zwycięzcą jest osoba, która zapisała większą liczbę. Gra zazwyczaj pozwala graczom zapisywać funkcje ocenione w danym momencie, więc byłoby również do przyjęcia.2)2)2)2)2)2)2)2)2^{2^{2^{2}}} Wartości funkcji...
Rozważ dowolną bezkontekstową gramatykę nad alfabetem . Do produkcji tej gramatyki dodaj dwie stałe produkcje bezkontekstowe : i \ overline {1} 1 \ rightarrow \ epsilon . Nazwij wynikową gramatykę G ^ P oznaczającą „ G uzupełniony o produkcje P ”.solGG{ 0 , 1 ,0¯¯¯,1¯¯¯}{0,1,0¯,1¯}\lbrace...
Istnieją problemy, które można rozstrzygnąć, niektóre są nierozstrzygalne, istnieje możliwość rozstrzygnięcia itp. W tym przypadku zastanawiam się, czy problem może być nierozstrzygalny. Oznacza to (przynajmniej w mojej głowie), że nie możemy stwierdzić, czy jest to rozstrzygalne, czy nie. Być...
Czy każdy rozpoznawalny przez Turinga niezdecydowany język ma podzbiór NP? Pytanie to może być postrzegane jako silniejsza wersja faktu, że każdy nieskończony rozpoznawalny język Turinga ma nieskończony decydujący
Jeśli masz dwie funkcje implementujące inny algorytm sortowania, to czy można na podstawie kodu źródłowego wnioskować, że obie mają takie same właściwości zewnętrzne? Czy to znaczy, że oboje będą mieć możliwą nieposortowaną sekwencję jako dane wejściowe i posortowaną sekwencję jako dane wyjściowe?...