Pytania otagowane jako undecidability

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
Problemy z wydajnym rozwiązaniem, z wyjątkiem niewielkiej części nakładów
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 dziury”, w którym trudność niewykonalnego lub nierozstrzygalnego problemu ogranicza się do bardzo małego regionu, czarnej …
3
Czy P zawiera języki, których istnienie jest niezależne od PA lub ZFC? (Wiki społeczności TCS)
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ę podklasy:PPP języki gnostyczne i bazy TM (które można …
1
Dobre referencje na temat przybliżonych metod rozwiązywania problemów logicznych
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 algorytmów praktycznych. Można więc oczekiwać, że odpowiednie będą również algorytmy przybliżone dla problemów …
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
Nieporównywalne liczby naturalne
„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 Busy Beaver, , nie można ustalić (w ZFC lub w żadnym rozsądnym spójnym systemie …
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.