Jakie są najprostsze przykłady programów, których nie wiemy, czy się kończą?

27

Problem zatrzymania mówi, że nie ma algorytmu, który określi, czy dany program się zatrzyma. W rezultacie powinny istnieć programy, o których nie możemy powiedzieć, czy się kończą, czy nie. Jakie są najprostsze (najmniejsze) znane przykłady takich programów?

MaiaVictor
źródło
W swoich odpowiedziach zaprzeczasz ..... Dzięki! Ale program zatrzymania zakłada znajomość źródła. ... Jeśli to prawda, odpowiedziałeś na swoje pytanie. Program zatrzymania będzie już wiedział. Wyobraź sobie system kontrolujący znak, który zawsze świeci i miga, kiedy się wyłącza? Awaria zasilania, wyłącznik zasilania lub podczas sekwencji lampy błyskowej. Lub biorąc pod uwagę podtrzymanie bateryjne i generator, nigdy.
htm11h
Dodam, że problem zatrzymania jest problemem tylko wtedy, gdy nie ustawisz górnej granicy czasu. Z pewnością nie ma w praktyce różnicy między otrzymaniem odpowiedzi za późno, aby była przydatna, a jej nigdy nie otrzymaniem. Możesz zapytać, czy program zwróci odpowiedź w ciągu kilku kroków, takich jak definicja poprawności w czasie rzeczywistym. Jeśli nie możesz zagwarantować terminowej odpowiedzi, masz po prostu program, który nie ma gwarancji poprawności.
Rob
1
@Rob To nie jest prawda. Jeśli nie wiesz, czy maszyna się zatrzyma, możesz poczekać w nieskończoność, aby zobaczyć, czy się zatrzyma; po tysiącleciu nadal nie będziesz wiedział, czy to się skończy, powiedzmy, następnego dnia.
Kyle Strand
@KyleStrand Zgadzam się z tobą. Ale mówię też, że w praktyce jest to całkowicie przesadzona kwestia, ponieważ wszystkie realistyczne obliczenia podlegają terminom (milisekundy do miesięcy). Jeśli potrzebujesz odpowiedzi w 5 sekund, aby była użyteczna, jedyne, co się liczy, to czy możesz zagwarantować odpowiedź w 5 sekund. Załóżmy, że mógłby zagwarantować odpowiedź daną nieokreśloną ilość czasu, aby obliczyć. To byłaby bezużyteczna gwarancja.
Rob

Odpowiedzi:

41

Dość prostym przykładem może być program testujący hipotezę Collatza :

f(n)={HALT,if n is 1f(n/2),if n is evenf(3n+1),if n is odd

Jest znane , w celu zatrzymania do na poziomie co najmniej , ale na ogół jest to problemem otwartym.n5×2605.764×1018

npostavs
źródło
9
Dla podkreślenia mojej uwagi z komentarza pod pytaniem: problem „czy zatrzymuje się dla wszystkich ?” jest obliczalny . nf(n)n
Raphael
6
@KyleStrand Zobacz tutaj .
Raphael
10
@KyleStrand, Raphael ma 100% poprawności. Jest to powszechne nieporozumienie. Musisz bardzo uważnie prześledzić, co mówi definicja, i wtedy możesz odkryć, że twoja intuicja nie do końca pasuje do definicji. Według definicji obliczalności, wystarczy, że istnieje maszyna Turinga, aby ją obliczyć - to nie ma znaczenia, czy wiemy, co to jest maszyna Turinga. Po zobaczeniu tego wielu uczniów myśli, że to oszustwo, ale tak nie jest - to tylko konsekwencja definicji.
DW
2
@KyleStrand Musisz pozbyć się pomysłu, że program musi rozwiązać problem . To nie. Musi jedynie podać odpowiedź, co jest trywialnym zadaniem. Algorytmicznie problemy ze skończonymi zestawami instancji są nudne, ponieważ możemy na stałe zakodować odpowiedzi. (A nawet jeśli my nie znamy odpowiedzi, nadal nie wiemy, że jest poprawny algorytm). W ogóle, gdy pokazano, że nie istnieje algorytm do czegoś, nie dostać się do żadnych założeń o tym, jak to będzie praca. Nasz brak wyobraźni nie stanowi dowodu.
Raphael
2
@KyleStrand Afaik, używam standardowej definicji obliczalności, jak się ją obecnie uczy (i, afaik, istnieje od dziesięcioleci). Zalecam przyswojenie odpowiedzi i powiązanych materiałów oraz ustalenie, gdzie popełniłeś błąd. Nie ma sensu dla mnie i innych powtarzanie tych samych rzeczy w kółko. Jeszcze jedna próba: definicja obliczalności jest z natury egzystencjalna, a nie konstruktywna. Tak długo, jak myślisz w dziedzinie klasycznej logiki, nie ma potrzeby przekazywania algorytmu „rozwiązywania” - musimy tylko pokazać, że istnieje taki, który daje właściwe odpowiedzi.
Raphael
31

Problem zatrzymania mówi, że nie ma algorytmu, który określi, czy dany program się zatrzyma. W rezultacie powinny istnieć programy, o których nie możemy powiedzieć, czy się kończą, czy nie.

„My” nie jest algorytmem =) Nie ma ogólnego algorytmu, który mógłby określić, czy dany program zatrzymuje się dla każdego programu .

