|
![](/i/fill.gif) |
On 10/10/2010 08:57 AM, Warp wrote:
> While this is not a proof of anything, it's however, a marvelously simple
> example of why solving the halting problem is extremely difficult:
>
> "A program that goes through all even numbers and checks if one of them
> is a counter-example to the Goldbach's conjecture. The program terminates
> when it finds the first such number."
>
> An algorithm which solves the halting problem would prove (or disprove)
> the Goldbach's conjecture with its answer (if the answer is "it never
> halts", then it proves the conjecture, while the answer "it halts"
> disproves it, and this disproval would be valid even if it couldn't give
> the counter-example).
>
> How could an algorithm resolve whether that program will ever halt or not?
> Top mathematicians have struggled with that problem for over 250 years, to
> no avail. A program which solves the halting problem for any given program
> would make proving basically *all* mathematical problems trivial.
>
> While, as said, this is not a proof that it's not possible, it gives a good
> idea why it would be a tremendously difficult problem to solve.
My favourite one is determining whether a point belongs to the
Mandelbrot set. The program to do this is about 3 lines long. Depending
on which point you choose to investigate, the program will either loop
forever (indicating that the point belongs to the M set) or halt after
finite iterations (indicating that the point belongs to the complement
of M).
The trouble is, the most celebrated single property of the M set is that
it's absurdly complicated.
When I was a teenager, I used to think that maybe instead of blindly
iterating the equations, you could use the geometric properties of the
set to figure out the answer faster. But now I realise that since the
geometric forms repeat to infinity as well, there are still points which
would be just as slow to categorise that way.
In fact I've seen how there are different ways of representing real
numbers (ratios, continued fractions, radicals, etc.), and for almost
every one, there are some real numbers that do not have a finite
representation. It seems reasonable that no matter what algorithm you
use for determining membership of M, there will still be cases requiring
infinity iterations.
No matter which way round you look at it, it's just not solvable in
finite time, *every* time.
And this is just one of the possible computer programs you could write.
We haven't even considered any of the more complicated generalised sets
one might contemplate. An algorithm that knows the special properties of
every single set mathematically definable so that they can all be
resolved in finite time? I double it...
Post a reply to this message
|
![](/i/fill.gif) |