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

21

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ę)

daven11
źródło
13
„sekwencje nieskończone… trwają zbyt długo”. Rozśmieszyło mnie głośno.
Bryan Oakley,
3
Uważam, że SQL92 i wyrażenia regularne są przykładami języków, które na pewno zostaną zatrzymane.
Elian Ebbing,
2
W odpowiedzi umieść post „Update2 ...”.
S.Lott,
2
Nie musisz wykluczać rekurencji. Jeśli ograniczysz rekurencję do ścisłych warunków podrzędnych argumentów odbiorcy, zawsze będziesz w stanie udowodnić zakończenie. Jest to wystarczający wymóg - żadne „ograniczone pętle” i podobne nie są konieczne, dopóki używasz cyfr Kościoła.
SK-logic
1
Język Idris używa pisania zależnego i sprawdzania poprawności, aby udowodnić, że twoje programy kończą się przed ich uruchomieniem. Jest podobny do Haskell i umożliwia rekurencję, ale nie rekurencję ogólną - tylko rekurencja, którą może udowodnić (poprzez typy zależne) prowadzi do pewnego stanu końcowego.
Jack

Odpowiedzi:

8

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ę).

AProgrammer
źródło
10

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.

Eric Lippert
źródło
2
Można użyć instrukcji if, jeśli skok zawsze musi być do przodu, nigdy do tyłu. Mam na myśli ograniczony podzbiór języka BASIC, w którym „GOTO X” oznacza przejście do numeru linii currentLine + X, a X musi być większy niż 0. Jeśli linia jest nieprawidłowa, to zatrzymaj się. Zwiększyłoby to zapotrzebowanie na pamięć, ale pozwoliłoby na pewną nietrywialną logikę. Prawdopodobnie jest to równoważne skończonej maszynie stanów, w której wierzchołki tworzą wykres i wykres ten może nie mieć żadnych cykli, w przeciwnym razie FSM jest nieprawidłowy. Ponadto każdy stan będący ślepym zaułkiem musi być stanem akceptującym.
Job
3
mógł mieć ograniczone pętle - na przykład dla i = 1 do 10, podobnie dobrze zachowane iteratory. Czy istnieje więc klasa skończonych problemów, które można rozwiązać - twierdzenie fermatów ponownie bierze udział w nieskończonej sekwencji liczb rzeczywistych. Ale jeśli ograniczymy domenę do liczb mniejszych niż 1 000 000, wówczas się zatrzyma.
daven11
2
Dlaczego nie warunki? Wygląda na to, że warunki bez skoków można zawsze zatrzymać ...
Billy ONeal,
2
@nikie: Oczywiście to słaby argument. Chodzi o to, że taki wykrywacz zatrzymania byłby w stanie udowodnić lub obalić takie stwierdzenia bez konieczności znalezienia dowodu . Intuicja, którą zamierzam tutaj rozwinąć, polega na tym, że język, dla którego można napisać trywialny detektor zatrzymania, jest językiem, który nie może reprezentować nawet prostych problemów w teorii liczb, takich jak Ostatnie twierdzenie Fermata lub Hipoteza Goldbacha, i dlatego prawdopodobnie nie jest bardzo przydatny język.
Eric Lippert,
3
@EricLippert: Wrong. Taki język będzie miał pętle, odpowiednie miejsce do przechowywania i wiele innych przydatnych rzeczy. Można w nim zakodować prawie wszystko. Oto tutaj: coq.inria.fr
SK-logic
6

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).

zvrba
źródło
Przepraszam, źle cię odczytałem. Usunąłem swój komentarz, ale zmienię zalecenie GEB.
AProgrammer
@zvrba To jest na mojej liście czytelniczej od jakiegoś czasu - prawdopodobnie czas na nurkowanie.
daven11
5

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.

użytkownik 281377
źródło
3

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.

