piclist 2009\02\08\002134a >
Thread: Halting problem
face picon face BY : Sean Breheny email (remove spam text)

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.)


On Sat, Feb 7, 2009 at 11:40 PM, Vitaliy <.....spamspamRemoveMEmaksimov.org> wrote:
> Is the halting problem really so hard to explain, that one needs to buy a
> 777 page book?
> Vitaliy
> -
<e726f69f0902072121i26f37eedi24b58369b24f477b@mail.gmail.com> 7bit

In reply to: <1A25A26CF7034666A4D900C915FC2B31@ws11>
See also: www.piclist.com/techref/index.htm?key=halting+problem
Reply You must be a member of the piclist mailing list (not only a www.piclist.com member) to post to the piclist. This form requires JavaScript and a browser/email client that can handle form mailto: posts.
Subject (change) Halting problem

month overview.

new search...