任意两个一般递归函数是否等价,是一个可判定的问题吗?

来源：学生作业帮编辑：作业帮分类：综合作业时间：2024/11/06 08:08:11

任意两个一般递归函数是否等价,是一个可判定的问题吗?
两个一般递归函数的表达式可能并不相同,例如：
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是等价的,也得到矛盾.
结论：不存在能判断任意两个一般递归函数等价性的一般递归函数,由于一般递归函数与图灵机程序是等价的,故不存在能判断任意两个一般递归函数等价性的程序.“任意两个一般递归函数等价性”是不可判定的.
证毕.

写一个递归函数,判断输入的正整数是否是回文数（不使用数组）线性代数问题:两个矩阵相等和两个矩阵等价是一个意思吗? 编一个程序,用递归函数 gcd(a,b)实现求两个整数 a,b 最大公因子的欧几里德算法.输入任意整数a,b,调用递 e^-x -1 (e的-x次幂减1)的导数怎么求可导的数才有反函数吗? 否则怎么判定一个函数是否有反函数如何判定一个函数在一个区间内是否可导、连续存在原函数是否等价于可积,他们的区别在哪? C语言编写递归函数1.设计递归程序任意给定输入的一个小写英文字符串a1a2a3…an-1an (n≥5)输出：字符串A C语言利用递归函数解决一个数学问题用C语言写一个函数,判定任意给定的两维数组（100×100）中是否有相同元素. 怎么判定一个晶胞中的原子是否等价?举一个例子若两个矩阵的秩相等,那么它们等价吗?是否一个可逆另一个一定也可逆?为什么? 1.证明任意两个n*n非奇异矩阵行等价 2.奇异矩阵B可能行等价于非奇异矩阵A吗?