|
Feb. 18th, 2007|04:51 pm |
Эта задача не решается.
http://www.springerlink.com/content/g117578246437364/
The undecidability of the spatialized prisoner's dilemma
Patrick Grim, Theory and Decision 42 (1997), no. 1, 53--80.
Abstract In the spatialized Prisoner''s Dilemma, players
compete against their immediate neighbors and adopt a
neighbor''s strategy should it prove locally
superior. Fields of strategies evolve in the manner of
cellular automata (Nowak and May, 1993; Mar and St. Denis,
1993a,b; Grim 1995, 1996). Often a question arises as to
what the eventual outcome of an initial spatial
configuration of strategies will be: Will a single
strategy prove triumphant in the sense of progressively
conquering more and more territory without opposition, or
will an equilibrium of some small number of strategies
emerge? Here it is shown, for finite configurations of
Prisoner''s Dilemma strategies embedded in a given
infinite background, that such questions are formally
undecidable: there is no algorithm or effective procedure
which, given a specification of a finite configuration,
will in all cases tell us whether that configuration will
or will not result in progressive conquest by a single
strategy when embedded in the given field. The proof
introduces undecidability into decision theory in three
steps: by (1) outlining a class of abstract machines with
familiar undecidability results, by (2) modelling these
machines within a particular family of cellular automata,
carrying over undecidability results for these, and
finally by (3) showing that spatial configurations of
Prisoner''s Dilemma strategies will take the form of such
cellular automata. |
|