Język to podzbiór zbioru wszystkich słów nad danym alfabetem.
Język jest obliczalny (rekurencyjny, rozstrzygalny), jeżeli istnieje funkcja obliczalna taka, że dla każdego słowa :
, gdy należy do języka, , gdy nie należy do języka.
Język jest obliczalnie przeliczalny (rekurencyjnie przeliczalny, półrozstrzygalny), jeżeli istnieje funkcja obliczalna taka, że jest określona wtedy i tylko wtedy, gdy należy do języka.
Przykłady Do funkcji obliczalnych należą m.in.:
każda funkcja o skończonej dziedzinie, każda funkcja stała, Dodawanie liczb naturalnych, funkcja wyznaczająca czynniki pierwsze liczby, Największy wspólny dzielnik, rozwiązania wynikające z tożsamości Bézouta oraz liniowe równania diofantyczne.
Jeżeli i są obliczalne, to obliczalne są również ich suma, iloczyn, złożenie (przy odpowiednich założeniach) oraz wiele innych operacji konstruowanych z użyciem operatora minimizacji.
Przykładem funkcji obliczalnej, dla której nie jest znany jawny algorytm, jest funkcja zależna od własności rozwinięcia dziesiętnego liczby (np.