Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!security!genrad!decvax!harpo!seismo!hao!hplabs!sri-unix!warbob.rice@Rand-Relay
From: warbob.rice%Rand-Relay@sri-unix.UUCP
Newsgroups: net.ai
Subject: Halting Problem Discussion
Message-ID: <13222@sri-arpa.UUCP>
Date: Sat, 5-Nov-83 00:23:33 EST
Article-I.D.: sri-arpa.13222
Posted: Sat Nov  5 00:23:33 1983
Date-Received: Sun, 6-Nov-83 10:13:47 EST
Lines: 16

From:  Bob.Warfield <warbob.rice@Rand-Relay>

It turns out that any computer program running on a real piece of hardware
may be simulated by a deterministic finite automaton, since it only has a
finite (but very large) number of possible states. This is usually not a
productive observation to make, but it does present one solution to the
halting problem for real (i.e. finite) computing hardware. Simulate the
program in question as a DFA and look for loops. From this, one should
be able to tell what input to the DFA would produce an infinite loop,
and recognition of that input could be done by a smaller DFA (the old
one sans loops) that gets incorporated into the learning program. It
would run the DFA in parallel (or 1 step ahead?) and take action if a
dangerous situation appeared.

                                        Bob Warfield
                                        warbob@rice