Alex ten Brink
źródło
2
-1, To jest złe na tak wielu poziomach ...
user281377
1
Po pierwsze, komputery ze świata rzeczywistego nie są w stanie obliczyć niczego, czego nie potrafi maszyna Turinga. Do tej pory nikt nie pokazał, że komputer w świecie rzeczywistym jest bardziej zdolny (pod względem obliczalności) niż maszyna Turinga. Po drugie, jeśli program powtórzy swój stan, nie zatrzyma się, więc problem zatrzymania został rozwiązany dla tego programu i danych wejściowych. Pamiętaj: Problem zatrzymania polega na podjęciu decyzji, czy program zatrzyma się na danych wejściowych. Pętla nieskończona jest w porządku po pozytywnym wykryciu. Wreszcie: istnieje duży zestaw przydatnych programów, dla których problem zatrzymania można rozwiązać: programy działające na ograniczonej przestrzeni dyskowej.
user281377,
Co do twojego pierwszego wydania: jak zauważono w artykule, wykazanie, że jakiś model obliczeń jest kompletny w Turingu, nie zachowuje liczby programów dokładnie zatrzymanych, więc wynik, który udowodnią, nie ma natychmiastowego znaczenia dla innych modeli obliczeń. Jestem w pełni świadomy kompletności Turinga i nie jestem całkowicie pewien, dlaczego sprawia, że ​​moja odpowiedź jest „błędna”.
Alex ten Brink,
Jeśli chodzi o twój drugi problem: stany, o których mówię, nie są tym samym, co „stan maszyny”, o którym zwykle mówi się (co obejmuje stan wszystkiego, co może mieć stan), ale raczej stan automat skończony służy do sterowania maszyną Turinga, która z grubsza odpowiada linii kodu, nad którą program pracuje w dowolnym momencie podczas wykonywania. Po powtórzeniu wiersza kodu zawartość twojej pamięci może być inna, więc nie oznacza to natychmiastowego zatrzymania. Zaktualizuję moją odpowiedź, aby to wyjaśnić.
Alex ten Brink,
@ammoQ: Nie, problemu zatrzymania nie da się rozwiązać, jeśli mówimy o systemach rzeczywistych z ograniczoną pamięcią, ponieważ oznaczałoby to zbudowanie systemu rzeczywistego, który mógłby obsługiwać kombinacje stanów. Ponieważ liczba możliwych stanów rejestru w większości procesorów przekracza liczbę atomów we Wszechświecie, nie będziesz w stanie tego zrobić.
David Thornley,
3

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.

Terrence Kwasha
źródło
1

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

daven11
źródło
0

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.

S.Lott
źródło
„prawie” jest tym, o co pytam. Czy istnieje skończona klasa problemów, dla których można powiedzieć, że program się zatrzymuje i jak ograniczony jest problem? Na przykład instrukcja if (i <10), a następnie print (i) zatrzymuje się dla wszystkich i. Jeśli ograniczę domenę i do 32-bitowych liczb całkowitych, to również się zatrzyma.
daven11
Pamiętaj, że forpętla to pętla while, a ludzie często stawiają bardziej skomplikowane rzeczy w warunku warunku niż po prostu x < 42.
Billy ONeal,
@BillyONeal: Dobra uwaga. W Pythonie forpętla jest bardzo, bardzo ściśle ograniczona do pracy przez iterator. Bardziej ogólna forpętla w Javie może jednak zawierać dodatkowe warunki, które unieważniają proste użycie iteratora.
S.Lott,
„Czy istnieje skończona klasa problemów, dla których można powiedzieć, że program się zatrzymuje?” Odpowiedź pozostaje twierdząca. „jak ograniczony jest problem?” Um. Skończone jest skończone. Jeśli rezygnujesz z prób przybliżania liczb rzeczywistych i trzymania się liczb naturalnych, zamkniętych we wszystkich operacjach matematycznych, robisz zwykłą teorię grup. Arytmetyka modułowa. Nic specjalnego. Nie jest jasne, o co pytasz. Pytasz, czym jest arytmetyka modułowa?
S.Lott,
@ S.Lott Mam na myśli liczby przedstawione w maszynie, a nie liczby w sensie abstrakcyjnym. Pomyśl więc o liczbach jako o stałej liczbie bitów. Liczby te mają nieco inne reguły niż liczby całkowite i liczby rzeczywiste. Mam nadzieję, że to ma sens.
daven11