算法论

算法论   suàn fǎ lùn

亦称“能行性理论”。对一类问题(函数)的有穷地机械地判定(计算)过程称为对这类问题(函数)的算法。算法应满足如下要求:(1)只用有穷多条指令描绘算法,指令可以由人或机器机械地执行;(2)如果算法用于某初始材料上有结果,那么执行算法有穷步后会有结果;(3)如果算法用于某初始材料上没有结果,那么算法的执行过程永不停止,或得不出结果。算法论是描绘和处理上述直观算法的数学理论。迄今已建立了不少等价的理论,如递归论、图灵机和递归算法论。算法论用于其他数学分支后已解决了一些难题,如群论中字的等价性问题的不可判定性;希尔伯特第十问题的算法不可解性。此外在计算机科学中也有重要应用。