Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!elroy.jpl.nasa.gov!ncar!noao!arizona!gudeman
From: gudeman@cs.arizona.edu (David Gudeman)
Newsgroups: comp.lang.misc
Subject: Re: Halting Problem Solved! Film at 11! (Was Re:
Message-ID: <3406@optima.cs.arizona.edu>
Date: 21 May 91 18:56:04 GMT
Sender: news@cs.arizona.edu
Lines: 48

In article  <ROCKWELL.91May19193927@socrates.umd.edu> Raul Rockwell writes:
]David Gudeman:
]   ...  There are very few applications where it is useful to
]   model a computer as a TM -- infinite or not.
]
]Except that each "cell" on a turing machine tape represents a FSM of
]arbitrary complexity...

This is rather opaque.  I can think of several functions to map a
turing machine with a fixed cell to a FSM.  None of them seem
particularly useful.

]So any FSM is a restricted case of a turing machine, and turing
]machines are trivially useful for anything that a FSM is useful for.

Not so.  If an FSM is useful for some purpose, then it would not
necessarily be useful to use a TM (with the added complications) for
the same thing.  It is not useful to build a TM to recognize a regular
expression.

For that matter, I can't think of any application where it is useful
to model a computer as an FSM.  If you are interested in machine
limits, then it seems simpler to begin with a nonfinite machine model.
For example, if you want to answer the question "For what inputs will
this program exceed the machine paramaters?" then the easiest thing to
do is to derive a function of the needed machine resources in terms of
the input (assuming arbitrary resources).  If you were really using an
FSM model then the effect of the resources limits would be pervasive,
making the work much harder.

]The way I understand it, the only kind of machine with an infinite
]state space that can't be modeled by a TM is one with non-denumerable
]state state space.

That depends on what you what you want to model.  If you are only
interested in whether a set can be generated, then this is true.  But
if you are interested in how many operations you need to generate a
given set, then your statement is false.

Besides, just because you _can_ do something a certain way doesn't
mean that is a good way to do it.  It would be silly to define
programming language semantics in terms of a TM.  The Lambda calculus,
the predicate calculus, or a specialized state transition system is
far easier to use.
--
					David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudeman