Що означає, що функція є обчислювальною?
Хоча неформально функція обчислюється, якщо її значення можна обчислити, Алан Тюрінг, Алонзо Церква і Курт Годель мали формальні визначення обчислюваності, а саме Машини Тюрінг, Ламбда-калькулятор і загальні рекурсивні функції. Коли в тезі Церкви-Тюрінга було показано, що ці три формулювання є еквівалентними, стало зрозуміло, що вони можуть бути використані як формальне визначення обчислюваності.