🚀 go-pugleaf

David Gudeman:
   By the way, the term "Turing machine" refers to a specific
   architecture, and does not describe all machines with infinite
   state spaces.  ...  A Turing machine has an infinite read-write
   tape with a movable head and only four possible actions (as I
   recall).  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.  The "four actions" of a TM are:

(1) do a state transition in the FSM
(2) move to the FSM on the left
(3) move to the FSM on the right
(4) "halt" or "suspend" (transition to an undefined state)

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.

Often when people speak of turing machines, they think of one where
every FSM has only two states, and numbers are implemented as strings
of ones.  This particular instance of a turing machine is quite a bit
more limited than turing machines in general.

And while the basic definition of a turing machine only has rules for
a transition to an adjacent FSM you can usually make transitions to
FSMs located arbitrary distances away (as long as the states of the
intervening FSMs are known).  Note that you don't have to enumerate
the states and transitions, as long as each FSM is finite.

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.

Raul Rockwell

In article <3354@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes:
>In article  <1991May19.024820.25262@sbcs.sunysb.edu> Joseph Allen writes:
>]From: yodaiken@chelm.cs.umass.edu (victor yodaiken)
>]>[A finite TM is translatable into a FSM.  A FSM has a state space S and a
>]>mapping S -> S.  To see if it halts, pick a starting state, run through the
>]>sequences.  If if goes on the halt state then it halts.  If it ever touches a
>]>state which already occured, it doesn't.  Since there is only a finite number
>]>of states, it takes a finite amount of time to decide (since at most it has
>]>to go through all the states)]

>What machine is going to do this?  If computers are FSM's then you
>only have an FSM to do this, and I can always find a program too big
>to analysis in this way.

I agree, none (plus it would much much too slow- the number of states in real
computers is huge).  The 64K question is can it be done symbolically on the
language source code.  I believe the answer is sometimes.  If you don't have
malloc and you don't have other forms of bignums then it might even be
practicle.  Maybe.  It would be usefull because you could tell at compile time
if you're going to overflow or go past array bounds or run out of stack space.
At any rate, the halting problem proof should not be justification to not at
least research this.  I originally thought that it was because I misunderstood
the halting problem and its scope.

If you're programming in an idealized lisp-like environment, then I guess the
problem starts to approach the actuall halting problem.

>By the way, how do you know that the TM is finite in the first place?

Well it's not as defined, but real computers are.  And more importantly, many
times the "functions" or whater the modularity structure in the language in
question is is.

This is not to say that the halting problem is not usefull- it is, but for
fundamental questions of discrete algorithms in idealized environments.  

>By the way, the term "Turing machine" refers to a specific
>architecture, and does not describe all machines with infinite state
>spaces.  (PDAs are infinite-state devices that can't even recognize
>the recursive sets.)  A Turing machine has an infinite read-write tape
>with a movable head and only four possible actions (as I recall).
>There are very few applications where it is useful to model a computer
>as a TM -- infinite or not.

TMs are used because they can represent any machine with a finite or infinite
(but not continuum) state space (including PDAs).  It's not pretty to
represent real computers on TMs, but it can be done, and that's the point.  