Jakie są najprostsze (najmniejsze) znane przykłady takich programów?

Rozważ następujący program:

n = 3
while true:
    if is_perfect(n):
            halt()
    n = n + 2

Funkcja is_perfect sprawdza, czy n jest liczbą całkowitą . Nie wiadomo, czy są jakieś nieparzyste liczby idealne, więc nie wiemy, czy ten program się zatrzyma, czy nie.

avsmal
źródło
7
Jesteśmy algorytmem.
PyRulez
3
@PyRulez nie ma dowodów na to, że moc obliczeniowa ludzkiego umysłu jest równoważna maszynie Turinga. Dowód nie działa, np. Nie wiadomo, jak symulować jeden umysł w drugim.
avsmal
1
@avsmal W porządku, ale jest bardzo mało prawdopodobne, że jesteśmy zdolni do hiper obliczeń.
PyRulez
2
@PyRulez John Lucas i Roger Penrose zasugerowali, że ludzki umysł może być wynikiem pewnego rodzaju obliczeń „nie-algorytmicznych” ulepszonych kwantowo-mechanicznie. To jest pewne silne założenie. Ale przynajmniej nasz umysł może mieć jakieś źródło niepewności. I to wystarczy, aby przełamać dowód: nie można zanegować „zrandomizowanej” (dla jakiejś odpowiedniej definicji tego, co oznacza zrandomizowanego) maszyny Turinga, jeśli nie wiadomo, czy się zatrzyma.
avsmal
5
Czy obliczenia kwantowe są uważane za hiperkomputery? Zakładałem, że komputery kwantowe mogą być doskonale symulowane przez maszyny Turinga - tylko trochę wolniej.
MaiaVictor,
10

Ty piszesz:

Problem zatrzymania mówi, że nie ma algorytmu, który określi, czy dany program się zatrzyma. W rezultacie powinny istnieć programy, o których nie możemy powiedzieć, czy się kończą, czy nie.

Jest to niesekurujące, w obu kierunkach. Ulegasz powszechnemu błędowi , któremu warto się zająć.

Biorąc pod uwagę każdy ustalony program , jego problem zatrzymania („Czy zawsze się zatrzymuje?”) Jest zawsze rozstrzygalny, ponieważ odpowiedź brzmi „tak” lub „nie”. Nawet jeśli nie możesz powiedzieć, który to jest, wiesz, że jeden z dwóch trywialnych algorytmów, które zawsze odpowiadają „tak” lub. „nie” rozwiązuje problem uwięzieniaP PPPP

Tylko jeśli potrzebujesz, aby algorytm rozwiązał problem zatrzymania dla wszystkich programów1, możesz pokazać, że taki algorytm nie istnieje.

Wiedząc, że problem zatrzymania jest nierozstrzygalny, nie oznacza, że ​​istnieją programy, których nikt nie może udowodnić zakończenia lub zapętlenia. Nawet jeśli nie jesteś potężniejszy od maszyny Turinga (co jest tylko hipotezą, nie udowodnionym faktem), wiemy tylko, że żaden pojedynczy algorytm / osoba nie może dostarczyć takiego dowodu dla wszystkich programów. Dla każdego programu może być inna osoba.

Niektóre bardziej podobne czytanie:


