X-Message-Number: 7999
Subject: Misc. computability theory and speculation
Date: Thu, 03 Apr 1997 12:55:53 -0500
From: "Perry E. Metzger" <>

> From: Mike Perry <>
>  
> I have made a confusing statement. A growing automaton 
> is not an FSM--but behaves like one over a finite interval
> of time.

ALL automata behave like Finite State Machines if you bound them in
time. A Turing Machine can only reach a finite number of slots on its
tape in a finite number of steps, you know.

The statement is therefore "nearly" tautological.

BTW, computer scientists tend to model large systems as TMs and not as
FSMs because although the systems are almost always in fact FSMs, the
analytic tools used for TMs are far more easily applied to the sort of
systems we typically use.

> (Finite sequences are always computable,

Nope. Not by a long shot. See Rice's theorem. Any non-trivial property
of an element of an R.E. language is non-computable. The answer to the
halting problem is a finite sequence. It is not, however, computable.

> Overall, it seems that reality 
> can be described as an interconnection of FSMs--in-
> finitely many of them. I would call this "digital"--so our
> existence could be described as digital, even if the FSM
> model only applies locally. 

Interconnected FSMs are simply FSMs.

> Thomas questions whether mathematics would be universal 
> to "advanced" aliens, and uses this to call into question my 
> idea of a universal language.

More interestingly, I question whether or not without any notion of
the semantics of a language it is possible for a remote and alien
civilization to reconstruct the semantics. In particular, it is fairly
easy to imagine sending a sequence that says "5 + 5 = 10" and get
across the notion of addition. Trying to get across enough symbols to
convey the notion 'this symbol in our code means a Cauchy Integral"
would be quite a challenge, however -- I can't conceive of how to
build up to it without a predefined shared "human" language. Trying to
establish the notions of most human languages like "please do X" or
what have you in a "universal" way is beyond me. I'm not saying it
can't be done, but the entire discussion seems extraordinarily
speculative.

> One trend in our own civilization is that mathematics is a 
> cumulative enterprise--branches once developed do not 
> lose relevance or interest over time,

I see you haven't been involved with many professional mathematics
types.

Lots of fields go "dead". Often they only had a couple of people
interested in the first place.

Perry

Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=7999