Jeżeli procedura zwraca wartość , to musi ona być poprawna.
Enderton wskazuje ponadto, że:
nie ma ograniczenia liczby argumentów funkcji, liczba kroków potrzebnych do uzyskania wyniku jest skończona, lecz nieograniczona z góry, nie zakłada się ograniczeń pamięci – w modelu dopuszcza się dowolnie dużą ilość zasobów.
Teoria złożoności bada funkcje obliczalne przy dodatkowych ograniczeniach dotyczących czasu lub pamięci.
Zbiory i relacje obliczalne Podzbiór zbioru liczb naturalnych nazywa się obliczalnym (rekurencyjnym, rozstrzygalnym), jeżeli istnieje funkcja obliczalna taka, że dla każdej liczby zachodzi:
, gdy , , gdy .
Zbiór jest obliczalnie przeliczalny (rekurencyjnie przeliczalny, półrozstrzygalny), jeżeli istnieje funkcja obliczalna taka, że jest określona wtedy i tylko wtedy, gdy . Innymi słowy, zbiór jest obliczalnie przeliczalny wtedy i tylko wtedy, gdy jest dziedziną pewnej funkcji obliczalnej.
Analogicznie definiuje się relacje obliczalne i relacje obliczalnie przeliczalne, utożsamiając relacje z odpowiednimi zbiorami skończonych ciągów liczb naturalnych.
Języki formalne
W teorii obliczalności rozważa się również języki formalne. Alfabet to dowolny zbiór symboli. Słowo nad alfabetem to skończony ciąg symboli z tego alfabetu.