🚀 go-pugleaf

Andy Walker:
   Consider, for example, an input consisting of the digits of pi, and
   consider the FSM that moves into state N on reading the digit "N".
   That will not terminate, and because pi is irrational it cannot
   "loop" either.

It's not a finite state machine either, because it has too many
states.  

   ...  but once you link up two FSMs with each able to read the
   output of the other, you get TM capability.

No, a turing machine has the ability to "create" a new FSM on the fly
(in state 0).  In fact, it has the ability to create an infinite
number of FSMs (given infinite time).

	   The trouble is that few "useful" programs work on FSMs.  FSMs
   cannot multiply arbitrary integers, cannot match brackets, etc.  

No, but they can multiply bounded integers, and they can match
brackets in bounded strings.  By placing the bounds conveniently high
they can be considered transparent for most applications.

   In real life they do these things quite well, purely because the
   real-life integers we want to multiply and the real-life programs
   whose brackets we want to match fit adequately into real-life
   computers.

Exactly.  In real life, the integers (and string lengths) are not
arbitrary.

By the way, a classic example of the problems involved in a solution
which takes infinite time is the following "algorithm" for a turing
machine:

 Find the first non-zero cell on a tape  by scanning left  till you hit
 a non-zero cell.  If this does not terminate,  scan right till you hit
 a non-zero cell.  The tape provided is arbitrary.

But the turing machine doesn't have a method for determining if a
given algorithm will terminate.  You could set up the TM to scan both
directions, and halt when it finds the first non-zero cell that's
close to the starting point, but you can't even use that result to run
the above algorithm (because you still wouldn't know if the tape on
the left had a non-zero cell).

*lecture off*

Raul Rockwell