补充资料：算法问题

算法问题
algorithmic problem

　　算法问题回g威.面cp叻lem;~plfTM.，ecKa，Ilpo吞月eMa」 寻找一个(唯一的)方法(算法(al即rithm”以解决同一类型的无穷多个单个问题系列的问题.历史上在各个数学分支中都曾提出并解决了算法问题.但是某些算法问题长期未能解决.其原因只是在20世纪30年代在数理逻辑中给出了算法的精确定义后才弄明白.并且发现了不可解的算法问题，即根本不存在所要求的算法.结果使数学家关于算法的观念有了彻底的变化，新的算法问题开始陈述为对给定类型的无穷多个问题系列的解的算法的存在性问题且当算法存在时找出此算法问题的解. 几个比较精确的算法定义在算法论(al即rithms，theoryof)中几乎同时出现且它们被证明本质上都是等价的.在每个这种定义中给出了特定算法的充分广泛的类，它们关于算法的组合的自然运算是封闭的.每个关于某算法问题不可解的命题是一个对所考虑的算法问题借助于给定的算法类是不可解的、在数学上有严格证明的定理.在这种形式下这些定理可以看成是特定的，即关于给定算法类的.但是，所有这些结果都可以用数学家所理解的直观算法概念来表示.这种“翻译”是建立在所谓的Church论题(Church thesis)(依给定算法的确切表述方法的不同也可称为Turing论题(Turing thesis)或正规化原理(normalizationPrindPle))之上的，这个论题断言，所考虑的这类算法是通用的，即任何直观算法可以计算的函数可以用这类算法中的某个来计算.这个论题是由数学的历史所肯定的科学事实一切数学上已知的算法都符合这论题，而想在上述范围之外找到算法的所有企图都遭到了失败.最后，这论题也由于各种严格定义的算法类的等价性而被肯定.Church论题不能被证明，因为它所涉及的是在数学上模糊的直观算法概念，但这论题对于数学又是非常重要的，因为它使得有可能来谈论数学家理解的一般意义的算法问题的不可解性. 最早的不可解算法问题的例子是在算法论本身里被指出的.它们包括自然数的给定非递归集元素归属性的判定间题，通用Turing机的停机问题，正规算法(n~alal即rithm)可自应用的判定问题等等. 关于在算法论本身之外的算法问题，首先应该指出的是，1936年Church首先证明一阶谓词演算有效公式的判定问题的不可能性.在模型论(model thco-ry)里许多算法问题是这类问题.模型论是20世纪30年代由A 1.Mal’tsev和A.Tarski创立的，它用谓词演算处理非空集和在它们上面定义的关系.模型论中许多算法问题的表述和一些基本结果也要归功于他们.给定的模型类K的初等理论(elementary theory)是在K中的一切模型中为真的所有一阶谓词演算的闭公式集.类K可以只含个模型.一个初等理论T是可解

[1] [2] [3] [4]  下一页

说明：补充资料仅用于学习参考，请勿用于其它任何用途。