Actions

Difference between revisions of "Randomness, Structure and Causality"

From Santa Fe Institute Events Wiki

Line 1: Line 1:
 
{{Randomness, Structure and Causality}}
 
{{Randomness, Structure and Causality}}
  
 
+
<head><title>Santa Fe Institute Workshop Summary Description//</title>
sdfsdf
+
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
 +
<meta name="generator" content="TeX4ht (http://www.cse.ohio-state.edu/~gurari/TeX4ht/)">
 +
<meta name="originator" content="TeX4ht (http://www.cse.ohio-state.edu/~gurari/TeX4ht/)">
 +
<!-- html -->
 +
<meta name="src" content="rsc.tex">
 +
<meta name="date" content="2010-12-13 15:07:00">
 +
<link rel="stylesheet" type="text/css" href="rsc.css">
 +
</head><body
 +
>
 +
  <div class="maketitle">
 +
  <h2 class="titleHead"><a
 +
id="x1-1doc"></a>
 +
Santa Fe Institute Workshop<br />
 +
Summary Description
 +
  </h2>
 +
  <div class="RRAP">
 +
<span
 +
class="cmr-10">(</span><span class="date" ><span
 +
class="cmr-10">Dated: December 13, 2010</span></span><span
 +
class="cmr-10">)</span>
 +
  </div>
 +
<div class="abstractheading"></div>
 +
        <div class="abstract">
 +
      <!--l. 50--><p class="noindent" ><span
 +
class="cmbx-12">Title</span><span
 +
class="cmr-12">:</span><br
 +
class="newline" /><span
 +
class="cmr-12">&#x00A0;      Randomness, Structure, and Causality:</span><br
 +
class="newline" /><span
 +
class="cmr-12">&#x00A0;</span><span
 +
class="cmr-12">&#x00A0;</span><span
 +
class="cmr-12">&#x00A0;          Measures of complexity from theory to applications</span><br
 +
class="newline" />
 +
      <span
 +
class="cmbx-12">Dates</span><span
 +
class="cmr-12">: 9-13 January 2011</span><br
 +
class="newline" /> <span
 +
class="cmbx-12">Location</span><span
 +
class="cmr-12">: Santa Fe Institute, Santa Fe, New Mexico</span><br
 +
class="newline" /> <span
 +
class="cmbx-12">Organizers</span><span
 +
class="cmr-12">:</span><br
 +
class="newline" /><span
 +
class="cmr-12">&#x00A0;      Jim Crutchfield (SFI and UC Davis, chaos@ucdavis.edu)</span><br
 +
class="newline" /><span
 +
class="cmr-12">&#x00A0;      Jon Machta (SFI and University of Massachusetts, machta@physics.umass.edu)</span>
 +
        </div>
 +
  <div class="frontpagefootnotes">
 +
  </div>
 +
  </div>
 +
<a
 +
id="likesection.1"></a>
 +
  <h3 class="likesectionHead"><a
 +
id="x1-1000"></a>Description</h3>
 +
<!--l. 75--><p class="noindent" >In 1989, SFI hosted a workshop&#8212;<span
 +
class="cmti-10x-x-109">Complexity, Entropy, and the Physics of Information</span>&#8212;on fundamental
 +
                                                                                       
 +
                                                                                       
 +
definitions of complexity. This workshop and the proceedings that resulted [<a
 +
href="#XZure89a">1</a>] stimulated a great deal of
 +
thinking about how to define complexity. In many ways&#8212;some direct, many indirect&#8212;the foundational
 +
theme colored much of SFI&#8217;s research planning and, more generally, the evolution of complex system
 +
science since then. Complex systems science has considerably matured as a field in the intervening
 +
decades and we believe it is now time to revisit fundamental aspects of the field in a workshop format at
 +
SFI. Partly, this is to take stock; but it is also to ask what innovations are needed for the coming
 +
decades, as complex systems continues to extend its influence in the sciences, engineering, and
 +
humanities.
 +
<!--l. 90--><p class="indent" >  The goal of the workshop is to bring together workers from a variety of fields to discuss structural and
 +
dynamical measures of complexity appropriate for their field and the commonality between these
 +
