From: John K Clark (johnkclark@fastmail.fm)
Date: Tue Oct 13 2009 - 10:38:07 MDT
On Tue, 13 Oct 2009 "Robin Lee Powell"
> John: the problem you're talking about simply doesn't exist in real
> computers.
Like hell it doesn't! Why do you think programs unexpectedly hang?
Obviously if a computer has a finite memory it would be possible in
theory to keep a record of every state the machine goes into, and if you
found that a state was repeated then you'd know for sure that the
machine was in a infinite loop. But the trouble is that the machine
needed to do all that checking would have to be much larger than the
original machine, and that larger machine would have no way to know if
it was itself in a infinite loop unless it was watched over by an even
larger machine.
Before Turing nearly everybody assumed that a finite algorithm would be
found that cuts through all that recursive stuff and just tells you if a
program will send you into an infinite loop or not. What Turing found is
that such an algorithm does not exist, and the implications of his
discovery are vast.
John K Clark
--
John K Clark
johnkclark@fastmail.fm
--
http://www.fastmail.fm - Access all of your messages and folders
wherever you are
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:04 MDT