Hi SIMSOC,
On Tue, 1 Apr 2003, Alan Penn wrote:
> This brings a question to mind: are there any qualitative properties
> of systems that are provably _not_ representable in terms of bits?
>
> The theory of computation says that anything computable can be
> computed using a finite state machine (if I understand it right) so
> I suppose such properties - if they exist - must not be computable.
> If so what are they, and are they socially interesting?
From a social sciences' point of view (and quite some more), I'd
say that I do not like the notion of 'computability'. Is there a
property that is not represented in any way? Is there a property that
cannot be represented in some way? Every computation is some form of
representation (that we generally call model). It depends solely on
yourself (and your colleagues) whether a property is computable or
not.
Of course, the notion of 'representation' is also a representation.
But, that's a different story.
Another story, since we have already discussed lots of chaos theory,
here, goes like this: As most of you know, one of the properties of a
deterministic chaotic time series is the fact that values do not
repeat. No matter how often you iterate, e.g., the logistic equation
X(n+1) = 4 * X(n) * ( 1- X(n) ) ; X(0) out of [ 0 ... 1 ]
there will never be a value of X(n) that equals any other X(m) except
for m = n.
A computer is only a finite state machine. It can compute everything,
but only given enough time and enough finite states :) Our everyday
computers are _very_ finite state machines. So, if you compute the
logistic equation with a computer (using some computer language, say
FORTRAN or C), you will observe that already after only a few
iterations of the logistic equation you will get a X(n) that you have
seen before. Once you have found this X(n), say after p iterations,
every X(m+p) will equal X(m) for m = n, n+1, n+2, ... You have found a
cycle, a period of length p. (p, by the way, is astonishingly small:
often only a few thousand iterations if you declare/define X as a
single precision variable).
So, here is a property that is (generally) not computable:
Deterministic chaos.
Besides non-periodicity there is also the Lyapunov exponent which
shall be above 1 for chaotic time series. The Lyapunov exponent, by
the way, is a measure for how much or how fast 2 time series that
describe the same system will nevertheless diverge if computed with
slightly different values.
The strange part of this story is that when you compute the Lyapunov
exponent for a time series generated by a computation of the logistic
equation, i.e, a periodic time series, you still get values above 1.
Does that mean that when we look at computed non-computable properties
by means of computation that we see the world just like it is?
Sorry for this lengthy post.
Story-telling is my passion,
--
-- Andreas
|