www.piclist.com/techref/index.htm?key=halting+problem

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

Sean

On Sat, Feb 7, 2009 at 11:40 PM, Vitaliy <spam_OUTspam@spam@EraseMEmaksimov.org> wrote:

>

> Is the halting problem really so hard to explain, that one needs to buy a

> 777 page book?

>

> Vitaliy

>

> -

In reply to: <1A25A26CF7034666A4D900C915FC2B31@ws11>

See also: www.piclist.com/techref/index.htm?key=halting+problem