From: orourke@sophia.smith.edu (Joseph O'Rourke)
Subject: Re: A rock implements every FSA
Organization: Smith College, Northampton, MA, US
Date: Fri, 10 Apr 1992 13:18:42 GMT

In article <1992Apr8.030922.29649@oracorp.com> 
	daryl@oracorp.com (Daryl McCullough) writes:

 >orourke@sophia.smith.edu (Joseph O'Rourke) writes:
 >
 >> To me the functional equivalence of the map-checker and the single-
 >> state machine shows that your definition of functional equivalence
 >> is flawed.
 >
 >That was my point, that functional equivalence doesn't work the way
 >that people want it to. It doesn't distinguish between systems that
 >(a) have no outputs, or (b) are deterministic, because in both these
 >cases, functional equivalence reduces to behavioral equivalence.

OK, that is clear.  I would only like to distinguish between
"functional equivalence naively defined" and some better definition
of functional equivalence, which I admit I haven't offered.

 >What I believe that you are suggesting is that we separate the
 >functionality of systems into two pieces: the memory (the tape), and
 >the controller (the Turing Machine proper), and you are demanding that
 >functional equivalence (in my sense) hold for each piece separately.

Yes, and I made this more precise in a later post, defining equivalence
in terms of fine-grained tape behavior, ignoring the state mappings.

 >This is a possible direction to go, but it seems unsatisfactory to me,
 >for several reasons.
 >
 >First, what you consider to be memory, and what you consider to be
 >controller often depends on the level you are looking at it. 

Your point is excellent, and shows that what I was attempting can
not succeed completely.  It seems clear to me now that even when 
comparing two Turing Machines, there is a continuum of possible
definitions of equivalence from coarse behavior to fine behavior:
comparing just input tape to output tape, or considering in addition
the intermediate tape values, or considering in addition the head 
movements, or considering in addition the state transitions.  Where
you draw the line between behaviorally-equivalent and functionally-
equivalent seems arbitrary.

 >In my opinion, the intuitive reason that a 5-color map checker program
 >and a one-state do-nothing program are "functionally different" is
 >that you could easily modify the map checker program to do something
 >useful (like coloring your maps for you), while there is no easy way
 >to do anything with the one-state program. Perhaps this intuition
 >could lead to some notion of functional equivalence that would include
 >some kind of "closeness" to related programs.

This is a nice idea.  I have thought about this some myself.  One
approach is to treat the behavior (coarse or fine as above) as
points in an infinite dimensional space (one point per input), so
that any particular TM is an infinite set of points in this space,
and then measure the distance between machines with the Hausdorff metric.
The other approach, as you suggest, is to measure the distance between
machines by the number of changes necessary to convert one into the
other.
	This is drifting rather far from the original topic, but it
has served to weaken my faith in functionalism.
Xref: sparky comp.ai.philosophy:4154 sci.philosophy.tech:2071