measures. Some of the questions that we will address in the workshop are:
 +
      <ol  class="enumerate1" >
 +
      <li
 +
  class="enumerate" id="x1-1002x1">Are there fundamental measures of complexity that can be applied across disciplines or are
 +
      measures of complexity necessarily tied to particular domains?
 +
      </li>
 +
      <li
 +
  class="enumerate" id="x1-1004x2">How is a system&#8217;s causal organization, reflected in models of its dynamics, related to its
 +
      complexity?
 +
      </li>
 +
      <li
 +
  class="enumerate" id="x1-1006x3">Are  there  universal  mechanisms  at  work  that  lead  to  increases  in  complexity  or  does
 +
      complexity arise for qualitatively different reasons in different settings?
 +
      </li>
 +
      <li
 +
  class="enumerate" id="x1-1008x4">Can we reach agreement on general properties that all measures of complexity must have?
 +
      </li>
 +
      <li
 +
  class="enumerate" id="x1-1010x5">How would the scientific community benefit from a consensus on the properties that measures
 +
      of complexity should possess?</li></ol>
 +
<!--l. 112--><p class="indent" >  It&#8217;s a four-day workshop with about 20 or so participants. We will have a stimulating and highly
 +
interdisciplinary group with representation from physics, biology, computer science, social science, and
 +
mathematics. An important goal is to understand the successes and difficulties in deploying complexity
 +
measures in practice. And so, participants come from both theory and experiment, with a particular
 +
emphasis on those who can constructively bridge the two.
 +
<!--l. 120--><p class="indent" >  Since the 1989 SFI workshop, a number of distinct strands have developed in the effort to measure
 +
complexity. Several of the well-developed strands are based on
 +
                                                                                       
 +
                                                                                       
 +
      <ul class="itemize1">
 +
      <li class="itemize">Predictive information and excess entropy&#x00A0;[<a
 +
href="#XJunc79">2</a>&#8211;<a
 +
href="#XCrut01a">7</a>],
 +
      </li>
 +
      <li class="itemize">Statistical complexity and causal structure&#x00A0;[<a
 +
href="#XCrut88a">8</a>&#8211;<a
 +
href="#XShal98a">10</a>],
 +
      </li>
 +
      <li class="itemize">Logical depth and computational complexity&#x00A0;[<a
 +
href="#XBenn90">11</a>&#8211;<a
 +
href="#XMach06a">15</a>], and
 +
      </li>
 +
      <li class="itemize">Effective complexity&#x00A0;[<a
 +
href="#XGeLl96">16</a>,&#x00A0;<a
 +
href="#Xay-2008">17</a>].</li></ul>
 +
<!--l. 134--><p class="noindent" >While these measures are broadly based on information theory or the theory of computation, the full set of
 +
connections and contrasts between them is not well developed. Some have sought to clarify
 +
the relationship among these measures [<a
 +
href="#XCrut01a">7</a>,&#x00A0;<a
 +
href="#Xay-2008">17</a>&#8211;<a
 +
href="#XFeld98b">20</a>] and so another goal of the workshop is
 +
to foster this kind of comparative work by bringing together researchers developing various
 +
measures.
 +
<!--l. 141--><p class="indent" >  A second motivation for the workshop is to bring together workers interested in foundational
 +
questions&#8212;who are mainly from the physics, mathematics, and computer science communities&#8212;with
 +
complex systems scientists in experimental, data-driven fields who have developed quantitative
 +
measures of complexity, organization, and emergence that are useful in their fields. The range of
 +
data-driven fields using complexity measures is impressively broad: ranging from molecular
 +
excitation dynamics [<a
 +
href="#XNeru08a">21</a>] and spectroscopic observations of the conformational dynamics of
 +
single molecules [<a
 +
href="#XLi08a">22</a>] through modeling subgrid structure in turbulent fluid flows [<a
 +
href="#XPalm00a">23</a>] and new
 +
visualization methods for emergent flow patterns [<a
 +
href="#XJani07a">24</a>] to monitoring market efficiency [<a
 +
href="#XYang08a">25</a>] and the
 +
organization of animal social structure [<a
 +
href="#XAy07a">26</a>]. The intention is to find relations between the practically
 +
motivated measures and the more general and fundamentally motivated measures. Can the
 +
practically motivated measures be improved by an appreciation of fundamental principles? Can
 +
