Dear Andreas and colleagues,
I thought that non-computability is particularly relevant to social
systems because the N of cases is part of the exponent. The
computational space then rapidly explodes.
For example, if one throws two dice there are 6^2 possibilities. If one
throws three dice, there are 6^3 possibilities, etc. In general: 6^N,
where N is the number of dice.
Analogously: If we have a group of 10 persons who can all maintain
relations with each other, this system has 10^10 possible states if each
configuration of relations is counted as one possible state. The
specification of mechanisms (hypotheses) selects on this phase space and
makes the system computable.
With kind regards,
Loet
_____
Loet Leydesdorff
Science & Technology Dynamics, University of Amsterdam
[log in to unmask] ; http://www.leydesdorff.net/
> -----Original Message-----
> From: News and discussion about computer simulation in the
> social sciences [mailto:[log in to unmask]] On Behalf Of
> Andreas Schamanek
> Sent: Sunday, April 06, 2003 12:31 AM
> To: [log in to unmask]
> Subject: computability ... Re: Bit-flipping model of culture
>
>
> 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
>
|