Darren New <dne### [at] sanrrcom> wrote:
> Warp wrote:
> >   An algorithm which solves the halting problem would prove (or disprove)
> > the Goldbach's conjecture with its answer

> FWIW, Rice's Theorem basically say *any* property that some but not all 
> functions have can be turned into the halting problem. So if there's 
> anything non-trivial you want to find out about what a function computes, 
> it's just as impossible to compute as the halting problem is.

  One interesting thing about the example I mentioned is that the program
in question is quite short. I'm sure you could write the program in 2 or 3
lines of Haskell (of course it has to assume integers of unlimited size and
an unlimited amount of RAM). Yet proving whether this extremely short program
will ever terminate has puzzled top mathematicians for over 250 years.

-- 
                                                          - Warp

Post a reply to this message