Similarly, a FSM as a classification means much more than an EPROM and a
latch.
-- 
/*  jallen@ic.sunysb.edu  */     /* Amazing */     /* Joe Allen 129.49.12.74 */
int a[1817];main(z,p,q,r){for(p=80;q+p-80;p-=2*a[p])for(z=9;z--;)q=3&(r=time(0)
+r*57)/7,q=q?q-1?q-2?1-p%79?-1:0:p%79-77?1:0:p<1659?79:0:p>158?-79:0,q?!a[p+q*2
]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n"," #"[!a[q-1]]);}

In article <1991May25.135757.6912@sbcs.sunysb.edu> jallen@eeserv1.ic.sunysb.edu (Joseph Allen) writes:
> [...]  The 64K question is can it be done symbolically on the
>language source code.  I believe the answer is sometimes.  If you don't have
>malloc and you don't have other forms of bignums then it might even be
>practicle.  Maybe.  It would be usefull because you could tell at compile time
>if you're going to overflow or go past array bounds or run out of stack space.

Bignums and malloc are important in the theoretical sense in which they
were brought up in this thread, but eliminating their consideration doesn't
help all that much in practice.

>At any rate, the halting problem proof should not be justification to not at
>least research this.

It gets researched all the time, the halting problem notwithstanding. It
is quite frequent to see papers that discuss heuristics, or actually more
often ones that assume certain simplifications that allow some progress
to be made, but which make the algorithm in question useless for general
application because of the difficulty/impossibility of proving that
the assumption holds for any particular real-world case.

If you actually try to design an analyzer that e.g. tries to predict whether
an array index will ever go out of bound (as good an example as any), you
almost always end up modeling behavior which is highly input-data-dependent,
dependent on the results of other function calls (whether they were called
or how often and what they computed), etc. In short you get a model which
represents significant chunks of the original program, with very few
possible simplifications, and hence can't make much progress.

A great deal of the work on this subject comes up under the heading "symbolic
execution", and it *is* useful, just not as much as you would like to hope.
Another related area is "the aliasing problem", which refers to the
problem of figuring out when/whether two names (or pointers, depending
on the language/problem being analyzed) refer to the same memory cell(s).
It turns out that a lot hangs on this, and an awful lot of people would
be very happy if some general solution to this could be found. Unfortunately
in most forms it maps to the halting problem, or impractical simplifying
assumptions need to be made.

So although it is generally thought to be hopeless in the completely
general case, people do tackle subsets, and some people hope that eventually
some significantly powerful subset of the problem may prove tractable.
But still, the halting problem says that you'll never get a hundred percent
solution.

Oh, btw: another interesting related problem is that there is no
"normalized form" for algorithms in any of the universal models of computation
developed thus far. I.e. you can express, say, a shell sort in any of
numerous different ways, and within broad limits, no single one of those
forms can be called "the base case"/"the natural form"/"the simplest form".
This means that even so simple a concept as trying to compare two algorithms
for functional equality is intractable. In number theory, positive numbers
have a unique factorization, and this makes a lot of things very tractable.
But most other things (e.g. general two- and multi- dimensional polynomials)
have no unique factorization. They can be factored several different ways.
And that significantly complicates things. Same thing with algorithms.

So if you discovered a universal model of computation that *did* have
a unique factorization, then that would be a breakthrough. Much would
become possible within that system. Only problem is that it would necessarily
be intractable or impossible to automatically translate algorithms from
other systems into that one, which probably means that it would be very
difficult to prove that it really was a universal model of computation.
	Doug
-- 
Doug Merritt	doug@netcom.com		apple!netcom!doug

>>]>[A finite TM is translatable into a FSM.

Consider an input tape with a left end marker '<' and right end marker '>'.
Between the markers are the symbols '(' and ')'.

The following Markov machine terminates with 'Y' if the '()' are semi-Dyck,
'N' if not.

	<	->	[p
	p(	->	(p
	(p)	->	p
	[p>	->	Y

	[p)	->	q
	q(	->	q
	q)	->	q
	q>	->	N

	(r>	->	r
	(r	->	r
	)r	->	r
	[r	->	N

This has a fixed number of rules. For any input string of length n, it uses
finite space O(n) and finite time O(n).

>>]>[A finite TM is translatable into a FSM.

This is finite and TM-equivalent. Please translate into a FSM for any legal
input string.
-- 
In compliance with DoC,            Steven Ryan
this posting is devoid             2400 Geng Road, Palo Alto, CA
of all information.                ...!{apple|pyramid}!clipper!wyrmham!smryan
fxxx!                              A new xxxx for xxxxxxx  xxxxxxxxxx.

In article <1991Jun3.210908.17574@clipper.ingr.com> smryan@clipper.ingr.com (Steven Ryan) writes:
>>>]>[A finite TM is translatable into a FSM.
>
>Consider an input tape with a left end marker '<' and right end marker '>'.
>Between the markers are the symbols '(' and ')'.
>
> ...
>
>This has a fixed number of rules. For any input string of length n, it uses
>finite space O(n) and finite time O(n).
>
>This is finite and TM-equivalent. Please translate into a FSM for any legal
>input string.
>-- 
>In compliance with DoC,            Steven Ryan
>this posting is devoid             2400 Geng Road, Palo Alto, CA
>of all information.                ...!{apple|pyramid}!clipper!wyrmham!smryan
>fxxx!                              A new xxxx for xxxxxxx  xxxxxxxxxx.

Quite true. A TM in which the size of the tape is limited to the size of the
input is a Linear Bounded Automaton(LBA). A LBA accepts Context Sensitive Languages (CSL).
The set of CSLs is a strict superset of the set of Context Free Languages.

The difference between a FSM and a TM with a finite tape is that the FSM has a fixed
finite amount of "memory" while the amount of "memory" available to the TM with a finite
tape must necessarily grow as the length of the input grows (i.e. the tape must be at
least large enough to hold the input string).

The only way (that I am aware of) to restict the power of a TM to that of a FSM is to
not allow the TM to write to the tape.