Pytania otagowane jako halting-problem

Pytania dotyczące problemu Halting, który decyduje o tym, czy dany program zatrzyma się na danym wejściu.

4
Zdefiniowanie problemu zatrzymania dla niedeterministycznych automatów
Podstawowa definicja maszyny Turinga (TM), przynajmniej w moim własnym podręczniku (Hopcroft + Ullman 1979), jest deterministyczna. Stąd moje własne rozumienie problemu zatrzymania dotyczy przede wszystkim deterministycznej TM, chociaż jestem świadomy, że można go rozważyć w przypadku innych rodzajów automatów. Zauważyłem również, że determinizm jest często mniej lub bardziej dorozumiany w …
3
Czy istnieje baza TM, która zatrzymuje się na wszystkich danych wejściowych, ale tej właściwości nie da się udowodnić?
Czy istnieje maszyna Turinga, która zatrzymuje się na wszystkich wejściach, ale z jakiegoś powodu ta właściwość nie jest możliwa do udowodnienia? Zastanawiam się, czy to pytanie zostało zbadane. Uwaga: „nie do udowodnienia” może oznaczać „ograniczony” system dowodowy (który w słabym sensie uważa, że ​​odpowiedź musi być twierdząca). Jestem oczywiście zainteresowany …
5
Maszyna Turinga + dylatacja czasu = rozwiązać problem zatrzymania?
Istnieją relatywistyczne czasoprzestrzenie (np. Czasoprzestrzenie MH; patrz Hogarth 1994), w których linia świata o nieskończonym czasie trwania może być zawarta w przeszłości skończonego obserwatora. Oznacza to, że normalny obserwator może mieć dostęp do nieskończonej liczby kroków obliczeniowych. Zakładając, że komputer może funkcjonować idealnie przez nieskończony czas (i wiem, że to …
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 …
3
Czy dowód nierozstrzygalności problemu zatrzymania oszukuje poprzez odwrócenie wyników?
Mam problem ze zrozumieniem problemu zatrzymania Turinga. Jego dowód zakłada, że ​​istnieje magiczna maszyna która może ustalić, czy komputer zatrzyma się lub zapętli na zawsze dla danego wejścia. Następnie dołączamy inną maszynę, która odwraca dane wyjściowe i mamy sprzeczność i dlatego H nie może istnieć.H.HHH.HH Obawiam się, że wydaje się, …
1
Czy są jakieś istniejące problemy, których nie można rozwiązać za pomocą wyroczni zatrzymującej?
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ć o problemie zatrzymania dla wyroczni Turinga +. Czy istnieją jakieś rzeczywiste, praktyczne przykłady …
1
Czy problem zatrzymania jest rozstrzygalny w przypadku trójwymiarowych automatów komórkowych?
Próbowałem dowiedzieć się, czy problem zatrzymania jest rozstrzygalny w przypadku trójwymiarowych jednowymiarowych automatów komórkowych. Definicja Niech f(w,i)f(w,i)f(w,i) oznacza konfigurację systemu w kroku czasowym iii . Bardziej formalnie f:A∗×N→A∗f:A∗×N→A∗f:A^*\times \mathbb{N} \to A^* , gdzie AAA jest alfabetem. Definicja. Automat komórkowy zatrzymał się w konfiguracji f(w,i)f(w,i)f(w,i) , jeśli ∀k∈N∀k∈N\forall k\in \mathbb{N} mamy …
2
Zatrzymanie problemu bez odniesienia
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 , a następnie wyprowadzamy sprzeczność za pomocą wystąpienia …
4
Czy maszyna Turinga (TM) może zdecydować, czy problem zatrzymania dotyczy wszystkich baz TM?
Na tej stronie istnieje wiele wariantów pytania, czy bazy TM mogą zadecydować o problemie zatrzymania, czy dla wszystkich innych baz TM lub niektórych podzbiorów. To pytanie jest nieco inne. Pytanie, czy problem zatrzymania dotyczy wszystkich baz TM może zostać rozstrzygnięty przez TM. Uważam, że odpowiedź brzmi „nie” i chcę sprawdzić …
2
Czy to możliwe, że problem zatrzymania można rozwiązać dla wszystkich danych wejściowych oprócz kodu maszyny?
To pytanie przyszło mi do głowy z powodu problemu z zatrzymaniem i nie mogłem znaleźć dobrej odpowiedzi online, zastanawiając się, czy ktoś może pomóc. Czy jest możliwe, że problem zatrzymania jest rozstrzygalny dla dowolnej TM na dowolnym wejściu, o ile wejście nie jest samą TM? Gruntownie: Halts(TM, I) IF TM …
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.