Tracy R Reed wrote:
Darren New wrote:
Depends on which analog computer. Most are rather a lot smaller than a
Turing machine. Remember the halting problem only exists for
infinite-storage computers. Anything with a fixed number of states is
"trivial" to check whether it halts.
A modern digital computer has a fixed number of states but given the
definition of a program and a finite input is unable to tell you whether
that program will run forever or not.
I can tell you whether a program on (for example) a Z80 computer will
run forever fairly easily, assuming it's a self-contained system.
The Z80 has 2^16 bytes of address space (add the appropriate amount of
space for registers). That means the processor can only be in one of
8*2^16 different states (again, modulo register content, which is just
more memory, and ignoring external stuff like removable media,
interrupts, keyboards, etc).
Run the processor, making a complete copy of memory after every
instruction. Continue until you execute a halt instruction or until the
state of memory matches what you have already seen. In the former case,
the program halts. In the latter, it is in an infinite loop. Both cases
will be determined in finite time.
Trivial, except for the cost of storing (8*2^16)^(8*2^16) copies of the
memory, or so.
The reason you can't solve the halting problem on a Turing machine is
you don't have an upper limit on the number of states you have to
examine, since memory is unbounded.
> The last two sentences of the
above paragraph are false. Were they true it would imply that my
computer with a mere 4G of RAM is not an infinite-storage computer and
can therefore decide the halting problem.
No, it can't decide the halting problem due to being finite. It can be
the subject of the decision due to being finite.
It also has a fixed number of
states but checking whether a program halts is far from trivial.
It's quite trivial if the machine doing the checking has unbounded
amounts of memory.
Not sure where the halting problem comes in at all, actually.
The human brain can analyze a program and determine whether or not it
will ever halt.
The halting problem isn't that "there are no programs for which you can
decide whether it halts." The halting problem is "there are some
programs for which you cannot decide whether it halts." There are many,
many programs for which it is easy to determine whether the program
halts - all programs lacking indefinite loops, for example. The problem
is whether you can do this for *every* program, and no, the human brain
cannot look at *every* program and figure out whether it halts.
--
Darren New / San Diego, CA, USA (PST)
It's not feature creep if you put it
at the end and adjust the release date.
--
KPLUG-LPSG@kernel-panic.org
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
