Problem stopu

Problem stopu: dla danego algorytmu i danych wejściowych stwierdzić, czy program realizujący algorytm zatrzyma się. Na przykład

   x=xstart;
   do {
     if(x%2==0) x/=2;
     else x=3*x+1;}
   while(x!=1);

Dla wszystkich danych początkowych (xstart $\in N$) testowanych dotychczas, algorytm zatrzymywał się. Brak jednak dowodu, że zatrzyma się dla każdego xstart.

Inny przykład: rozważmy dyskretny sygnał $s$, określony w następujący sposób: $s(n)=1$ jeśli w rozwinięciu dziesiętnym liczby $\pi$ występuje sekwencja dokładnie $n$ kolejnych ósemek, $s(n)=0$ w przeciwnym razie. Ile wynosi np. $s(100)$?

Ogólnie problem stopu jest nierozstrzygalny.