From: J. Andrew Rogers (andrew@ceruleansystems.com)
Date: Fri May 21 2004 - 12:54:15 MDT
John K Clark wrote:
> I don’t know what you mean, I suppose you could have a machine that
> always gives up after a fixed amount of time, but such a device would
> hardly be “universal” and certainly doesn’t seem an appropriate
> architecture for a super brain. Alan Turing proved 70 years ago that
> sometimes you can’t even tell if you’re in a infinite loop or not.
I meant "universal" in the sense that all real computers are -- Finite
Turing Machines. UTMs are a mathematical amusement, and not relevant
here, particularly since even a "superbrain" probably won't have access
to one.
On a finite machine, it is quite possible to show that some specific
implementation will always halt. The Halting Problem is about *general*
solutions, not specific implementations. As I stated in my original
post, it is possible to have a computational model that is "universal"
but which can only approximate an infinite loop as a consequence of
being on a finite machine. Yes, if it was running on a genuine UTM the
Halting Problem would apply, but for finite machines you can prove that
it doesn't. In the pathological case it might return an approximation
to the correct answer when it runs out of space.
A finite machine that always halts has the caveat that while you will
always get some kind of answer, it will sometimes be an approximation of
the "correct" answer and sometimes not a very good approximation. But
that seems like a reasonable trade-off and an interesting way to exploit
finite state hardware.
j. andrew rogers
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:47 MDT