Apa artinya fungsi dapat dihitung?

Meskipun secara informal suatu fungsi dapat dihitung jika nilainya dapat dihitung, Alan Turing, Alonzo Church, dan Kurt Godel masing-masing memiliki definisi formal dari computablility, yaitu Turing Machines, Lambda Calculus, dan fungsi rekursif umum. Ketika ditunjukkan dalam tesis Church-Turing bahwa ketiga formulasi ini setara, menjadi lebih jelas bahwa mereka dapat digunakan sebagai definisi formal dari computability.