计算机汇编语言教程:任意两个一般递归函数是否等价，是一个可判定的问题吗？

来源：百度文库编辑：杭州交通信息网时间：2024/04/26 06:19:28

两个一般递归函数的表达式可能并不相同，例如：
F1(a,n)=n==1?f(n):F1(F1(a,n-1),1)
F2(a,n)=n==1?f(n):F2(F2(a,1),n-1)
虽然F1和F2的表达式并不一样，但它们对相同的输入能产生相同的输出，所以是等价的。
是否存在一个通用的算法能判断任意两个一般递归函数是等价的。
希望您能给出一个证明，就像证明停机问题是不可判定的哪样。
当然，两个递归函数的表达式是已知的。

首先，这个问题有点不够准确，如果所给的递归函数的计算过程不停机，那么这就是不可判定的问题，因为图灵机停机问题是不可判定的，而一般递归函数的计算能力与图灵机是等价的。所以，应该把这个问题修正为：
“两个停机的递归函数是否等价是不是可判定的。”
而这个问题可能是不可判定的。类似的有一个不可判定的问题就是判断任意两个lamda表达式是否等价是不可判定的问题。

今天突然想到一个非形式化证明方法，可以解决这个问题，请大家一起点评一下：
证明：
由于一般递归函数与图灵机在计算能力上是等价的。因此，判定程序也是一个一般递归函数，称为判定函数。
假定存在一个判定函数P能判断任意两个一般递归函数f1和f2是否等价。
P(f1,f2)=1，若f1与f2等价
P(f1,f2)=0，若f1与f2不等价
重新定义一个新的一般递归函数P1：
P1(f1,f2)=(f1=P∧f2=P1)?0:P(f1,f2)
现在讨论P(P,P1)的值
若P(P,P1)=1，则P1与P等价，但P1(P,P1)=0，与P和P1等价性矛盾。
若P(P,P1)=0，则P1与P不等价。但根据P1的定义，当f1=P∧f2=P1=false时P1=P；当f1=P∧f2=P1=true时P1=P=0，因此对于任意输入(f1,f2)P1的值都与P相同，P与P1是等价的，也得到矛盾。
结论：不存在能判断任意两个一般递归函数等价性的一般递归函数，由于一般递归函数与图灵机程序是等价的，故不存在能判断任意两个一般递归函数等价性的程序。“任意两个一般递归函数等价性”是不可判定的。
证毕。

任意两个一般递归函数是否等价，是一个可判定的问题吗？编写一个调用递归函数的程序，求出两个自然数m和n的最小公倍数。编写一个调用递归函数的程序，求出两个自然数m和m的最大公约数。分别用函数递归和非递归的方法求出两个整数的最大公约数。分别用函数递归和非递归的方法求两个整数的最大公约数。输入任意三个整数，判断其中是否有两个奇数一个整数，是输出yes不是no 求证：任意函数都可表示成一个奇函数和一个偶函数的和写一个判素数的函数,在主函数输入一个整数,输出是否素数的信息写一个判素数的函数,在主函数输入一个整数,输出是否素书的信息用C 语言写出一个判素数的函数，在主函数输入一个整数，输出是否素数的信息