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? 
 A: 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).
A: 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.
