Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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).

share|cite|improve this answer
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 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
    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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.