News for hackers. Stuff that matters.
Re:Rent-a-coder hilarity (2008) by nadam on Monday May 06, 2013 @03:09AM (#5661231)
Yes, there is a small program, for which you could be one of the most famous mathematicians if you could tell whether it terminates or not:

i = 4; while(there exists such p and q that prime(p) and prime(q) and p+q == i)) i+=2;

keyword: Goldbach conjecture. The Goldbach conjecture states that this program will never halt. No one could prove this yet; seems to be really hard.

Re:Rent-a-coder hilarity (2008) by StavrosK on Monday May 06, 2013 @07:43AM (#5661839)
I find your code hilarious in that, if it ever terminates, it doesn't print the two primes.
Re:Rent-a-coder hilarity (2008) by pi18n on Monday May 06, 2013 @11:37AM (#5662913)
A true mathematician; nadam only cares that a solution exists.
Re:Rent-a-coder hilarity (2008) by lifeformed on Monday May 06, 2013 @03:13PM (#5664154)
But if you were to code out such a program it would have to still have an upper bound for the size of the numbers you are testing. My implementation would look like this:

  int i = 4;
  bool sumFound = true;
  while(sumFound)
  {
    sumFound = false;
    for(int p = 0; p < MAX_INT && !sumFound; p++)
    {
      if (isPrime(p))
      {
        for (int q = 0; q < MAX_INT && !sumFound; q++)
        {
          if (isPrime(q))
          {
            if (p + q == i)
            {
              i += 2;
              sumFound = true;
            }	
          }
        }
      }
    }
  }
You could use big integers, but it'd still be bound by whatever the max size is for that. This program would eventually terminate. Could you write an implementation where the limitations of the system don't get in the way of the theoretical mathematical limitation? I guess you could build some system which can accommodate arbitrarily large numbers, but even that would be limited by the computer specs.

I guess what I'm saying is, isn't the implementation of the program the test in itself?

Re:Rent-a-coder hilarity (2008) by nadam on Monday May 06, 2013 @03:54PM (#5664376)
The program must run on the Turing machine. The Turing machine has an infinite tape, so it is able to represent arbitraily large numbers on its tape. It is a different question that a real Turing machine cannot be built in the known physical universe which contains only a finite number of atoms.
Re:Rent-a-coder hilarity (2008) by nijk on Monday May 06, 2013 @05:00PM (#5664747)
Since you don't have a real Turing machine, why would you care? Your computer is not Turing machine.
Re:Rent-a-coder hilarity (2008) by tomjen3 on Monday May 06, 2013 @11:48AM (#5662964)
That program doesn't run forever, you didn't declare that there what had to exist for the (just there exist) and prime isn't declared (is prime? highest prime which is a factor in the argument?).
Re:Rent-a-coder hilarity (2008) by nadam on Monday May 06, 2013 @04:02PM (#5664433)
The Goldbach conjecture is this:

"Every even integer greater than 2 can be expressed as the sum of two primes."

My program is simply constructed in such a way that it terminates if and only if the Goldbach conjecture is not true. Maybe my pseudocode is not very precise (and also english is not my mother language), but given the Goldbach conjecture anyone can construct the program more precisely if needed.