ماذا يعنى ان الدالة قابلة للحساب؟
بالرغم من انه بشكل غير رسمي الوظيفة قابلة للحساب اذا كان من الممكن حساب قيمها، إلا ان كل من آلان تورينج، ألونزو تشيرش، وكورت غوديل كان لديه تعاريف رسمية للقابلية الحسابية، وهي آلات تورينج، وحساب لامدا، والوظائف التكرارية العامة. لما تبين في أطروحة تشيرش-تورينج ان هذه الصيغ الثلاث متساوية، اصبح اكثر وضوحا انه يمكن استخدامها كعرف رسمي للقدرة على الحساب.