Вычисли́мые фу́нкции[1] — множество функций то есть отображения множества натуральных чисел во множество натуральных чисел, в математических обозначениях это которые могут быть реализованы некоторым, алгоритмом, описание которого конечно, например, описанием переходов некоторой машиной Тьюринга.
Функции называют алгоритмически разрешимыми или алгоритмически неразрешимыми, в зависимости от того, возможен ли некоторый теоретический алгоритм, вычисляющий эту функцию за конечное время.
В упрощённом виде в качестве множества обычно рассматривается множество — множество слов в двоичном алфавите . Это не снижает общности рассмотрения функций с точки зрения разрешимости, если результатом вычисления может быть не только некоторое слово, но и специальное значение — «неопределённость», соответствующее случаю, когда алгоритм вычисления аргумента функции на некотором множестве аргументов «зависает» — то есть никогда не выдает результат. Таким образом, можно дать следующее определение вычислимой функции :
где , а — специальный элемент, означающий неопределённость.
Роль множества может играть множество натуральных чисел, к которому добавлен элемент , и тогда вычислимые функции — это некоторое подмножество натуральнозначных функций натурального аргумента.