Проверка, является ли функция вычислимой или нет

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 - вычитать y из x до x = y. Если вычитание y из x в конечном итоге не приводит к x = y, то l oop продолжается вечно. Мы знаем, что вычитание y из x несколько раз может вызвать x = y, только если первоначально x = cy для натуральных чисел c> = 1. Таким образом, 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                                }

Условие x = cy для некоторого натурального числа c> = 1 само вычислимо, поскольку это эквивалентно "x > = y "и" GCD (x, y) = y ".