Zgodnie z hipotezą Churcha–Turinga funkcjami obliczalnymi są te funkcje, które mogą zostać obliczone przez urządzenie maszynowe dysponujące nieograniczonym czasem i pamięcią. Hipoteza ta zakłada, że każda funkcja dająca się wyrazić za pomocą algorytmu jest obliczalna.
Aksjomaty Bluma pozwalają zdefiniować teorię złożoności obliczeniowej na zbiorze funkcji obliczalnych. W jej ramach problem określenia złożoności funkcji obliczalnej rozpatruje się jako zagadnienie funkcji.
Definicja Istnieje wiele równoważnych sposobów określenia klasy funkcji obliczalnych. Są to częściowe funkcje na liczbach naturalnych, które można obliczyć za pomocą maszyny Turinga. Równoważne modele obliczalności, wyznaczające tę samą klasę funkcji, obejmują m.in.:
funkcje μ-rekurencyjne, maszyny Turinga, maszyny von Neumanna, maszyny znakujące, rachunek lambda, programy GOTO, programy WHILE.
Każda obliczalna funkcja ma skończoną liczbę argumentów będących liczbami naturalnymi. Funkcje te mogą być częściowe, tzn. nie muszą być określone dla wszystkich argumentów. Jeżeli funkcja jest określona dla danego argumentu, jej wartością jest pojedyncza liczba naturalna. Funkcje takie nazywa się również funkcjami częściowo rekurencyjnymi.