Pytania otagowane jako undecidability

Pytania dotyczące problemów, których nie może rozwiązać żadna maszyna Turinga.

4
Czy problem grafu skończonego jest rozstrzygalny? Jakie czynniki decydują o problemie?
Chcę wiedzieć, czy można rozwiązać następujący problem i jak się dowiedzieć. W każdym problemie, który widzę, mogę powiedzieć „tak” lub „nie”, więc czy większość problemów i algorytmów można rozstrzygać, z wyjątkiem kilku (które podano tutaj )? Wejście: kierowane i skończonych wykres z i , jak wierzchołki Pytanie: Czy ścieżką w …
1
Czy jest rozstrzygalne, czy automat przesuwający rozpoznaje dany regularny język?
Problem, czy dwa automaty przesuwające rozpoznają ten sam język, jest nierozstrzygalny. Problem, czy automat przesuwający rozpoznaje pusty język, jest rozstrzygalny, a zatem decydujące jest, czy rozpoznaje dany język skończony. Nie można rozstrzygnąć, czy język akceptowany przez automat pushdown jest regularny. Ale ... ... czy można zadecydować, czy automat przesuwający rozpoznaje …
1
Czy nierozwiązywalność problemu N-ciała jest równoważna problemowi zatrzymania
Nie ma ogólnego analitycznego rozwiązania problemu n-ciała, który mógłby wytworzyć funkcję analityczną, która mogłaby zostać użyta do nadania stanu układu n-ciała w dowolnej chwili t z dokładną dokładnością. Istnieją jednak pewne szczególne przypadki układów n-ciała, dla których znana jest funkcja analityczna. W podobny sposób nie ma ogólnego algorytmu, który mógłby …
5
Czy istnieją nierozstrzygalne właściwości niekompletnych automatów?
Czy istnieją nierozstrzygalne właściwości automatów z ograniczeniami liniowymi (unikanie sztuczki z pustym językiem ustawiania)? A co z deterministycznym automatem skończonym? (odłóż na bok trudność). Chciałbym uzyskać przykład (jeśli to możliwe) niezdecydowanego problemu, który jest zdefiniowany bez jawnego używania maszyn Turinga . Czy kompletność modelu Turinga jest niezbędna do obsługi problemów …
1
W przypadku maszyny Turinga , w jaki sposób zestaw maszyn które są „krótsze” niż i które akceptują ten sam język, jest rozstrzygalny?
Zastanawiam się, jak to się stało, że język jest w następujący .RR\mathrm R L.M.1= { ⟨M2)⟩∣∣M.2) jest TM, a L ( M1) = L ( M2)) , A | ⟨ M1⟩ | > | ⟨ M2)⟩ | }L.M.1={⟨M.2)⟩|M.2) jest TM, i L.(M.1)=L.(M.2)), i |⟨M.1⟩|>|⟨M.2)⟩|}L_{M_1}=\Bigl\{\langle M_2\rangle \;\Big|\;\; M_2 \text{ is a …
2
Czy jest rozstrzygalne, czy TM osiągnie jakąś pozycję na taśmie?
Mam te pytania ze starego egzaminu, który próbuję rozwiązać. Dla każdego problemu wejście jest kodowanie pewnej maszyny Turingowi .MMM Dla liczby całkowitej i następujących trzech problemów:c>1c>1c>1 Czy to prawda, że ​​dla każdego wejścia , M nie przechodzi przez pozycję podczas pracy na ?xxx|x|+c|x|+c|x|+cxxx Czy to prawda, że ​​dla każdego wejścia …
3
nierozstrzygalny problem i jego negacja jest nierozstrzygalna
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 jego uzupełnienie są nierozstrzygalne i nierozstrzygalne? Myślałem o języku diagonalizacji …
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 …
2
Czy wszystkie języki kontekstowe są rozstrzygalne?
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 ograniczany liniowo jest bezpośrednio poniżej decydującego w porządku tego artykułu. Jeśli …
4
Operacje, w których klasa nierozstrzygalnych języków nie jest zamknięta
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 też na to przykłady? Czy to znaczy, że zamknięcie nierozstrzygalnego …
6
Nierozstrzygalne problemy ograniczają teorie fizyczne
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 określić, przy dowolnym ustawieniu wejściowym obwodów, czy obwód się zatrzyma. Wydaje się to trywialnością, ale czy nie daje …
1
Redukcje wśród nierozstrzygniętych problemów
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 trudności problemu. Ale moje pytanie brzmi - czy …
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.