"Jesteśmy skazani na śmierć"

Na mocy tezy Churcha-Turinga każdy komputer jest równoważny maszynie Turinga. Każdy algorytm rozwiązujący problem ma dolne ograniczenie pamięciowe i dolne ograniczenie złożoności (czasami n-krotnie wykładnicze dla żadnego n:(). Dla rozstrzygalnych problemów długość taśmy użyta do rozwiązania jest zawsze skończona i rozwiązanie zawsze zajmuje skończoną ilość kroków (czasem zabraknie protonów we Wszechświecie i nanosekund od Wielkiego Wybuchu by rozwiązać:(). Komputery automatami skończonymi nie są bo rozwiązują problemy, które żaden automat skończony rozwiązać nie może (istnieje równoważność między automatami skończonymi a gramatykami regularnymi).

Co do praktyczności problemu stopu. Jest to bardzo bardzo bardzo praktyczny problem. Wszyscy uczestniczący w przedsięwzięciach budowy systemów oprogramowania byli by bardzo zadowoleni bardzo zadowoleni bardzo zadowoleni. Niestety problem jest nierozstrzygalny:(

Co do ograniczoności języka to każdy jest opisany w ograniczony sposób.

Jeśli chodzi proste algorytmy to udowodnij, że dla każdej liczby naturalnej L poniższy algorytm jest poprawny. To znaczy zatrzymuje się i daje poprawną odpowiedź (to drugie nietrudno udowodnić):
dopóki ( L jest różne od 1 )
{
jeśli ( L jest parzyste ) L = L / 2;
w przeciwnym wypadku L = 3 * L + 1;
}
Powodzenia;)