fundamental definitions be sharpened by consideration of how they interact with real-world
 +
data?
 +
<!--l. 159--><p class="indent" >  Overall, the workshop&#8217;s intention is to re-ignite the efforts that began with <span
 +
class="cmti-10x-x-109">Complexity, Entropy,</span>
 +
<span
 +
class="cmti-10x-x-109">and the Physics of Information </span>workshop. A new level of rigor, in concepts and in analysis,
 +
is now apparent in how statistical mechanics, nonlinear dynamics, information theory, and
 +
computation theory can be applied to complex systems. The meteoric rise of both computer
 +
power and machine learning has led to new algorithms that address many of the original
 +
computational difficulties in managing data from complex systems and in estimating various
 +
complexity measures. Given progress on all these fronts, the time is ripe to develop a much closer
 +
                                                                                       
 +
                                                                                       
 +
connection between fundamental theory and applications in many areas of complex systems
 +
science.
 +
<!--l. 1--><p class="indent" >
 +
                                                                                        <a
 +
id="likesection.2"></a><a
 +
id="Q1-1-1"></a>
 +
<!--l. 1--><p class="noindent" >
 +
    <div class="thebibliography">
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XZure89a"></a><span
 +
class="cmr-10">[1]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">W.</span><span
 +
class="cmr-10">&#x00A0;Zurek, editor. </span><span
 +
class="cmti-10">Entropy, Complexity, and the Physics of Information</span><span
 +
class="cmr-10">, volume VIII of </span><span
 +
class="cmti-10">SFI Studies</span>
 +
    <span
 +
class="cmti-10">in the Sciences of Complexity</span><span
 +
class="cmr-10">. Addison-Wesley, Reading, Massachusetts, 1990.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XJunc79"></a><span
 +
class="cmr-10">[2]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">A.</span><span
 +
class="cmr-10">&#x00A0;del Junco and M.</span><span
 +
class="cmr-10">&#x00A0;Rahe.  Finitary codings and weak bernoulli partitions.  </span><span
 +
class="cmti-10">Proc. AMS</span><span
 +
class="cmr-10">, 75:259,</span>
 +
    <span
 +
class="cmr-10">1979.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XCrut82b"></a><span
 +
class="cmr-10">[3]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">J.</span><span
 +
class="cmr-10">&#x00A0;P. Crutchfield and N.</span><span
 +
class="cmr-10">&#x00A0;H. Packard. Symbolic dynamics of one-dimensional maps: Entropies, finite</span>
 +
    <span
 +
class="cmr-10">precision, and noise. </span><span
 +
class="cmti-10">Intl. J. Theo. Phys.</span><span
 +
class="cmr-10">, 21:433, 1982.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XErik87"></a><span
 +
class="cmr-10">[4]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">K-E. Eriksson and K.</span><span
 +
class="cmr-10">&#x00A0;Lindgren. Structural information in self-organizing systems. </span><span
 +
class="cmti-10">Physica Scripta</span><span
 +
class="cmr-10">,</span>
 +
    <span
 +
class="cmr-10">1987.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XGras86"></a><span
 +
class="cmr-10">[5]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">P.</span><span
 +
class="cmr-10">&#x00A0;Grassberger.  Toward a quantitative theory of self-generated complexity.  </span><span
 +
class="cmti-10">Intl. J. Theo. Phys.</span><span
 +
class="cmr-10">,</span>
 +
    <span
 +
class="cmr-10">25:907, 1986.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XEbel99a"></a><span
 +
class="cmr-10">[6]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">W.</span><span
 +
class="cmr-10">&#x00A0;Ebeling, L.</span><span
 +
class="cmr-10">&#x00A0;Molgedey, J.</span><span
 +
class="cmr-10">&#x00A0;Kurths, and U.</span><span
 +
class="cmr-10">&#x00A0;Schwarz.  Entropy, complexity, predictability and</span>
 +
    <span
 +
class="cmr-10">data analysis of time series and letter sequences. </span><a
 +
href=" http://summa.physik.hu-berlin.de/tsd/" class="url" ><span
 +
class="cmtt-10">http://summa.physik.hu-berlin.de/tsd/</span></a><span
 +
class="cmr-10">, 1999.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XCrut01a"></a><span
 +
