补充资料：算法的等价性

算法的等价性
algorithms, equivalence of

　　算法的等价性【日g喊‘Ins，呵‘初~of;助呷盯Mo.3姗H.即e.TI.oeT‘] 联系一定类型的算法的二元关系(binary relation)，这种二元关系表示以下事实:当送人同样类型的输入时两个由此种关系联系的算法产生同样的结果(也可能产生关于执行此计算的附带信息—所谓计算的历史(history of 00r压putation)).下面给出这种关系的几个典型例子. a)考虑所有可能的溥归撑术(reCUrsive schemes)，即定义n元部分递归函数的等式系.定义函数切和妙的两个模式称为函攀等价的(funCtionally equivalen‘)，若对任意自然数x、，…，x。，条件等式 毋(x，，…，xn)二《xl，…，x。)为真(若两边同时有意义，且当有意义时给出相同的值，这时认为是真的).S.C.Kleene咧如见[l])证明了，对于任意在递归模式上处处有定义的可计算算子级都可以找到一模式S使得哭(S)和S是函数等价的(所谓不动卓牢浮(fixed一poin‘theorem”.特别地，它的推论有，在一定条件下，即当存在模式S，和52，使得Sl有此性质而S:无此性质时，递归模式的关于函数等价性不变的任何性质的不可解性的y改曰邢跳益一Rice定理.由此定理可得函数等价性的关系本身的不可解性. b)考虑一给定字母表A上的正规算.法(n ormalal即rithm)，两个这种算法级和见称为关于A是等价的(e quivalent)，若对A上任意字下述条件满足:如果这两个算法中的一个把字尸转换到同一字母表A上的字Q，那么另一个算法也把尸转换到Q(见[2]).这两个算法称为关于A宇拿等妙的(completely eqnivalen‘)，若对A上任意P条件等式吸(尸)二’升(P)为真这两个关系都是不可解的 口考虑算汀的逻辑模式(乡1、。模式(Yan()、、ch-cmes)见13]卜这种模式的实现是在它由头到尾的执行中包含的算户序列.两个模式称为等价的(equlvalent)，若它们的实现集相重.知。B模式的算价关系被证明是可解的，而且付它已构造出等价变换的完全系(见{31[4]). 算法等价关系的详细研究对于只能用算法等价变换先进技术完成的一些当前迫切的任务(特别在程序设计模式理论中)具有很大的重要性.这些问题包括由-种语言到另一种语言的算法的翻译及其最优化(为了改进它们的“_L作特征”的翻译).这方面特别引起注意的是，能够找到使等价变换完全系在应用中方便的算法等价性可解关系(见【5])13]中略述的概念在很大程度L决定算法等价性研究的一般方法，
　　

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