Обчислювана функція, одне з основних понять теорії алгоритмів. Функція f називається обчислюваною, якщо існує алгоритм, що переробляє всякий об'єкт х , для якого визначена функція f, в об'єкт f ( x ) і не застосовний ні до якого x , для якого f не визначена. Приклади: х — натуральне число, f ( x ) = х 2 ; x — пара раціональних чисел x 1 і x 2 , f ( x ) = x 1 : x 2 (ця функція визначена лише для тих x , в яких x 2 ¹0); X — пара матриць X 1 і X 2 з цілочисельними елементами, f ( X ) = X 1 X 2 (ця функція визначена лише для тих X , в яких число стоблцов в X 1 збігається з числом рядків в X 2 ). Аргументами і значеннями Ст ф. можуть бути лише так звані конструктивні об'єкти (див. Конструктивний напрям в математиці) (бо лише з такими об'єктами можуть оперувати алгоритми); таким чином, функція f така, що f ( x ) º х не є обчислюваною, якщо її розглядати на всій дійсній прямій, але є обчислюваною, якщо її розглядати як функцію натурального або раціонального аргументу. Ст ф., областю визначення якої служить натуральний ряд, називається обчислюваною послідовністю.