class="cmr-10">[7]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">J.</span><span
 +
class="cmr-10">&#x00A0;P. Crutchfield and D.</span><span
 +
class="cmr-10">&#x00A0;P. Feldman. Regularities unseen, randomness observed: Levels of entropy</span>
 +
    <span
 +
class="cmr-10">convergence. </span><span
 +
class="cmti-10">CHAOS</span><span
 +
class="cmr-10">, 13(1):25&#8211;54, 2003.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
                                                                                       
 +
                                                                                       
 +
<a
 +
id="XCrut88a"></a><span
 +
class="cmr-10">[8]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">J.</span><span
 +
class="cmr-10">&#x00A0;P. Crutchfield and K.</span><span
 +
class="cmr-10">&#x00A0;Young. Inferring statistical complexity. </span><span
 +
class="cmti-10">Phys. Rev. Let.</span><span
 +
class="cmr-10">, 63:105&#8211;108, 1989.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XCrut97a"></a><span
 +
class="cmr-10">[9]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">J.</span><span
 +
class="cmr-10">&#x00A0;P. Crutchfield and D.</span><span
 +
class="cmr-10">&#x00A0;P. Feldman. Statistical complexity of simple one-dimensional spin systems.</span>
 +
    <span
 +
class="cmti-10">Phys. Rev. E</span><span
 +
class="cmr-10">, 55(2):1239R&#8211;1243R, 1997.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XShal98a"></a><span
 +
class="cmr-10">[10]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">C.</span><span
 +
class="cmr-10">&#x00A0;R. Shalizi and J.</span><span
 +
class="cmr-10">&#x00A0;P. Crutchfield.  Computational mechanics: Pattern and prediction, structure</span>
 +
    <span
 +
class="cmr-10">and simplicity. </span><span
 +
class="cmti-10">J. Stat. Phys.</span><span
 +
class="cmr-10">, 104:817&#8211;879, 2001.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XBenn90"></a><span
 +
class="cmr-10">[11]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">C.</span><span
 +
class="cmr-10">&#x00A0;H. Bennett. How to define complexity in physics, and why. In W.</span><span
 +
class="cmr-10">&#x00A0;H. Zurek, editor, </span><span
 +
class="cmti-10">Complexity,</span>
 +
    <span
 +
class="cmti-10">Entropy and the Physics of Information</span><span
 +
class="cmr-10">, page 137. SFI Studies in the Sciences of Complexity, Vol.</span><span
 +
class="cmr-10">&#x00A0;7,</span>
 +
    <span
 +
class="cmr-10">Addison-Wesley, 1990.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XVita93a"></a><span
 +
class="cmr-10">[12]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">M.</span><span
 +
class="cmr-10">&#x00A0;Li and P.</span><span
 +
class="cmr-10">&#x00A0;M.</span><span
 +
class="cmr-10">&#x00A0;B. Vitanyi.  </span><span
 +
class="cmti-10">An Introduction to Kolmogorov Complexity and its Applications</span><span
 +
class="cmr-10">.</span>
 +
    <span
 +
class="cmr-10">Springer-Verlag, New York, 1993.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XBenn95"></a><span
 +
class="cmr-10">[13]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">C.</span><span
 +
class="cmr-10">&#x00A0;H. Bennett. Universal computation and physical dynamics. </span><span
 +
class="cmti-10">Physica D</span><span
 +
class="cmr-10">, 86:268, 1995.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XMaGr96"></a><span
 +
class="cmr-10">[14]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">J.</span><span
 +
class="cmr-10">&#x00A0;Machta and R.</span><span
 +
class="cmr-10">&#x00A0;Greenlaw. The computational complexity of generating random fractals. </span><span
 +
class="cmti-10">J. Stat.</span>
 +
    <span
 +
class="cmti-10">Phys.</span><span
 +
class="cmr-10">, 82:1299, 1996.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XMach06a"></a><span
 +
class="cmr-10">[15]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">J.</span><span
 +
class="cmr-10">&#x00A0;Machta.    Complexity,  parallel  computation  and  statistical  physics.    </span><span
 +
class="cmti-10">Complexity  Journal</span><span
 +
class="cmr-10">,</span>
 +
    <span
 +
class="cmr-10">11(5):46&#8211;64, 2006.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XGeLl96"></a><span
 +