Widzisz więc, że twoje aktualne pytanie (jak powtórzono poniżej) nie ma nic wspólnego z tym, czy problem zatrzymania jest obliczalny. W ogóle.

Jakie są najprostsze (najmniejsze) znane przykłady [programów, o których nie wiemy, że się zatrzymują lub zapętlają]?

To samo w sobie jest ważnym pytaniem; inni dali dobre odpowiedzi. Zasadniczo możesz przekształcić każde zdanie o nieznanej wartości prawdy w przykład, pod warunkiem że ma ono wartość prawdy:S

g(n)={1,S true,g(n+1),else.

To prawda, że ​​nie są one zbyt „naturalne”.


  1. Niekoniecznie wszystkie , ale w pewnym sensie „wielu”. Przynajmniej nieskończenie wiele.
Raphael
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
Raphael
Aby spróbować sformułować to inaczej dla własnego zrozumienia, czy słuszne jest stwierdzenie, że chociaż nie ma unikalnego algorytmu, który może ustalić, czy dowolny program może zostać zatrzymany, może istnieć jakiś algorytm specyficzny dla programu, który rozwiąże problem zatrzymania każdego możliwego programu?
Asad Saeeduddin
@AsadSaeeduddin Jest „gorzej”: dla każdego określonego skończonego zestawu programów problem zatrzymania jest trywialny . Każdy skończony zestaw jest rozstrzygalny.
Raphael
7

Jakikolwiek otwarty problem dotyczący istnienia liczby o określonych właściwościach powoduje powstanie takiego programu (takiego, który szuka takiej liczby). Weźmy na przykład hipotezę Collatza; ponieważ nie wiemy, czy to prawda, nie wiemy również, czy następujący program zakończy działanie:

    n:=1;
    found:=false;
    while not found do
      s:={};
      i:=n;
      while i not in s do
        add i to s;
        if i even then i:=i/2 else i:=3i+1
      if 1 not in s then found:=true;
      n:=n+1  
Klaus Draeger
źródło
6

Biorąc pod uwagę, że problem Busy Beaver nie został rozwiązany w przypadku maszyny Turinga z 5 stanami i 2 symbolami, musi istnieć maszyna Turinga z tylko pięcioma stanami i tylko dwoma symbolami, które nie zostały zatrzymane lub nie zostały uruchomione po uruchomieniu pustej taśmy . To bardzo krótki, zwięzły i zamknięty program.

nie-użytkownik
źródło
0

pytanie jest trudne, ponieważ rozstrzygalność (formalizacja równoważna CS / uogólnienie problemu zatrzymania) jest związana z językami, dlatego należy ją przekształcić w tym formacie. wydaje się, że nie zwracano na to większej uwagi, ale wiele otwartych problemów w matematyce / CS można łatwo przekształcić w problemy (języki) o nieznanej rozstrzygalności. dzieje się tak z powodu ścisłej zgodności między dowodzeniem twierdzeń a analizą (nie) rozstrzygalności. na przykład (nieco jak inna odpowiedź nieparzysta liczb idealnych), weźmy hipotezę o dwóch liczbach pierwszych, która pochodzi od Greków (ponad 2 tysiące lat temu) i jest przedmiotem znacznych najnowszych badań, np. Zhanga / Tao. przekonwertuj go na problem algorytmiczny w następujący sposób:

Dane wejściowe: n . Wyjście: T / N istnieje co najmniej n podwójnych liczb pierwszych.

algorytm szuka podwójnych liczb pierwszych i zatrzymuje się, jeśli znajdzie n z nich. nie wiadomo, czy ten język jest rozstrzygalny. rozwiązanie problemu podwójnych liczb pierwszych (które pyta, czy istnieje liczba skończona lub nieskończona) rozwiązałoby również rozstrzygalność tego języka (jeśli udowodniono / odkryto, ile ich jest, jeśli jest skończony).

inny przykład, weź hipotezę Riemanna i rozważ ten język:

Dane wejściowe: n . Wyjście: T / N istnieje co najmniej n nietrywialnych zer funkcji zeta Riemanna.

algorytm wyszukuje nietrywialne zera (kod nie jest szczególnie skomplikowany, jest podobny do znalezienia pierwiastka, a istnieją inne równoważne sformułowania, które są stosunkowo proste, które w zasadzie obliczają sumy „parzystości” wszystkich liczb pierwszych mniejszych niż x itp.) i zatrzymuje się, jeśli znajduje n z nich i ponownie, nie wiadomo, czy ten język jest rozstrzygalny, a rozdzielczość jest „prawie” równoważna rozwiązaniu hipotezy Riemanna.

a może jeszcze bardziej spektakularny przykład? ( zastrzeżenie, prawdopodobnie również bardziej kontrowersyjne)

Dane wejściowe: c: Dane wyjściowe: T / N istnieje algorytm O (n c ) dla SAT.

podobnie rozdzielczość rozstrzygalności tego języka jest prawie równoważna problemowi P vs NP . jednak w tym przypadku mniej oczywisty jest przypadek „prostego” kodu problemu.

vzn
źródło
1
Czy downvoter wyjaśniłby, co jest nie tak z tą odpowiedzią?
MaiaVictor,
2
Twój „podwójny główny” język jest rozstrzygalny. Jeśli jest ich tylko skończona liczba , odpowiedź brzmi „Tak” dla i „Nie”, w przeciwnym razie zawsze „Tak”. Jasne, że nie wiem, , ale to nie ma znaczenia, A (bardzo prosty) Turing odpowie. Podobnie jak język „ostatniego twierdzenia Fermata”, czy istnieją liczby całkowite takie, że dla ? ”, Ostatnio„ dowiedzieliśmy się, że to , Wilesa ” dowód nie zmienił języka . n N N a , b , c a n + b n = c n n N = 2NnNNa,b,can+bn=cnnN=2
vonbrand
3
Nie jestem zwycięzcą, ale wszystkie twierdzenia w tej odpowiedzi są błędne. Wszystkie trzy z tych problemów są możliwe do rozstrzygnięcia (bez konieczności przyjmowania niepotwierdzonych założeń). Dlatego dokładnie przestudiuj odpowiedź Raphaela.
DW
ok, może wejście musi mieć określoną TM, a algorytm decyduje, czy TM obliczy problem. muszę o tym więcej pomyśleć ... pomyśleć, że istnieje prosty przepis na tego typu problemy, w zasadzie łączący otwarte problemy z niezdecydowanymi językami ... ale zgodzili się, że rzadko jest to udokumentowane / sformułowane w referencjach CS ... znalazłem tylko kilka rozproszonych referencje ... a może dane wejściowe są dowodem, a język weryfikuje, czy dowód jest poprawny ... inne wysoko głosowane odpowiedzi wspominają nieparzyste liczby idealne, problem z collatzem itp ... programy nie są w stanie zatrzymać lub nie dla określonych stałych .
vzn
przepraszam za zamieszanie! w niektórych dalszych stwierdzeniach twierdzenia są poprawne w formie, w której opisują proste programy, o których nie wiadomo, że kończą się (dla wszystkich danych wejściowych) (tj. pierwotne pytanie), a niepowodzenie ogólnego pomysłu nakreślonego / wskazanego przez DW próbuje przekonwertować każdy z nich na nierozstrzygalne języki. będzie nadal rozważał ten drugi pomysł budowy, szukając takiego, który się powiedzie. innym sposobem spojrzenia na to jest to, że problemy mogą być postrzegane jako pojedyncze instancje / dane wejściowe dla rozwiązania problemu zatrzymania, ale nie są tak naprawdę (jak wiadomo) równoważne z samym problemem zatrzymania.
vzn
0

Napisz prosty program, który sprawdza, czy dla każdego n, sekwencja Collatz zaczynająca się od n osiągnie liczbę 1 w mniej niż miliard iteracjach. Gdy ma odpowiedź, pozwól programowi zatrzymać się, jeśli odpowiedź brzmi „Tak”, i niech zapętla się na zawsze, jeśli odpowiedź brzmi „Nie”.1n1050

Nie możemy stwierdzić, czy ten program się zakończy, czy nie. (Kim jesteśmy? Powiedzmy, że „my” to każdy, kto mógłby dodać komentarz do mojej odpowiedzi). Jednak ktoś z niewiarygodnie wydajnym komputerem może to powiedzieć. Pewien genialny matematyk może to powiedzieć. Może być raczej mała n, powiedzmy n ≈ gdzie potrzebny jest miliard iteracji; byłby w zasięgu osoby o dużej determinacji, dużo czasu i pieniędzy. Ale w tej chwili nie możemy powiedzieć.1020

gnasher729
źródło