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

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?

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

Jest znane , w celu zatrzymania do na poziomie co najmniej , ale na ogół jest to problemem otwartym.$n$$5 × 2^{60} ≈ 5.764 × 10^{18}$

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.

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 $P$$P$$P$

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:

• Jak można rozstrzygać, czy ma pewną sekwencję cyfr?$\pi$
• Moc obliczeniowa człowieka: czy ludzie mogą rozwiązać problem zatrzymania na maszynach Turinga?
• Algorytm rozwiązywania „problemu zatrzymania” Turinga
• Synteza programu, rozstrzygalność i problem zatrzymania
• Czy można rozwiązać problem zatrzymania, jeśli masz ograniczony lub przewidywalny wkład?
• Dlaczego sumy funkcji nie są policzalne?

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$

$\qquad\displaystyle g(n) = \begin{cases}1, &S \text{ true},\\ g(n+1), &\text{else}.\end{cases}$

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

1. Niekoniecznie wszystkie , ale w pewnym sensie „wielu”. Przynajmniej nieskończenie wiele.

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  

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.

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.

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”.$1 ≤ n ≤ 10^{50}$

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ć.$10^{20}$