class="cmr-10">[16]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">Murray  Gell-Mann  and  Seth  Lloyd.    Information  measures,  effective  complexity,  and  total</span>
 +
    <span
 +
class="cmr-10">information. </span><span
 +
class="cmti-10">Complexity</span><span
 +
class="cmr-10">, 2(1):44&#8211;52, 1996.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="Xay-2008"></a><span
 +
class="cmr-10">[17]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">Nihat Ay, Markus Mueller, and Arleta Szkola. Effective complexity and its relation to logical depth,</span>
 +
    <span
 +
class="cmr-10">2008.</span>
 +
                                                                                       
 +
                                                                                       
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XLind88b"></a><span
 +
class="cmr-10">[18]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">K.</span><span
 +
class="cmr-10">&#x00A0;Lindgren and M.</span><span
 +
class="cmr-10">&#x00A0;G. Norhdal. Complexity measures and cellular automata. </span><span
 +
class="cmti-10">Complex Systems</span><span
 +
class="cmr-10">,</span>
 +
    <span
 +
class="cmr-10">2(4):409&#8211;440, 1988.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XCrut92c"></a><span
 +
class="cmr-10">[19]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">J.</span><span
 +
class="cmr-10">&#x00A0;P. Crutchfield.  The calculi of emergence: Computation, dynamics, and induction.  </span><span
 +
class="cmti-10">Physica D</span><span
 +
class="cmr-10">,</span>
 +
    <span
 +
class="cmr-10">75:11&#8211;54, 1994.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XFeld98b"></a><span
 +
class="cmr-10">[20]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">D.</span><span
 +
class="cmr-10">&#x00A0;P. Feldman and J.</span><span
 +
class="cmr-10">&#x00A0;P. Crutchfield. Discovering non-critical organization: Statistical mechanical,</span>
 +
    <span
 +
class="cmr-10">information theoretic, and computational views of patterns in simple one-dimensional spin systems.</span>
 +
    <span
 +
class="cmr-10">1998. Santa Fe Institute Working Paper 98-04-026.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XNeru08a"></a><span
 +
class="cmr-10">[21]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">D.</span><span
 +
class="cmr-10">&#x00A0;Nerukh, V.</span><span
 +
class="cmr-10">&#x00A0;Ryabov, and R.C. Glen.  Complex temporal patterns in molecular dynamics: A</span>
 +
    <span
 +
class="cmr-10">direct measure of the phase-space exploration by the trajectory at macroscopic time scales.  </span><span
 +
class="cmti-10">Physical</span>
 +
    <span
 +
class="cmti-10">Review E</span><span
 +
class="cmr-10">, 77(3):036225, 2008.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XLi08a"></a><span
 +
class="cmr-10">[22]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">C.-B. Li, H.</span><span
 +
class="cmr-10">&#x00A0;Yang, and T.</span><span
 +
class="cmr-10">&#x00A0;Komatsuzaki.  Multiscale complex network of protein conformational</span>
 +
    <span
 +
class="cmr-10">fluctuations in single-molecule time series.  </span><span
 +
class="cmti-10">Proceedings of the National Academy of Sciences USA</span><span
 +
class="cmr-10">,</span>
 +
    <span
 +
class="cmr-10">105:536&#8211;541, 2008.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XPalm00a"></a><span
 +
class="cmr-10">[23]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">A.</span><span
 +
class="cmr-10">&#x00A0;J. Palmer, C.</span><span
 +
class="cmr-10">&#x00A0;W. Fairall, and W.</span><span
 +
class="cmr-10">&#x00A0;A. Brewer. Complexity in the atmosphere. </span><span
 +
class="cmti-10">IEEE Transactions</span>
 +
    <span
 +
class="cmti-10">on Geoscience and Remote Sensing</span><span
 +
class="cmr-10">, 38(4):2056&#8211;2063, 2000.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XJani07a"></a><span
 +
class="cmr-10">[24]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">H.</span><span
 +
class="cmr-10">&#x00A0;Janicke,  A.</span><span
 +
class="cmr-10">&#x00A0;Wiebel,  G.</span><span
 +
class="cmr-10">&#x00A0;Scheuermann,  and  W.</span><span
 +
