Searching \ for '[TECH] Halting problem' in subject line. ()
Help us get a faster server
FAQ page: www.piclist.com/techref/index.htm?key=halting+problem
Search entire site for: 'Halting problem'.

Exact match. Not showing close matches.
'[TECH] Halting problem'
2009\02\06@045731 by

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

On Fri, Feb 6, 2009 at 1:56 AM, Vitaliy <spammaksimov.org> wrote:
>
> 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.
>

Have you heard of Godel Escher Bach: An Eternal Golden Braid by
Hofstaeder?  An amazing book, and it covers the halting problem.
Simple, concrete, 777 pages long.
en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach
From: "Alex Harford" <harfordgmail.com>
>> 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.
>
> Have you heard of Godel Escher Bach: An Eternal Golden Braid by
> Hofstaeder?  An amazing book, and it covers the halting problem.
> Simple, concrete, 777 pages long.

Agreed, this is truly an amazing book. Highly recommended. I don't know if
I'd go so far as to say it is simple, but it is probably about as simple as
it could be to get across the ideas that it does.

-- Bob Ammerman
RAm Systems

On Feb 6, 2009, at 11:21 AM, Bob Ammerman wrote:

>> Simple, concrete, 777 pages long.

That is funny, in its own way...

Nate
Alex Harford wrote:
>> 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.
>>
>
> Have you heard of Godel Escher Bach: An Eternal Golden Braid by
> Hofstaeder?  An amazing book, and it covers the halting problem.
> Simple, concrete, 777 pages long.
> http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach

I looked it up on Amazon. I usually pay more attention to the critical
reviews, than the praises, and I read several reviews where apparently
intelligent people say the book is a total bore. Amazon's own review
criticizes the author for claiming that computers would never beat humans at
chess, and basing many of his analogies on vinyl records.

Is the halting problem really so hard to explain, that one needs to buy a
777 page book?

Vitaliy

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 <spammaksimov.org> wrote:
>
> Is the halting problem really so hard to explain, that one needs to buy a
> 777 page book?
>
> Vitaliy
>
> -
On Sat, Feb 7, 2009 at 8:40 PM, Vitaliy <spammaksimov.org> wrote:
> Alex Harford wrote:
>>
>> Have you heard of Godel Escher Bach: An Eternal Golden Braid by
>> Hofstaeder?  An amazing book, and it covers the halting problem.
>> Simple, concrete, 777 pages long.
>> http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach
>
> I looked it up on Amazon. I usually pay more attention to the critical
> reviews, than the praises, and I read several reviews where apparently
> intelligent people say the book is a total bore.

My guess is that people didn't enjoy the style that the book is
written in.  It is a mix of Socratic dialogue between various
characters (Crab, Tortiose) and 'textbook' style explanations.  I can
understand that some people wouldn't like this method, personally, I
enjoy it.  My wife, who can't make it through the first few pages of
Lord of The Rings, probably wouldn't enjoy it.

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

I apologize if my original email was unclear.  The subject of the book
is not the halting problem, but it is discussed.

Alex

More... (looser matching)
- Last day of these posts
- In 2009 , 2010 only
- Today
- New search...