Pytania otagowane jako decidability

15
Prosty problem, którego rozstrzygalność nie jest znana
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 z nich nie wyróżnia się na tle innych. Co to jest prosty …
3
Ograniczenia maszyny Turinga, które sprawiają, że zatrzymanie jest rozstrzygalne
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 powtórzyć.SSSQQQSSS Czy istnieją inne naturalne ograniczenia dotyczące maszyny Turinga, które sprawiają, że …
2
Czy można rozstrzygnąć, czy dany kształt może pokryć płaszczyznę?
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 pozostanie nierozwiązane, chciałbym wiedzieć, jaka jest minimalna liczność zbioru płytek, …
1
Czy można rozstrzygać o równoważności jednoznacznych języków bezkontekstowych?
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 pozostaje nierozstrzygalny, ograniczając się do jednoznacznych języków bezkontekstowych. To znaczy, biorąc pod uwagę dwie …
2
Decydowanie, czy jednolity język kontekstowy jest prawidłowy
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 polega na tym, aby wiedzieć, co dzieje się w przypadku jednoargumentowych …
5
Jakie znaczące modele automatów mają wielomianowo rozstrzygalne ograniczenie?
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 ( M2))L.(M.1)⊆L.(M.2))L(M_1) \subseteq L(M_2) Oczywiste, które przychodzą na myśl, …
2
Czy można zdecydować równoważność w Systemie F (lub innym typowym rachunku λ)?
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 i B są rekurencyjnie nierozdzielne. Wynika z tego, …
1
Jaki jest najprostszy model obliczeniowy, dla którego problem pustki jest nierozstrzygalny?
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 maszyny język rozpoznawany / definiowany przez tę maszynę jest pusty. Tutaj opis …
1
Decydująca teoria asymptotycznego wzrostu
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 …
3
Czy P zawiera niezrozumiałe języki? (Wiki społeczności TCS)
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) ”. Preferowana jest nowsza wiki, ponieważ jej definicje …
1
Czy istnieje algorytm, który wyszukuje zakazanych nieletnich?
Twierdzenie Robertsona-Seymour'a głosi, że każda niewielka, zamknięta rodzinasolG\mathcal G wykresów można scharakteryzować przez skończoną liczbę zakazanych nieletnich. Czy istnieje algorytm wejściowy solG\mathcal G wypuszcza zakazanych nieletnich, czy jest to nierozstrzygalne? Oczywiście odpowiedź może zależeć od tego, w jaki sposób solG\mathcal Gjest opisany na wejściu. Na przykład jeślisolG\mathcal G jest podany …
1
Problem członkostwa dla niektórych klas gramatyki nieograniczonej
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 0,1,\overline{0} ,\overline{1} \rbraceP.PP0¯¯¯0 → ϵ0¯0→ϵ\overline{0} …
2
Czy możliwa jest meta-nierozstrzygalność?
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ć może wiadomo, że rozstrzygalność jest nierozstrzygalna (wszystko jest meta-nierozstrzygalne) i nie …
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.