From: clarke@acme.ucf.edu (Thomas Clarke)
Newsgroups: comp.ai.philosophy
Subject: Re: A rock implements every FSA
Date: 15 Apr 92 14:01:28 GMT
Article-I.D.: cs.1992Apr15.140128.7755
Organization: IST, University of Central Florida, Orlando

In article <1992Apr14.153609.8539@mp.cs.niu.edu> rickert@mp.cs.niu.edu (Neil Rickert) writes:
>In article <1992Apr12.120115.1221@oracorp.com> daryl@oracorp.com (Daryl McCullough) writes:
>
>>I agree with you. As a matter of fact, in the the theory of processes,
>>as developed by Robin Milner, quite a bit is done with a notion of
>>"functional equivalence", and it is a theorem that any two processes
>>that are (1) deterministic, and (2) behaviorally equivalent, are also
>>functionally equivalent.
>
>  This claim seems quite preposterous.
>
>  Consider the following two methods of computing the GCD of two non-negative
>integers.  For each process, the observed behavior is to read two numbers,
>then after a brief delay print the GCD.
>
>  Method 1:
>
>	This is the usual Euclidean algorithm.
>
>	while (b > 0)
>	{
>		r := remainder on dividing a by b;
>		a := b;
>		b := r;
>	}
>
>	output a;
>
>
> Method 2:
>
>	if (b == 0  ) { output a; exit; }
>	m = 1;
>	while (a is even and b is even)
>	{
>		shift a and b left one bit;
>		shift m right one bit;
>	}
>
>	loop
>	{
>		if (a == 0  ) { output m*b; exit; }
>		if (b == 0  ) { output m*a; exit; }
>		while (a is even) shift a left one bit;
>		while (b is even) shift b left one bit;
>
>		if (b < a)
>			a := a - b;
>		else
>			b := b - a;
>	}
>
>   ---------------------------
>
>   Both methods compute the GCD.  Both take times at worst proportional to
>the log of the largest argument.  It is easy to add idle cycles in each
>iteration to keep the times of both processes identical.  [Roughly speaking,
>add idle cycles so each step takes a time equal to
>
>	K * (log (largest on input) - log (largest on output) )
>
>for some suitable K].
>
>  With method 1, given inputs 24 and 15, after the first few cycles it will
>find itself following the exact sequence of states you would get with
>inputs 15 and 9.  With method 2 and inputs 24 and 15 it will soon start
>following the same sequence of states as with inputs 12 and 3.
>
>  Method 1 essentially goes through the same functional states you would need
>to compute the continued fraction representation of a/b.  Method 2 doesn't.
>
>  How can these possibly be functionally equivalent?
>
>-- 
>=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
>  Neil W. Rickert, Computer Science               <rickert@cs.niu.edu>
>  Northern Illinois Univ.
>  DeKalb, IL 60115                                   +1-815-753-6940

Functionalism has the ring of a word of art, but the dictionary definition of
functional is "3.performing or able to perform a regular function"
The two algorithms above both perform the same fucntion.  Hence they are functionally equivalent, in English anyway.

Original Putnam and functionalists apparently interpreted "functionalism" to
mean that states equivalent to a Turing computation could be found in the brain.
In light of neural discoveries etc, this is hard to defend, and the new 
Putnam is at pains to show how it leads to behaviorism.

The broader (English) definition of functionalism - the FA implemnents a
given input output system - is transparently equivalent to behaiorism -
the FA implements a given behavior.

Some of the net debate thus seems to involve two definitions of the word
"functionalism".  Reminds me of arguments about how to functionally
specify the procurement of a computer system.  

Excuse any garbage in above.  Our nifty GUI news poster is down and I'm
not real used to rn and vi.

D
functional is "3. perfro
C
C
C