作业帮任意两个一般递归函数是否等价,是一个可判定的问题吗?两个一般递归函数的表达式可能并不相同,例如：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的表达式并不一样,但它
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/06 01:01:48
任意两个一般递归函数是否等价,是一个可判定的问题吗?两个一般递归函数的表达式可能并不相同,例如：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的表达式并不一样,但它
任意两个一般递归函数是否等价,是一个可判定的问题吗?
两个一般递归函数的表达式可能并不相同,例如：
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的表达式并不一样,但它们对相同的输入能产生相同的输出,所以是等价的.
是否存在一个通用的算法能判断任意两个一般递归函数是等价的.
希望您能给出一个证明,就像证明停机问题是不可判定的哪样.
当然，两个递归函数的表达式是已知的。
任意两个一般递归函数是否等价,是一个可判定的问题吗?两个一般递归函数的表达式可能并不相同,例如：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是等价的,也得到矛盾.
结论：不存在能判断任意两个一般递归函数等价性的一般递归函数,由于一般递归函数与图灵机程序是等价的,故不存在能判断任意两个一般递归函数等价性的程序.“任意两个一般递归函数等价性”是不可判定的.
证毕.