class="cmr-10">&#x00A0;Kollmann.    Multifield  visualization  using</span>
 +
    <span
 +
class="cmr-10">local  statistical  complexity.    </span><span
 +
class="cmti-10">IEEE  Transactions  on  In  Visualization  and  Computer  Graphics</span><span
 +
class="cmr-10">,</span>
 +
    <span
 +
class="cmr-10">13(6):1384&#8211;1391, 2007.</span>
 +
    </p>
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XYang08a"></a><span
 +
class="cmr-10">[25]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">J.-S. Yang, W.</span><span
 +
class="cmr-10">&#x00A0;Kwak, T.</span><span
 +
class="cmr-10">&#x00A0;Kaizoji, and I.-M. Kim. Increasing market efficiency in the stock markets.</span>
 +
    <span
 +
class="cmti-10">European Physical Journal B</span><span
 +
class="cmr-10">, 61(2):241&#8211;246, 2008.</span>
 +
    </p>
 +
                                                                                       
 +
                                                                                       
 +
    <p class="bibitem" ><span class="biblabel">
 +
<a
 +
id="XAy07a"></a><span
 +
class="cmr-10">[26]</span> <span class="bibsp"><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span><span
 +
class="cmr-10">&#x00A0;</span></span></span><span
 +
class="cmr-10">N.</span><span
 +
class="cmr-10">&#x00A0;Ay, J.C. Flack, and D.C. Krakauer.  Robustness and complexity co-constructed in multimodal</span>
 +
    <span
 +
class="cmr-10">signalling networks. </span><span
 +
class="cmti-10">Philos. Trans. Roy. Soc. London B</span><span
 +
class="cmr-10">, 362:441&#8211;447, 2007.</span>
 +
</p>
 +
    </div>
 +
   
 +
</body>

Revision as of 23:10, 13 December 2010

Workshop Navigation

<head><title>Santa Fe Institute Workshop Summary Description//</title> <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> <meta name="generator" content="TeX4ht (http://www.cse.ohio-state.edu/~gurari/TeX4ht/)"> <meta name="originator" content="TeX4ht (http://www.cse.ohio-state.edu/~gurari/TeX4ht/)"> <meta name="src" content="rsc.tex"> <meta name="date" content="2010-12-13 15:07:00"> <link rel="stylesheet" type="text/css" href="rsc.css"> </head><body >

<a id="x1-1doc"></a> Santa Fe Institute Workshop
Summary Description

(Dated: December 13, 2010)

Title:
  Randomness, Structure, and Causality:
    Measures of complexity from theory to applications
Dates: 9-13 January 2011
Location: Santa Fe Institute, Santa Fe, New Mexico
Organizers:
  Jim Crutchfield (SFI and UC Davis, chaos@ucdavis.edu)
  Jon Machta (SFI and University of Massachusetts, machta@physics.umass.edu)

<a

id="likesection.1"></a>

<a id="x1-1000"></a>Description

In 1989, SFI hosted a workshop—Complexity, Entropy, and the Physics of Information—on fundamental definitions of complexity. This workshop and the proceedings that resulted [<a href="#XZure89a">1</a>] stimulated a great deal of thinking about how to define complexity. In many ways—some direct, many indirect—the foundational theme colored much of SFI’s research planning and, more generally, the evolution of complex system science since then. Complex systems science has considerably matured as a field in the intervening decades and we believe it is now time to revisit fundamental aspects of the field in a workshop format at SFI. Partly, this is to take stock; but it is also to ask what innovations are needed for the coming decades, as complex systems continues to extend its influence in the sciences, engineering, and humanities.

The goal of the workshop is to bring together workers from a variety of fields to discuss structural and dynamical measures of complexity appropriate for their field and the commonality between these measures. Some of the questions that we will address in the workshop are:

  1. Are there fundamental measures of complexity that can be applied across disciplines or are measures of complexity necessarily tied to particular domains?
  2. How is a system’s causal organization, reflected in models of its dynamics, related to its complexity?
  3. Are there universal mechanisms at work that lead to increases in complexity or does complexity arise for qualitatively different reasons in different settings?
  4. Can we reach agreement on general properties that all measures of complexity must have?
  5. How would the scientific community benefit from a consensus on the properties that measures of complexity should possess?

