# Decidable predicates

I'm trying to see whether

i) The predicate "$x$ is a multiple of $y$" decidable? If it is, then how can we give a program which computes the characteristic function.

So, for above, I can show it is computable by the following:

$qt(y,x)$ = quotient when $x$ is divided by $y$. Since $qt(y,x+1) = qt(y,x) + 1$ if $rm(y,x) + 1 = x$

and $qt(y,x+1) = qt(y,x)$ if $rm(y,x) +1$ $\ne x$.

We have the following definition by recursion from computable functions:

$qt(0,0) = 0$

$qt(y,x+1) = qt(y,x) + sg(|x-(rm(y,x)+1)|)$

but I need help in translating it to a program. I am not sure if the step of writing it as a computable function is a first good attempt

ii) Do you think "$x$ is prime" is decidable?

-

We are talking natural numbers, and for simplicity we'll ignore the case where $x$ or $y$ is zero as waste cases to be dealt with separately.

Then $x$ is a multiple of $y$ just in case, for some $k \leq x$, $x = ky$. The obvious program structure to test whether this is so, for input $x$ and $y$ is,

for $k = 1$ to $x$,

compute $ky$

if $ky = x$ print "yes" and exit

else loop

print "no".

And there you are!

And yes it is decidable whether $x$ is prime (by deciding whether it is a multiple of any smaller number, other than 1).

-
Darn. Your answer appeared while I was writing mine. You have the prior claim, so I'll delete mine if you wish. –  Rick Decker Jan 23 '13 at 22:07
While this is good pseudocode, the question is in reference to notation following from this link such as problem #1 in people.math.carleton.ca/~ckfong/cut13.pdf. Your answer doesn't contain registers, nor something like J( , , ) and Z() nor S(). Can you please format it accordance with the notation of Cutland's computability? –  mary Jan 23 '13 at 22:28
@RickDecker Good heavens no need to delete! Overlap often happens here, and two slightly different takes on the same approach can be illuminating! –  Peter Smith Jan 23 '13 at 23:43
@mary Do you know how to implement "for" loops on a register machine? –  Peter Smith Jan 23 '13 at 23:45
I don't but we need to use only syntax of S(), J(), T() –  mary Jan 24 '13 at 3:07

Unless you're required to find the characteristic function, Peter's solution is perfectly fine. He's written a decider for you:

M(y, x) =
for k = 1 to x
if k * y = x
return true
return false


As he says, here's a predicate for "$x$ is prime" (assuming x is positive):

Prime(x) =
if x = 1
return false
else
for k = 2 to x - 1
if M(k, x)
return false
return true


Sure, it's inefficient, but a decider doesn't have to be efficient, only correct.

-