Ilekroć ludzie pytają o problem z zatrzymaniem, gdy chodzi o programowanie, ludzie odpowiadają: „Jeśli dodasz tylko jedną pętlę, masz program zatrzymujący i dlatego nie możesz zautomatyzowaćzadanie"

Ma sens. Jeśli twój program ma nieskończoną pętlę, to kiedy twój program jest uruchomiony, nie masz możliwości sprawdzenia, czy program nadal przetwarza dane wejściowe lub czy po prostu zapętla je w nieskończoność.

Ale niektóre z nich wydają się sprzeczne z intuicją. A co jeśli pisałem rozwiązanie problemu zatrzymania, które pobiera kod źródłowy jako jego wejście.rascher@localhost$ ./haltingSolver source.c

Jeśli mój kod (source.c) wygląda tak:

for (;;) {  /* infinite loop */  }

Wygląda na to, że mój program może to łatwo zobaczyć. „Spójrz na pętlę i spójrz na warunek. Jeśli warunek jest oparty tylko na literałach, a nie na zmiennych, to zawsze znasz wynik pętli. Jeśli istnieją zmienne (np. Podczas (x <10)), sprawdź, czy te zmienne są zawsze modyfikowane, a jeśli nie, zawsze znasz wynik pętli. ”

Oczywiście, te kontrole nie byłyby trywialne (obliczanie arytmetyki wskaźnika itp.), Ale nie wydaje się to niemożliwe. na przykład:

int x = 0
while (x < 10) {}

mógł zostać wykryty. wraz z - choć nie trywialnie:

int x = 0
while (x < 10)
{
   x++;
   if (x == 10)
   {
      x = 0
   }
}

A co z wprowadzaniem danych przez użytkownika? To jest kicker, co sprawia, że ​​program jest nieprzewidywalny.

int x = 0;
while (x < 10) 
{
   scanf("%d", &x); /* ignoring infinite scanf loop oddities */
}

Teraz mój program może powiedzieć: „Jeśli użytkownik wprowadzi wartość 10 lub większą, program zatrzyma się. Na wszystkich innych wejściach zapętli się ponownie”.

Co oznacza, że ​​nawet z setkami wejść, jednympowinien być w stanie wymienić warunki, na których program się zatrzyma. Rzeczywiście, kiedy piszę program, zawsze upewniam się, że ktoś ma możliwość go zakończyć! Nie twierdzę, że wynikająca z tego lista warunków jesttrywialny tworzyć, ale nie wydaje mi się to niemożliwe. Możesz wziąć dane od użytkownika, użyć ich do obliczenia indeksów wskaźników, itp. - ale to tylko zwiększa liczbę warunków, aby zapewnić zakończenie programu, nie uniemożliwia wyliczenia ich.

Czym właściwie jest problem zatrzymania? Czego nie rozumiem na temat idei, że nie możemy napisać problemu, aby wykryć nieskończone pętle? Albo dlaczego „pętle” są często cytowanym przykładem?

AKTUALIZACJA

Pozwólcie, że zmienię nieco pytanie: jaki jest problem zatrzymaniajak to dotyczy komputerów? A potem odpowiem na niektóre komentarze:

Wiele osób powiedziało, że program musi być w stanie poradzić sobie z „dowolnymi danymi wejściowymi”. Ale w komputerach nie ma żadnego arbitralnego wejścia. Jeśli wprowadzę tylko jeden bajt danych, to mam tylko 2 ^ 8 możliwych wejść. Na przykład:

int c = getchar()

switch (c) {
   case 'q':
      /* quit the program */
}

Nagle po prostu rozliczyłem wszystkie możliwości. Jeślic ma wzór bitowy 0x71, robi jedną rzecz. Dla wszystkich innych wzorów robi coś innego. Nawet program, który akceptuje arbitralne dane wejściowe, nigdy nie jest tak naprawdę „arbitralny”, ponieważ zasoby są skończone, co oznacza, że ​​chociaż stosuje się teorię „arbitralnej” ... nie jest to dokładnie jedna z jedną z praktyką.

Inne przytoczone przykłady to:

while (n != 1)
    if (n & 1 == 1) 
        n = 3 * n + 1;
    else 
        n /= 2;

Jeśli n jest 32-bitową liczbą całkowitą ... to mogę ci wizualnie powiedzieć, czy to się zatrzyma.

Wydaje mi się, że ta edycja niczego nie pyta, ale najbardziej przekonującym przykładem, jaki widziałem, jestten:

Załóżmy, że masz swój magiczny program / metodę, aby ustalić, czy program zatrzymuje się.

public bool DeterminesHalt(string filename, string[] args){
    //runs whatever program you tell it do, passing any args
    //returns true if the program halts, false if it doesn't
}

Teraz powiedzmy, że piszemy mały fragment kodu, taki jak ...

public static void Main(string[] args){
    string filename = Console.ReadLine(); //read in file to run from user
    if(DeterminesHalt(filename, args))
        for(;;);
    else
        return;
}

W tym przykładzie możemy napisać program, który zrobi dokładnie odwrotność naszej magicznej metody zatrzymania. Jeśli w jakiś sposób ustalimy, że dany program się zatrzyma, wskakujemy do nieskończonej pętli; w przeciwnym razie, jeśli ustalimy, że program znajduje się w nieskończonej pętli, kończymy program.

Z drugiej strony, jeśli celowo napiszesz program, który zawiera nieskończoną pętlę ... „rozwiązanie problemu zatrzymania” jest trochę dyskusyjne, prawda?