piclist 2009\02\06\045731a >
Thread: Halting problem
www.piclist.com/techref/index.htm?key=halting+problem
flavicon
face BY : Vitaliy email (remove spam text)



Sean Breheny wrote:
> It is also true, though, that one can prove that certain vital aspects
> of a program cannot be proven true in general. For example, the
> halting problem:
>
> http://en.wikipedia.org/wiki/Halting_problem
>
> which says that for important classes of programs and possible inputs,
> it is not possible to create a general algorithm which shows whether
> they terminate or loop forever.


Sean, how would you explain this someone who admits that mathematics and
abstract thinking were never his forte? :)

I read about a similar theorem in college, where the problem was described
as "it is impossible to write a program that would prove the correctness of
another program". This was never covered in class, though.

I take these statements on faith, but I would love for someone to explain in
solid, concrete terms using simple, easy to understand examples the "why" of
it.

Vitaliy

<EBADB2CF45504FFE9E34B59ECAB8CE5E@ws11> 7bit

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