0
$\begingroup$

I've been trying for a while now to find a solution for the problem in the title: determining if a number is perfect using a Turing Machine. I only had one class on the TM and while I did "get" how it works, this particular algorithm is being really hard for me to develop.

The algorithm I'm trying to implement on the TM is basically this (on C, returns true iff n is a perfect number):

int main(int n) {
  int i=1, sum=0;

  while ( n > i ) {
    if ( n % i == 0 ) {
      sum = sum + i;
    }
    i++;
  }

  return sum == n
}

The tough part for me right now is the while(n>i) loop and the n%i inside it.

Since I already have a program that does a%b, I was trying to build the TM graph around it, but I'm not sure it's the best idea, specially since the b on this case changes on every iteration. The software I'm using to simulate the TM is called JFlap.

The algorithm on table or graph form would be perfect.

$\endgroup$
  • $\begingroup$ This is not a real question. Where do your problems with the loop lie? What have you tried so far and where did you fail? $\endgroup$ – adrianN Apr 22 '13 at 9:16
  • $\begingroup$ If you have problems with translating your algorithm, why not try another? $\endgroup$ – Raphael Apr 22 '13 at 11:20
1
$\begingroup$

You need do do:

  • Factor the number given
  • Add up the factors, and check they add up to $n$

It should be something like:

sum = 0;
for(k = 1; k < n; k++) {
     if(n % k == 0)
         sum += k;
}
return sum == n;

To get n % k == 0 you can:

tmp = n;
while(tmp > 0)
    tmp -= k;
return tmp == 0;

Translating into TM-speak and splicing all this together isn't hard, just very tedious. Use a multitape TM to simplify your description.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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