Czy istnieje podzbiór programów, które unikają problemu zatrzymania

Właśnie czytałem inne wyjaśnienie problemu zatrzymania i przyszło mi do głowy, że wszystkie problemy, które widziałem, podane jako przykłady, obejmują nieskończone sekwencje. Ale nigdy nie używam nieskończonych sekwencji w moich programach - trwają zbyt długo. Wszystkie aplikacje w świecie rzeczywistym mają dolną i górną granicę. Nawet liczby rzeczywiste nie są prawdziwymi wartościami rzeczywistymi - są przybliżeniami zapisanymi jako 32/64 bity itp.

Pytanie brzmi: czy istnieje podzbiór programów, które można ustalić, jeśli się zatrzymają? Czy to wystarczy dla większości programów. Czy mogę zbudować zestaw konstrukcji językowych, które mogę określić „haltability” programu. Jestem pewien, że zostało to gdzieś wcześniej zbadane, więc wszelkie wskazówki będą mile widziane. Język nie byłby kompletny, ale czy istnieje coś takiego jak prawie kompletny, co jest wystarczająco dobre?

Oczywiście taka konstrukcja musiałaby wykluczyć rekurencję i nieograniczoną liczbę pętli while, ale mogę napisać program bez tych dość łatwo.

Czytanie ze standardowego wejścia jako przykładu musiałoby być ograniczone, ale to dość proste - ograniczę mój wkład do 10 000 000 znaków itp., W zależności od dziedziny problemu.

tia

[Aktualizacja]

Po przeczytaniu komentarzy i odpowiedzi może powinienem powtórzyć moje pytanie.

Dla danego programu, w którym wszystkie wejścia są ograniczone, możesz ustalić, czy program się zatrzyma. Jeśli tak, jakie są ograniczenia języka i jakie są ograniczenia zestawu danych wejściowych. Maksymalny zestaw tych konstrukcji określałby język, który można wywnioskować, aby go zatrzymać lub nie. Czy przeprowadzono jakieś badania w tym zakresie?

[Aktualizacja 2]

oto odpowiedź, tak, w 1967 roku z http://www.isp.uni-luebeck.de/kps07/files/papers/kirner.pdf

Minsky już w 1967 r. Argumentował, że problem zatrzymania można przynajmniej teoretycznie rozwiązać dla systemów stanu skończonego [4]: ​​„... każda maszyna stanu skończonego, jeśli zostanie całkowicie sama, wpadnie w końcu w całkowicie okresowy okres powtarzalny wzór. Czas trwania tego powtarzającego się wzoru nie może przekraczać liczby stanów wewnętrznych maszyny ... ”

(więc jeśli trzymasz się skończonych maszyn Turinga, możesz zbudować wyrocznię)

Problem nie dotyczy danych wejściowych (oczywiście przy nieograniczonych danych wejściowych możesz mieć nieograniczony czas działania tylko do odczytu danych wejściowych), dotyczy liczby stanów wewnętrznych.

Gdy liczba stanów wewnętrznych jest ograniczona, teoretycznie możesz rozwiązać problem zatrzymania we wszystkich przypadkach (po prostu emuluj go, aż dojdziesz do zatrzymania lub powtórzenia stanu), a gdy nie jest, istnieją przypadki, w których nie można go rozwiązać . Ale nawet jeśli liczba stanów wewnętrznych jest w praktyce ograniczona, jest ona tak ogromna, że ​​metody polegające na ograniczeniu liczby stanów wewnętrznych są bezużyteczne, aby udowodnić zakończenie programów z wyjątkiem najbardziej trywialnych.

Istnieją bardziej praktyczne sposoby sprawdzania zakończenia programów. Na przykład, wyrażaj je w języku programowania, który nie ma rekurencji ani goto, a którego struktury zapętlające są powiązane z liczbą iteracji, które należy określić przy wejściu do pętli. (Należy pamiętać, że ograniczenie nie musi być tak naprawdę powiązane z efektywną liczbą iteracji, standardowym sposobem udowodnienia zakończenia pętli jest posiadanie funkcji, która, jak udowodniono, ściśle maleje z jednej iteracji do drugiej i warunek wejścia upewnij się, że jest pozytywny, możesz postawić pierwszą ocenę jako swoją granicę).

Po pierwsze, zastanów się, co by się stało, gdybyśmy mieli wykrywacz zatrzymania. Wiemy z przekątnego argumentu, że istnieje co najmniej jeden program, który spowodowałby, że detektor zatrzymania nigdy się nie zatrzyma lub udzieli błędnej odpowiedzi. Ale to dziwny i mało prawdopodobny program.

