[Math] about Goldbach conjecture

algorithmsgoldbachs-conjecture

About Goldbach conjecture, (that Every even integer greater than 2 can be expressed as the sum of two primes) and if algorithms exist to solve the Halting Problem, then algorithm that determine Goldbach conjecture is true or false is exist? please explain

Best Answer

Although there is not algorithm that can solve the halting problem, it is still meaningful to talk about an imaginary computer that has some procedure that decides whether a given program halts or not, called an oracle for the halting problem.

If we had an oracle for the halting problem, then we could immediately verify the truth of the Goldbach conjecture (as well as many others). Heres how:

Consider the following program:

  1. Let $n=2$.
  2. Increase $n$ by $2$
  3. Check to see if $n$ can be written as a sum of two primes (we can do this just by checking all of the (finitely many) primes less than n.
  4. If we could write $n$ as a sum of two primes, go back to step $2$. Otherwise, stop.

The only way for this program to halt is if, at some time during step $4$, we cannot write $n$ as a sum of two primes. Since $n$ is always even and at least $4$, then, the program halts only if the Goldbach conjecture is false. Since, furthermore, $n$ will run through all even integers greater than or equal to $4$ if the program does not halt, the program also always halts if the Goldbach conjecture is false.

Now, we can take this program, and run our oracle for the halting problem on it.

If the Goldbach conjecture is true, the oracle will say that the program does not halt, and if the Goldbach conjecture is false, the oracle will say that the program will halt.

Therefore, if the halting problem were solvable, the Goldbach conjecture (and many other problems) would also be easily solvable.

Related Question