It’s a four-day workshop with about 20 or so participants. We will have a stimulating and highly interdisciplinary group with representation from physics, biology, computer science, social science, and mathematics. An important goal is to understand the successes and difficulties in deploying complexity measures in practice. And so, participants come from both theory and experiment, with a particular emphasis on those who can constructively bridge the two.

Since the 1989 SFI workshop, a number of distinct strands have developed in the effort to measure complexity. Several of the well-developed strands are based on

  • Predictive information and excess entropy [<a href="#XJunc79">2</a>–<a href="#XCrut01a">7</a>],
  • Statistical complexity and causal structure [<a href="#XCrut88a">8</a>–<a href="#XShal98a">10</a>],
  • Logical depth and computational complexity [<a href="#XBenn90">11</a>–<a href="#XMach06a">15</a>], and
  • Effective complexity [<a href="#XGeLl96">16</a>, <a href="#Xay-2008">17</a>].

While these measures are broadly based on information theory or the theory of computation, the full set of connections and contrasts between them is not well developed. Some have sought to clarify the relationship among these measures [<a href="#XCrut01a">7</a>, <a href="#Xay-2008">17</a>–<a href="#XFeld98b">20</a>] and so another goal of the workshop is to foster this kind of comparative work by bringing together researchers developing various measures.

A second motivation for the workshop is to bring together workers interested in foundational questions—who are mainly from the physics, mathematics, and computer science communities—with complex systems scientists in experimental, data-driven fields who have developed quantitative measures of complexity, organization, and emergence that are useful in their fields. The range of data-driven fields using complexity measures is impressively broad: ranging from molecular excitation dynamics [<a href="#XNeru08a">21</a>] and spectroscopic observations of the conformational dynamics of single molecules [<a href="#XLi08a">22</a>] through modeling subgrid structure in turbulent fluid flows [<a href="#XPalm00a">23</a>] and new visualization methods for emergent flow patterns [<a href="#XJani07a">24</a>] to monitoring market efficiency [<a href="#XYang08a">25</a>] and the organization of animal social structure [<a href="#XAy07a">26</a>]. The intention is to find relations between the practically motivated measures and the more general and fundamentally motivated measures. Can the practically motivated measures be improved by an appreciation of fundamental principles? Can fundamental definitions be sharpened by consideration of how they interact with real-world data?

Overall, the workshop’s intention is to re-ignite the efforts that began with Complexity, Entropy, and the Physics of Information workshop. A new level of rigor, in concepts and in analysis, is now apparent in how statistical mechanics, nonlinear dynamics, information theory, and computation theory can be applied to complex systems. The meteoric rise of both computer power and machine learning has led to new algorithms that address many of the original computational difficulties in managing data from complex systems and in estimating various complexity measures. Given progress on all these fronts, the time is ripe to develop a much closer connection between fundamental theory and applications in many areas of complex systems science.

<a id="likesection.2"></a><a id="Q1-1-1"></a>

<a id="XZure89a"></a>[1]    W. Zurek, editor. Entropy, Complexity, and the Physics of Information, volume VIII of SFI Studies in the Sciences of Complexity. Addison-Wesley, Reading, Massachusetts, 1990.

<a id="XJunc79"></a>[2]    A. del Junco and M. Rahe. Finitary codings and weak bernoulli partitions. Proc. AMS, 75:259, 1979.

<a id="XCrut82b"></a>[3]    J. P. Crutchfield and N. H. Packard. Symbolic dynamics of one-dimensional maps: Entropies, finite precision, and noise. Intl. J. Theo. Phys., 21:433, 1982.

<a id="XErik87"></a>[4]    K-E. Eriksson and K. Lindgren. Structural information in self-organizing systems. Physica Scripta, 1987.

<a id="XGras86"></a>[5]    P. Grassberger. Toward a quantitative theory of self-generated complexity. Intl. J. Theo. Phys., 25:907, 1986.

<a id="XEbel99a"></a>[6]    W. Ebeling, L. Molgedey, J. Kurths, and U. Schwarz. Entropy, complexity, predictability and data analysis of time series and letter sequences. <a href=" http://summa.physik.hu-berlin.de/tsd/" class="url" >http://summa.physik.hu-berlin.de/tsd/</a>, 1999.

