Czytałem odpowiedź na ostatnie pytanie i przyszło mi do głowy coś dziwnego, efemerycznego. Moje pytanie może zdradzić, że moim teoretycznym kotletom poważnie brakuje (głównie prawdy) lub że jest zbyt wcześnie, aby przeczytać tę stronę. Teraz, gdy wyłączenie odpowiedzialności jest na drodze...
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ć...
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^* ,...
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...
W Chaimin's Meta Math! W Quest For Omega krótko mówi o 10. problemie Hilberta. Następnie mówi, że dowolne równanie diofantyczne można zmienić na dwa równe wielomiany o dodatnich współczynnikach całkowitych: .p = 0p = 0p=0p=0p = 0⟺p1= p2)p=0⟺p1=p2p=0 \iff p_1 = p_2 Następnie mówi, że możemy myśleć...
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?...