The Halting Problem (was: YALF (yet another lint foulup))

[Mark A Terribile]

> | ...  Never returning is a hard property to check in C.
 
> |Try "uncomputable."
> 
> But is this equivalent to the halting problem? ...  Real computers are
> finite state machines ... Does the halting problem hold for FSAs?

Consider a machine with 64K of 8-bit memory.  (By today's standards, that's
hardly large enough for a ``hello, world'', especially if you are using
a window package.)  You have 2 ** 16 words of memory or 2 ** 19 bits.  The
number of states that your machine can reach is 2 ** ( 2 ** 19 ) or about
2 ** 5E5 or about 10 ** 2E5 (within 40%).

A machine with a cycle time of 1 attosecond could, in the limit, mimimally
visit all those states in only 10 000 or so seconds.  But that's not enough,
because you have to examine all possible sequences through all of those states.
Now you are talking about ( 10 ** 2E5 )! , which is getting rather large.

Now make that a 1 Meg machine.  You have now got 2 ** 23 bits, or about
2 ** ( 10 ** 7 ) states ...

For all practical purposes, the problem of exhaustively verifying all
sequences through such state sets for whatever input is uncomputable.
-- 

(This man's opinions are his own.)
>From mole-end				Mark Terribile