可计算函数

任何可计算函数都可以使用 while 循环（即，“当某事为真时，执行其他操作”）并入程序中。For 循环（具有固定的迭代限制）是 while 循环的特例，因此可计算函数也可以使用 for 循环和 while 循环的组合进行编码。阿克曼函数是一个良定义全函数的最简单示例，该函数是可计算的但不是原始递归的，这为 1900 年代早期认为每个可计算函数也是原始递归函数的观点提供了一个反例 (Dötzel 1991)。