Istnieje jednak inny argument, że detektor zatrzymujący jest niemożliwy, i jest to bardziej intuicyjny argument, że detektor zatrzymujący byłby magiczny. Załóżmy, że chcesz wiedzieć, czy ostatnie twierdzenie Fermata jest prawdziwe, czy fałszywe. Po prostu piszesz program, który zatrzymuje się, jeśli jest prawdziwy, i działa wiecznie, jeśli jest fałszywy, a następnie uruchamiasz na nim detektor zatrzymania. Nie uruchamiasz programu , po prostu uruchamiasz wykrywacz zatrzymania w programie . Detektor zatrzymania umożliwiłby nam natychmiastowe rozwiązanie ogromnej liczby otwartych problemów w teorii liczb po prostu przez pisanie programów.

Czy potrafisz napisać język programowania, który gwarantuje produkcję programów, których zatrzymanie można zawsze ustalić? Pewnie. Po prostu nie może mieć pętli, warunków i używać dowolnie dużej ilości pamięci. Jeśli chcesz żyć bez pętli, instrukcji „if” lub ściśle ograniczonej ilości miejsca, możesz napisać język, którego zatrzymanie jest zawsze możliwe do ustalenia.

Polecam przeczytać Gödel, Escher, Bach . To bardzo zabawna i pouczająca książka, która porusza między innymi twierdzenie Gödela o niepełności i problem zatrzymania.

Aby odpowiedzieć na twoje pytanie w skrócie: problem zatrzymania jest rozstrzygalny, o ile twój program nie zawiera whilepętli (ani żadnej z wielu jej możliwych manifestacji).

Dla każdego programu, który działa na ograniczonej ilości pamięci (w tym wszelkiego rodzaju pamięci), problem zatrzymania można rozwiązać; tzn. nierozstrzygalny program musi zużywać coraz więcej pamięci.

Ale i tak ten wgląd nie oznacza, że ​​można go wykorzystać do rozwiązywania rzeczywistych problemów, ponieważ program zatrzymujący, działający na zaledwie kilku kilobajtach pamięci, może z łatwością trwać dłużej niż pozostały czas życia wszechświata.

Aby (częściowo) odpowiedzieć na pytanie „Czy istnieje podzbiór programów, które unikają problemu zatrzymania”: tak, w rzeczywistości istnieje. Jednak ten podzbiór jest niesamowicie bezużyteczny (zauważ, że podzbiór, o którym mówię, jest ścisłym podzbiorem programów, które się zatrzymują).

Badanie złożoności problemów dla „większości danych wejściowych” nazywa się złożonością przypadków ogólnych . Definiujesz pewien podzbiór możliwych danych wejściowych, udowadniasz, że ten podzbiór obejmuje „większość danych wejściowych” i podajesz algorytm, który rozwiązuje problem dla tego podzbioru.

Na przykład problem zatrzymania można rozwiązać w czasie wielomianowym dla większości danych wejściowych (w rzeczywistości w czasie liniowym, jeśli dobrze rozumiem papier ).

Jednak wynik ten jest raczej bezużyteczny ze względu na trzy uwagi dodatkowe: po pierwsze, mówimy o maszynach Turinga za pomocą pojedynczej taśmy, a nie o programach komputerowych w świecie rzeczywistym na komputerach w świecie rzeczywistym. O ile mi wiadomo, nikt nie wie, czy to samo dotyczy komputerów w świecie rzeczywistym (nawet jeśli komputery w świecie rzeczywistym mogą być w stanie obliczyć te same funkcje co maszyny Turinga, liczbę dozwolonych programów, ich długości i czy mogą się zatrzymać zupełnie inny).

Po drugie, musisz uważać, co oznacza „większość danych wejściowych”. Oznacza to, że prawdopodobieństwo, że losowy program o „długości” n może być sprawdzony przez ten algorytm, wynosi 1, a n dąży do nieskończoności. Innymi słowy, jeśli n jest wystarczająco duże, to losowy program o długości n może prawie na pewno zostać sprawdzony przez ten algorytm.

Które programy można sprawdzić według metody opisanej w artykule? Zasadniczo wszystkie programy, które zatrzymują się przed powtórzeniem stanu (gdzie „stan” w przybliżeniu odpowiada linii kodu w programie).

Chociaż prawie wszystkie programy można sprawdzić w ten sposób, żaden z programów, które można sprawdzić w ten sposób, nie jest bardzo interesujący i zwykle nie są projektowane przez ludzi, więc nie ma to żadnej praktycznej wartości.

Wskazuje również, że złożoność przypadków ogólnych prawdopodobnie nie pomoże nam w rozwiązaniu problemu zatrzymania, ponieważ prawie wszystkie interesujące programy są (najwyraźniej) trudne do sprawdzenia. Lub, alternatywnie: prawie wszystkie programy są nieciekawe, ale łatwe do sprawdzenia.

W rzeczywistości istnieją programy, które rozwiązują problem zatrzymania innych problemów przez cały czas. Są częścią systemu operacyjnego, na którym działa komputer. Nierozstrzygalność to dziwne twierdzenie, które mówi tylko, że nie ma takiego programu, który działałby dla WSZYSTKICH innych programów.

