[FOM] telling whether a program terminates

Martin Davis martin at eipye.com
Tue Feb 10 13:38:40 EST 2004

Apostolos Syropoulos wrote:

<<Also, I believe it is worth noticing that there are many expert
computer programmers who can tell whether a ``simple'' program will
loop for ever or not...>>

As shown it the textbook "Computability, Complexity, and Languages" (of 
which I'm co-author), it is easy to write a "simple program" that will halt 
if and only if the Goldbach Conjecture is false. A slightly more 
complicated program will do the same for the Riemann Hypothesis.


More information about the FOM mailing list