检查函数是否可计算

Question

我得到了以下用伪代码编写的函数：

P:

{ 

int x, y, z;
read (x, y, z); 
while (x != y) {
   x = x - y;
   z = z + y
}; 
write z; 

}

鉴于f(x,y,z)是P计算的函数，我想知道函数“g(x,y,z)=1 if f(x,y,z)不是全函数还是g(x,y,z)=0否则"，是可计算的。

我的第一个猜测是：是的，它是可计算的（例如 x=y）。

是否有更严格的通用方法来证明这一点？

Answer 1

P 不会改变 y 的值，它改变 x 值的唯一方法是从 x 中减去 y，直到 x = y。如果从 x 中减去 y 最终没有得到 x = y，那么循环将永远继续下去。我们知道，如果初始 x = cy 对于自然数 c >= 1，则重复从 x 中减去 y 只会导致 x = y。因此，g(x,y,z) = 1 因为 f(x,y,z) 不是总功能；当 x != cy 对于任何自然数 c >= 1 时，它是未定义的。即使你的意思是 g(x,y,z) = 1 只要定义了 f(x,y,z)，它仍然是可计算的，因为 g(x,y,z) 是函数：

g(x,y,z) = { 1, if x = cy for some natural number c >= 1 }
           { 0, otherwise                                }

某些自然数 c >= 1 的条件 x = cy 本身是可计算的，因为这等同于 "x >= y" 和 "GCD(x, y) = y".

检查函数是否可计算

Checking whether a function is computable or not

computation-theory