人工智能通识-科普-图灵机之可计算性
欢迎关注我的专栏( つ•̀ω•́)つ【人工智能通识】
所有数学问题都可以用计算机来解决吗？
如上一篇繁忙的海狸Busy beaver中所展示的，海狸是否会陷入无法停机的无限循环？这个看似简单的数学问题就无法完全用计算机来彻底解决，或者说它是不可计算的。
可计算性Computability/Calculability
可计算性是指某个数学问题是否可以用计算机在有限步骤内彻底解决。
首先必须是数学问题，而不能是给我做个汉堡包这种需要真实的实体变化的问题。
其次必须是有限步骤，如果这个问题的算法远远超过计算机目前可能拥有的计算能力，那么也应该视为不可计算的。
研究问题的可计算性质可以避免浪费时间在无底的坑里面做无意挣扎。
关于问题
可计算性是针对问题而言的，问题又主要是以下两类：
- 判定问题Decision Problem。判定问题就是回答是或否的问题。一个典型的决策问题是：大数据集U及其子集S，元素u属于大数据集U，判断u是否属于子集S。比如自然数中的n是否属于质数，这就是一个判定问题，当然我们可以采用试除算法来判定
不可判定就是已经确定无法对这种问题进行正确回答，要么答不对，要么陷入死循环永远答不出。比如繁忙海狸中的停机问题就是一个不可判定问题。
- 功能问题Function Problem。功能问题比判定问题更复杂，不能只回答是或否，可能需要回答一个数字，比如关于一个自然数的因数个数，或者地图导航到某地最近路线是哪条，这种问题的答案就需要一个数字或一条路径才行。
另外还有搜索问题Search Problem(在对象Y中是否能够找到符合要求的结构x)和最优化问题Optimization Problem(多个解决方案中哪一个更优）。
计算模型Model of computation
图灵机是一种抽象的计算模型，理论上可以实现无限多种算法，类似的计算模型（功能模型Functional models）还有以下几个，他们都被认为是图灵等价或图灵完整Turing completeness的：
- λ演算Lambda calculus，λ-calculus。阿隆佐·邱奇Alonzo Church在20世纪20~30年代发明。
- 组合逻辑Combinatory logic。摩西·施菲克尔Moses Schönfinkel和哈斯克尔库里Haskell Curry在20世纪20~30年代发明。
- μ-递归函数μ-recursive functions。μ音miu。最早在1934年由哥德尔提出。1967年，马文闵斯基指出μ-递归函数与图灵机等价。
- 寄存器机Register machine。由马文闵斯基和其他几位科学家几乎同时在1961年发明。
可计算理论
如上所示，递归理论起源于20世纪30年代，由库尔特·哥德尔KurtGödel，阿隆佐·邱奇Alonzo Church，罗莎·培特RózsaPéter，阿兰·图灵Alan Turing，斯蒂芬·克莱尼Stephen Kleene和埃米尔·珀斯特Emil Post等人提出。
早在1936年就邱奇和图灵就受到哥德尔的不完备性定理的启发，算法程序不可能正确的判断任意数学问题的真假。后来这个理论就被称为Church-Turing论文，定义了可计算概念的含义：可由算法计算的函数都是可计算函数。
可计算性的提出，也意味着科学家们对不可计算问题的认可，证明了数学中确实存在无法有效解决的问题。
此外还有描述可计算程度的相对可计算性Relative computability 和图灵度Turing degrees。
欢迎关注我的专栏( つ•̀ω•́)つ【人工智能通识】
每个人的智能新时代
如果您发现文章错误，请不吝留言指正；
如果您觉得有用，请点喜欢；
如果您觉得很有用，欢迎转载~
END
