W tym sensie problem decyzyjny jest równoważny językowi formalnemu poprawnych rozwiązań.
Formalnie, problem decyzyjny to dowolny podzbiór A liczb naturalnych. Używając numeracji Gödla można sprowadzić do takiego zbioru dowolny język formalny. Problem decyzyjny jest rozstrzygalny albo obliczalny, jeśli A jest zbiorem rekurencyjnym. Problem jest częściowo obliczalny, jeśli A jest zbiorem rekurencyjnie przeliczalnym. Problem jest nierozstrzygalny, jeśli nie jest obliczalny.
Przykłady Klasycznym przykładem problemu rozstrzygalnego jest zbiór liczb pierwszych. Istnieje metoda sprawdzenia, czy dana liczba jest pierwsza przez sprawdzenie wszystkich jej potencjalnych dzielników. Choć istnieją znacznie efektywniejsze testy pierwszości, powyższa metoda wystarcza do pokazania, że jest to problem rozstrzygalny.
Jednym z najważniejszych przykładów problemu nierozstrzygalnego jest problem stopu.