<a id="XCrut01a"></a>[7]    J. P. Crutchfield and D. P. Feldman. Regularities unseen, randomness observed: Levels of entropy convergence. CHAOS, 13(1):25–54, 2003.

<a id="XCrut88a"></a>[8]    J. P. Crutchfield and K. Young. Inferring statistical complexity. Phys. Rev. Let., 63:105–108, 1989.

<a id="XCrut97a"></a>[9]    J. P. Crutchfield and D. P. Feldman. Statistical complexity of simple one-dimensional spin systems. Phys. Rev. E, 55(2):1239R–1243R, 1997.

<a id="XShal98a"></a>[10]    C. R. Shalizi and J. P. Crutchfield. Computational mechanics: Pattern and prediction, structure and simplicity. J. Stat. Phys., 104:817–879, 2001.

<a id="XBenn90"></a>[11]    C. H. Bennett. How to define complexity in physics, and why. In W. H. Zurek, editor, Complexity, Entropy and the Physics of Information, page 137. SFI Studies in the Sciences of Complexity, Vol. 7, Addison-Wesley, 1990.

<a id="XVita93a"></a>[12]    M. Li and P. M. B. Vitanyi. An Introduction to Kolmogorov Complexity and its Applications. Springer-Verlag, New York, 1993.

<a id="XBenn95"></a>[13]    C. H. Bennett. Universal computation and physical dynamics. Physica D, 86:268, 1995.

<a id="XMaGr96"></a>[14]    J. Machta and R. Greenlaw. The computational complexity of generating random fractals. J. Stat. Phys., 82:1299, 1996.

<a id="XMach06a"></a>[15]    J. Machta. Complexity, parallel computation and statistical physics. Complexity Journal, 11(5):46–64, 2006.

<a id="XGeLl96"></a>[16]    Murray Gell-Mann and Seth Lloyd. Information measures, effective complexity, and total information. Complexity, 2(1):44–52, 1996.

<a id="Xay-2008"></a>[17]    Nihat Ay, Markus Mueller, and Arleta Szkola. Effective complexity and its relation to logical depth, 2008.

<a id="XLind88b"></a>[18]    K. Lindgren and M. G. Norhdal. Complexity measures and cellular automata. Complex Systems, 2(4):409–440, 1988.

<a id="XCrut92c"></a>[19]    J. P. Crutchfield. The calculi of emergence: Computation, dynamics, and induction. Physica D, 75:11–54, 1994.

<a id="XFeld98b"></a>[20]    D. P. Feldman and J. P. Crutchfield. Discovering non-critical organization: Statistical mechanical, information theoretic, and computational views of patterns in simple one-dimensional spin systems. 1998. Santa Fe Institute Working Paper 98-04-026.

<a id="XNeru08a"></a>[21]    D. Nerukh, V. Ryabov, and R.C. Glen. Complex temporal patterns in molecular dynamics: A direct measure of the phase-space exploration by the trajectory at macroscopic time scales. Physical Review E, 77(3):036225, 2008.

<a id="XLi08a"></a>[22]    C.-B. Li, H. Yang, and T. Komatsuzaki. Multiscale complex network of protein conformational fluctuations in single-molecule time series. Proceedings of the National Academy of Sciences USA, 105:536–541, 2008.

<a id="XPalm00a"></a>[23]    A. J. Palmer, C. W. Fairall, and W. A. Brewer. Complexity in the atmosphere. IEEE Transactions on Geoscience and Remote Sensing, 38(4):2056–2063, 2000.

<a id="XJani07a"></a>[24]    H. Janicke, A. Wiebel, G. Scheuermann, and W. Kollmann. Multifield visualization using local statistical complexity. IEEE Transactions on In Visualization and Computer Graphics, 13(6):1384–1391, 2007.

<a id="XYang08a"></a>[25]    J.-S. Yang, W. Kwak, T. Kaizoji, and I.-M. Kim. Increasing market efficiency in the stock markets. European Physical Journal B, 61(2):241–246, 2008.


<a id="XAy07a"></a>[26]    N. Ay, J.C. Flack, and D.C. Krakauer. Robustness and complexity co-constructed in multimodal signalling networks. Philos. Trans. Roy. Soc. London B, 362:441–447, 2007.

</body>