Hi Vitaliy,

You asked me to explain the Halting problem in a manner which was more
understandable. Unfortunately, I do not understand it fully myself. I
did learn about it and how it is proven in a CS class once, but I do
not remember all the details. A quick look at the wiki article didn't
clear up all of my fogginess so I can't explain it for you.

However, I can tell you that it is NOT that complicated. The book
which you mention, I have not read, but I am pretty sure it is about
much more than just the Halting problem. The Halting problem and also
Goedel's Incompleteness Theorem are one of several really interesting
results in CS and math which put some limits on what computers can do.
They are not incredibly difficult to understand but are quite subtle
in exactly what they say. They often get used improperly in casual use
(for example, the Halting Problem does NOT say that one can never
write a computer program which determines whether other programs halt.
It just says that you cannot write one algorithm which can perform
this check on ALL possible programs over ALL possible inputs.)

Sean


On Sat, Feb 7, 2009 at 11:40 PM, Vitaliy <spam@maksimov.org> wrote:
>
> Is the halting problem really so hard to explain, that one needs to buy a
> 777 page book?
>
> Vitaliy
>
> --
> http://www.piclist.com PIC/SX FAQ & list archive
> View/change your membership options at
> http://mailman.mit.edu/mailman/listinfo/piclist
>
-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist