Hacker News Reader

Comment by lifeformed | Hacker News Reader

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?

View on HN

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.

I find your code hilarious in that, if it ever terminates, it doesn't print the two primes.

A true mathematician; nadam only cares that a solution exists.

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

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.

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?

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.

Since you don't have a real Turing machine, why would you care? Your computer is not Turing machine.

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!

#2 isn't any more non-terminating than "for (i=0; i < 100; i++)" is.

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

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

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

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.

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.

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

Reply on news.ycombinator.com