Jedna osoba słusznie stwierdziła, że ​​dowód zatrzymania wydaje się być jedynym programem, dla którego nie można go rozwiązać, ponieważ nieskończenie śledzi się jak lustro. Ta sama osoba stwierdziła również, że gdyby istniała maszyna zatrzymująca, byłaby to magia, ponieważ oznaczałoby to trudne problemy matematyczne, informując nas z wyprzedzeniem, czy algorytm rozwiązujący się zatrzyma.

W obu przypadkach założono, że maszyna zatrzymująca nie śledzi, ponieważ nie ma dowodu, że śledzi. Jednak w rzeczywistości faktycznie śledzi / uruchamia program, w którym jest uruchamiany z podanymi danymi wejściowymi.

Dowód logiczny jest co najmniej prosty. Gdyby nie musiał śledzić przynajmniej pierwszego kroku, nie potrzebowałby danych wejściowych wraz z programem, na którym jest uruchomiony. Aby w jakikolwiek sposób wykorzystać informacje, musi przynajmniej prześledzić pierwszy krok, zanim spróbuje przeanalizować, dokąd zmierza ta ścieżka.

Trudne matematyczne problemy wymienione w górnej odpowiedzi to takie, w których nie można szybko przewinąć do przodu, aby znaleźć odpowiedź, co oznacza, że ​​problem zatrzymania musiałby być kontynuowany, dopóki jakiś wzór nie zostanie rozpoznany.

Tak więc jedynym praktycznym argumentem, który można wyciągnąć z problemu zatrzymania, jest to, że maszyna zatrzymująca nie jest w stanie ustalić wyniku zoptymalizowanego rozwiązania problemu szybciej, niż rozwiązanie problemu może zakończyć.

Podanie formalnego dowodu na to rozumowanie jest trudniejsze i chociaż uważam, że mógłbym, próba wyjaśnienia go każdemu ze środowisk akademickich spowoduje, że wyrzucą małpę jak furia i huśtają się z żyrandola. Najlepiej po prostu nie kłócić się z tymi ludźmi.

oto odpowiedź, tak, w 1967 roku z http://www.isp.uni-luebeck.de/kps07/files/papers/kirner.pdf

Minsky już w 1967 r. Argumentował, że problem zatrzymania można przynajmniej teoretycznie rozwiązać dla systemów stanu skończonego [4]: ​​„... każda maszyna stanu skończonego, jeśli zostanie całkowicie sama, wpadnie w końcu w całkowicie okresowy okres powtarzalny wzór. Czas trwania tego powtarzającego się wzoru nie może przekraczać liczby stanów wewnętrznych maszyny ... ”

(więc jeśli trzymasz się skończonych maszyn Turinga, możesz zbudować wyrocznię)

Oczywiście, jak długo to trwa

czy istnieje podzbiór programów, które można ustalić, jeśli się zatrzymają?

Tak.

Czy to wystarczy dla większości programów?

Zdefiniuj „większość”.

Czy mogę zbudować zestaw konstrukcji językowych, które mogę określić „możliwości zatrzymania” programu?

Tak.

czy istnieje coś takiego jak prawie całkowite zakończenie, co jest wystarczająco dobre?

Zdefiniuj „prawie”.

Wiele osób pisze Python bez użycia whileinstrukcji lub rekurencji.

Wielu ludzi pisze Javę, używając tylko forinstrukcji z prostymi iteratorami lub licznikami, które można w prosty sposób udowodnić, że się kończą; i piszą bez rekurencji.

Jest to dość łatwe do uniknięcia whilei rekurencji.

Czy dla danego programu, w którym wszystkie wejścia są ograniczone, możesz ustalić, czy program się zatrzymuje?

Nie.

Jeśli tak, jakie są ograniczenia języka i jakie są ograniczenia zestawu danych wejściowych.

Um. Problem zatrzymania oznacza, że ​​program nie może nigdy określić rzeczy o programach tak złożonych jak on sam. Możesz dodać jedno z wielu ograniczeń, aby obejść problem zatrzymania.

Standardowym podejściem do problemu zatrzymania jest dopuszczenie dowodów przy użyciu nieco „bogatszego” zestawu formalizmów matematycznych niż jest to możliwe w języku programowania.

Łatwiej jest rozszerzyć system dowodowy niż ograniczyć język. Wszelkie ograniczenia prowadzą do argumentów dla jednego algorytmu, który jest trudny do wyrażenia z powodu ograniczenia.

Maksymalny zestaw tych konstrukcji określałby język, który można wywnioskować, aby go zatrzymać lub nie. Czy przeprowadzono jakieś badania w tym zakresie?

Tak. Nazywa się to „teorią grupy”. Zestaw wartości zamkniętych w ramach zestawu operacji. Całkiem dobrze rozumiane rzeczy.