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 samo nie powinno ich obowiązywać?

— użytkownik5507
źródło

Możesz użyć TM, aby ustalić, czy LBA zatrzymuje się na danym wejściu, sprawdzając, czy zatrzymuje się, powiedzmy, O (2 ^ 2 ^ n) krokami przez symulację. Każdy LBA działający dłużej niż ten utknie w nieskończonej pętli. Nie oznacza to, że LBA mogą rozwiązać problem zatrzymania dla ogólnych TM!

— Yonatan N

Automaty skończone są również rodzajem TM.

— Raphael

@Raphael Nie możesz edytować takich pytań. Zmieniłeś znaczenie pytania, dzięki czemu moja istniejąca odpowiedź nie była tematyczna, podczas gdy druga odpowiedź była poza tematem i jest teraz w temacie.

— babou

@babou Nie widzę, jak zmieniłem znaczenie pytania, i nie widzę, w jaki sposób jedno z dwóch pytań nie odpowiadało na pytanie (mimo że stosują różne podejścia).

— Raphael

@Rap Oryginalne pytanie dotyczy bardziej dyskursu logicznego niż formalnego uzasadnienia właściwości LBA i właśnie to usunąłeś z tytułu. Dla mnie jasne jest, że chociaż można udowodnić, że wstrzymanie jest rozstrzygalne dla LBA, PO zastanawia się, w jaki sposób może być kompatybilne z innymi stwierdzeniami dotyczącymi włączenia LBA do baz TM i nierozstrzygalności zatrzymania dla baz TM (czy mogę edytować z powrotem?) . BTW nie ma zamiaru dyskredytować odpowiedzi Yuvala. Oczekuję, że zdobędzie większość głosów, bo o to właśnie chodzi czytelnikom (co samo w sobie jest problemem pedagogicznym), nawet jeśli nie pozwolę sobie na to.

— babou

Odpowiedzi:

Problem zatrzymania można rozwiązać dla dowolnej maszyny Turinga, która wykorzystuje znaną ograniczoną ilość miejsca, poprzez uogólnienie argumentu podanego przez Yonatan N. Jeśli ilość miejsca to , wielkość alfabetu to , a liczba stanów to , to liczba możliwych konfiguracji jest . Jeśli maszyna zatrzymuje się, musi zatrzymać się w obrębie kroków , ponieważ w przeciwnym razie, zgodnie z zasadą szuflady, ma powtarzalną konfigurację i dlatego utknie w nieskończonej pętli. Dlatego, aby ustalić, czy maszyna się zatrzymuje, po prostu uruchamiamy ją dla kroków i sprawdzamy, czy zatrzymuje się w tym czasie. $S$ $A$ $Q$ $QSA^S$ $QSA^S$ $QSA^S$

— Yuval Filmus
źródło

Dlaczego ten argument działa w przypadku maszyn niedeterministycznych?

— Raphael

Z powodu twierdzenia Savitcha.

— Yuval Filmus

Nie znałem (ani nie pamiętałem) twierdzenia Savitcha innego niż nazwa (nigdy nie zrobiłem zbyt dużej złożoności). Nie jestem jednak pewien, czy można go wykorzystać w ten sposób, ponieważ dotyczy procedur decyzyjnych, tj. Obliczeń zatrzymania, podczas gdy rozstrzygalność zatrzymania jest dokładnie tym, co należy udowodnić. Dowód można dostosować tak, aby obejmował półdecyzje ograniczone przestrzenią, ale wydaje się, że łatwiej jest osobno udowodnić, że zatrzymanie jest rozstrzygalne dla ograniczonej przestrzennie TM, przekształcając w ten sposób półdecydowania w pełne decyzje. Jest to bliskie temu, co robią Hopcroft-Ullman-79 w ich lemacie 12-1, zanim udowodnią twierdzenie Savitcha.

— babou

Być może nie rozumiem tego, ale czy odpowiedzią jest dosłownie uruchomienie programu i sprawdzenie, czy utknie w nieskończonej pętli, czy nie?

— Mikayla Maki

@TrentonMaki Tak, właśnie tak jest.

— Yuval Filmus,

Wydajesz się mieć problem z logiką.

Z faktu, że istnieją książki, których nie można przeczytać, nie można wnioskować, że nie można przeczytać żadnej książki.

