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