News for hackers. Stuff that matters.
Re:Rent-a-coder hilarity (2008) by lifeformed on Monday May 06, 2013 @02:25AM (#5661145)
What would happen if you went through with it? I bet it wouldn't be too hard to write a program that does it for 90% of cases. Is there a simple case that would be impossible to determine?
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.

Re:Rent-a-coder hilarity (2008) by rcfox on Monday May 06, 2013 @02:44AM (#5661177)
Off the top of my head:

1) Assuming rand(x,y) gives a uniform distribution between x and y:

    for (int a = 0; a < INT_MAX; a += rand(-1,1));
2) I can't find the source any more, but someone basically implemented a big int library with bit twiddling to allow for an upper bound on a loop that would finish after the heat-death of the universe, assuming generous CPU specs. Not infinite, but also non-terminating.

3) Anything that makes a system call. You might never get scheduled again!

Re:Rent-a-coder hilarity (2008) by dagw on Monday May 06, 2013 @08:20AM (#5661925)
As to 1) any rand() implementation that doesn't use an external source of randomness is deterministic and cyclical, thus it is quite possible to determine if 1) halts by analyzing rand()
Re:Rent-a-coder hilarity (2008) by StavrosK on Monday May 06, 2013 @07:47AM (#5661846)
#2 isn't any more non-terminating than "for (i=0; i < 100; i++)" is.
Re:Rent-a-coder hilarity (2008) by kens on Monday May 06, 2013 @02:53AM (#5661200)
A simple example that is hard to determine if it halts is to iterate through a,b,c,n and see if a^n+b^n=c^n. I.e. solve Fermat's last theorem by brute force. (I won't spell out the iteration details.) If your software could determine if this halts or not, it would prove Fermat's last theorem. (Obviously since FLT has been proven, this particular case is known not to halt.)
Re:Rent-a-coder hilarity (2008) by Luyt on Monday May 06, 2013 @04:23AM (#5661389)
Interesting read:

"The proof itself is over 100 pages long and consumed seven yearsof Wiles's research time. For solving Fermat's Last Theorem, he was knighted, and received other honors."

http://en.wikipedia.org/wiki/Wiles%27s_proof_of_Fermat%27s_L...

Re:Rent-a-coder hilarity (2008) by nijk on Monday May 06, 2013 @05:03PM (#5664767)
There is a paper online that proves fermat's last theorem in this way, by exploiting the C compiler's ability to optimize away non-terminating code that has no observable state changes.
Re:Rent-a-coder hilarity (2008) by eru on Monday May 06, 2013 @02:33AM (#5661159)
Oh, the halting problem is easy enough to solve for most cases (people do it informally all the time), just not for the worst cases.

For giving a percentage, you need to specify a distribution of programmes first. E.g. programmes created reading from /dev/random, or programmes downloaded at random from the internet, or something more sensible.

Re:Rent-a-coder hilarity (2008) by zura on Monday May 06, 2013 @02:37AM (#5661169)
Exactly. The first reason to reply to this kind of request would be to engage with the uneducated client, and make sure that she will pay for that 90%.