From: daryl@oracorp.com (Daryl McCullough)
Subject: Re: A rock implements every FSA
Organization: ORA Corporation
Date: Wed, 8 Apr 1992 03:09:22 GMT

orourke@unix1.cs.umass.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.

The definition I gave for functional equivalence is not vaccuous,
though, since it does allow us to distinguish between different
nondeterministic systems. For example, consider two nondeterministic
with the same external behavior:

    System A randomly picks a number between 0 and 255 and outputs
    a binary representation of it, one bit at a time.

    System B repeats 8 times: randomly output either 0 or 1.

Both of these systems nondeterministically output 8 bits, but there is
a difference in strategy: A decides at the beginning which 8-bit
number to output, while B makes the bits up as it goes along. There is
no way to map states of B to states of A and preserve the transition
relation,and so they are not functionally equivalent, although they
are behaviorally equivalent.

This example shows that functional equivalence, as I have defined it,
is not a vaccuous relation, and that it is indeed different from
behavioral equivalence, but only for nondeterministic systems. It
doesn't help to distinguish between different deterministic systems
(or systems with no outputs) with the same behavior.

> 	Perhaps the definition would more accord with intuition
> if the state-mappings were between Turing Machines with tapes?
> For a realistic map-checker program, if written as a TM, would repeatedly 
> return to some of its states, with only the contents of memory different
> (e.g., by incrementing various loop counters and so on), whereas
> the single-state-cross-time would never return to old states.
> The definition of functional equivalence would also need to demand a
> mapping between tapes.

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.
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. For
example, in an electronic computer, if you are looking at the level of
the programming language, then the program structure itself looks like
a controller, while external files might look like memory. At the leve
of machine language, the controller is determined by the hardware chip
(CPU), and the program is simply initial data loaded into memory. Even
for Turing machines, the separation is not very clear; you can always
shift functionality from the controller to the tape data or
vice-versa. A universal Turing machine has most of the functionality
in its input tape, while a finite state automaton (which is
essentially a Turing machine that never backs up on its tape) has all
the functionality in the controller. I think that the division between
controller and memory is mostly an arbitrary modelling decision.

The second problem that I have with this proposal is that for the
brain, neurons serve both as tape and as controller, so the
distinction doesn't seem appropriate for modeling the brain. The third
problem is that a realistic physical system will never be in the exact
same state twice, and so the distinctions that you are talking about
wouldn't make much difference.

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.

Daryl McCullough
ORA Corp.
Ithaca, NY


Newsgroups: comp.ai.philosophy