Algorithm to determine if a number is perfect on a Turing Machine

Question

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.

Answer 1

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.