Mówienie, że problem zatrzymania jest nierozstrzygalny dla Maszyn Turinga, oznacza tylko, że istnieją maszyny, dla których nie można ustalić, czy zatrzymają się, czy nie za pomocą jakiejś jednolitej procedury, która zawsze się zatrzyma.

Istnieją jednak maszyny Turinga, które zatrzymują się. Teraz weź podzbiór Maszyn Turinga, zwanych Ładnymi Maszynami Turinga (NTM), tak że zawiera on tylko Maszyny Turinga, które zatrzymują się tylko wtedy, gdy taśma zawiera parzystą liczbę symboli. Jeśli wiadomo, że maszyna M pochodzi z tego zestawu, możesz w prosty sposób zdecydować, czy M się zatrzyma: sprawdzasz, czy liczba symboli na taśmie jest parzysta (wymaga tylko dwóch palców).

Ale ta procedura nie będzie działać dla TM, które nie są w zestawie NTM. (szkoda!)

Problem zatrzymania jest więc rozstrzygalny dla NTM, ale ogólnie nie dla TM, mimo że zestaw NTM jest zawarty w zestawie TM.

Jest to w rzeczywistości krytyczne, a czasem zapomniane, przy interpretacji wyniku nierozstrzygalności.

Może się okazać, że można udowodnić, że ważna właściwość jest nierozstrzygalna dla bardzo dużej rodziny obiektów matematycznych lub obliczeniowych.

Nie oznacza to, że powinieneś przestać szukać rozwiązania, ale tylko, że nie znajdziesz takiego rozwiązania dla całej rodziny.

Następnie możesz zidentyfikować odpowiednie podrodziny, dla których rozwiązanie problemu jest nadal ważne, i spróbować dostarczyć algorytmy, aby zdecydować, czy właściwość dotyczy członków tej mniejszej rodziny.

Zazwyczaj zatrzymanie jest nierozstrzygalne w przypadku TM, ale jest rozstrzygalne, często bardzo prosto, w przypadku dużych i przydatnych rodzin automatów, które wszystkie mogą być postrzegane jako specjalne przypadki TM.

— Babou
źródło

„Mówienie, że problem zatrzymania jest nierozstrzygalny dla maszyn Turinga, oznacza tylko, że istnieją maszyny, dla których nie można ustalić, czy zatrzymają się, czy nie, za pomocą procedury, która zawsze się zatrzyma”. - Niezupełnie prawda. Dla każdej TM problem zatrzymania jest rozstrzygalny. Ogólny problem decyzyjny jest nierozstrzygalny, tzn. Nie ma jednego algorytmu, który zajmowałby się wszystkimi bazami TM. (Myślę, że dla początkujących musi to być bardzo jasne. Por . Problem z pi .)

— Raphael

Bardziej bezpośrednim przykładem jest zestaw wszystkich baz TM, które zawsze się utrzymują. Twój dodaje dodatkowego smaku, ponieważ leży poza normalną hierarchią.

— Raphael

Dobrze. Powinienem był powiedzieć „jednolitą procedurę”, ale w moim umyśle było to domniemane, ponieważ powiedziałem „procedurę, która zawsze się zatrzyma”, co oznacza, że mogę jej używać na dowolnym wejściu, co oznacza dowolną maszynę. Ale prawdą jest, że procedura może działać poprawnie dla jednego komputera i robić wszystko dla innych komputerów. Cóż ... - - - - - - - - Jeśli chodzi o drugi komentarz, to właśnie napisałem na początku. Następnie zmieniłem zdanie, ponieważ myślałem, że mój przykład będzie łatwiejszy do zrozumienia intuicyjnie, ponieważ wybór maszyn nie opiera się tak bezpośrednio na właściwości, która ma zostać ustalona (choć jest blisko).

— babou

Krótko mówiąc, LBA ma skończoną liczbę konfiguracji, powiedzmy D. Dlatego możemy uruchomić kroki D i zakończyć wynik. Jeśli działa więcej niż kroki D, zgodnie z zasadą szuflady, możemy powiedzieć, że utknie w nieskończonej pętli.

— SiluPanda
źródło

Co to dodaje do istniejącej odpowiedzi ? To wydaje się po prostu powtarzać, mniej szczegółowo. Doceniam to, że starasz się wnieść swój wkład, wolimy jednak unikać powtarzania istniejących odpowiedzi i skupić się na odpowiadaniu na pytania, na które nie ma jeszcze dobrej odpowiedzi.

— DW