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