Rozszerzeniem tego przykładu jest twierdzenie Rice’a, mówiące, że w ogólności każda nietrywialna własność podanego języka jest nierozstrzygalna.
Warto zauważyć, że język podany wyżej jest rekursywnie przeliczalny, ponieważ symulując działanie podanej maszyny na podanym wejściu dostaniemy w skończonym czasie odpowiedź dla każdego poprawnego wejścia. Można łatwo podać przykłady języków, które tego nie spełniają – przykładem jest język par dla których maszyna nie zatrzyma się na podanym wejściu.
Szersze modele obliczeń Istnieją modele obliczeń, które faktycznie rozszerzają maszyny Turinga, ale zwykle są uznawane za nierealizowalne w żadnym praktycznym sensie.
Nieskończone obliczenia Wyobraźmy sobie maszynę, której każdy kolejny krok wymaga o połowę mniej czasu niż poprzedni. Jeśli pierwszy krok wymaga jednej jednostki czasu, całe obliczenie trwa
W ciągu 2 jednostek czasu maszyna może wykonać nieskończoną liczbę kroków. Taka maszyna jest zdolna do rozwiązywania problemu stopu.
Maszyny z wyrocznią Wyobraźmy sobie że nasza maszyna ma dostęp do „wyroczni” która może odpowiadać na pytania dotyczące wyszczególnionych nierozstrzygalnych problemów.