Actions

Difference between revisions of "Randomness, Structure and Causality"

From Santa Fe Institute Events Wiki

 
(18 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
{{Randomness, Structure and Causality}}
 
{{Randomness, Structure and Causality}}
  
<head><title>Santa Fe Institute Workshop Summary Description//</title>
+
 
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
+
== Randomness, Structure, and Causality: Measures of complexity from theory to applications ==
<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 -->
+
== Organizers ==
<meta name="src" content="rsc.tex">  
+
Jim Crutchfield (SFI & UC Davis)
<meta name="date" content="2010-12-13 15:07:00">
+
 
<link rel="stylesheet" type="text/css" href="rsc.css">
+
Jon Machta (SFI & UMass Amherst)
</head><body
+
 
>
+
== Workshop summary ==
  <div class="maketitle">
+
[[Media:Rsc.pdf| Summary Description (PDF)]]
  <h2 class="titleHead"><a  
+
 
id="x1-1doc"></a>
+
<br>
Santa Fe Institute Workshop<br />
+
In 1989, SFI hosted a
Summary Description
+
workshop&mdash;''Complexity, Entropy, and the Physics of Information''&mdash;on
  </h2>
+
fundamental definitions of complexity. This
  <div class="RRAP">
+
workshop and the proceedings that resulted stimulated a
<span
+
great deal of thinking about how to define complexity. In many ways&mdash;some
class="cmr-10">(</span><span class="date" ><span
+
direct, many indirect&mdash;the foundational theme colored much of SFI's research
class="cmr-10">Dated: December 13, 2010</span></span><span
+
planning and, more generally, the evolution of complex system science since
class="cmr-10">)</span>
+
then. Complex systems science has considerably matured as a field in the intervening
  </div>
+
decades and we believe it is now time to revisit fundamental aspects of the field in a
<div class="abstractheading"></div>
+
workshop format at SFI. Partly, this is to take stock; but it is
        <div class="abstract">
+
also to ask what innovations are needed for the coming decades, as
      <!--l. 50--><p class="noindent" ><span
+
complex systems continues to extend its influence in the sciences,
class="cmbx-12">Title</span><span
+
engineering, and humanities.
class="cmr-12">:</span><br
+
 
class="newline" /><span
+
The goal of the workshop is to bring together workers from a
class="cmr-12">&#x00A0;      Randomness, Structure, and Causality:</span><br
+
variety of fields to discuss structural and dynamical measures of complexity appropriate for their
class="newline" /><span
+
field and the commonality between these measures. Some of the questions that
class="cmr-12">&#x00A0;</span><span
+
we will address in the workshop are:
class="cmr-12">&#x00A0;</span><span
+
<ul>
class="cmr-12">&#x00A0;          Measures of complexity from theory to applications</span><br
+
<li>
class="newline" />
+
Are there fundamental measures of complexity that can be applied across
      <span
+
disciplines or are measures of complexity necessarily tied to particular
class="cmbx-12">Dates</span><span
+
domains?
class="cmr-12">: 9-13 January 2011</span><br
+
<li>
class="newline" /> <span
+
How is a system's causal organization, reflected in models of its
class="cmbx-12">Location</span><span
+
dynamics, related to its complexity?
class="cmr-12">: Santa Fe Institute, Santa Fe, New Mexico</span><br
+
<li>
class="newline" /> <span
+
Are there universal mechanisms at work that lead to increases in
class="cmbx-12">Organizers</span><span
+
complexity or does complexity arise for qualitatively different reasons in
class="cmr-12">:</span><br
+
different settings?
class="newline" /><span
+
<li>
class="cmr-12">&#x00A0;      Jim Crutchfield (SFI and UC Davis, chaos@ucdavis.edu)</span><br
+
Can we reach agreement on general properties that all measures of
class="newline" /><span
+
complexity must have?
class="cmr-12">&#x00A0;      Jon Machta (SFI and University of Massachusetts, machta@physics.umass.edu)</span>
+
<li>
        </div>
+
How would the scientific community benefit from a consensus on the
  <div class="frontpagefootnotes">
+
properties that measures of complexity should possess?
  </div>
+
</ul>
  </div>
+
 
<a  
+
It's a four-day workshop with about 20 or so participants.
id="likesection.1"></a>
+
We will have a stimulating and highly interdisciplinary group with
  <h3 class="likesectionHead"><a
+
representation from physics, biology, computer science, social science, and
id="x1-1000"></a>Description</h3>
+
mathematics. An important goal is to understand the successes and
<!--l. 75--><p class="noindent" >In 1989, SFI hosted a workshop&#8212;<span
+
difficulties in deploying complexity measures in practice. And so,
class="cmti-10x-x-109">Complexity, Entropy, and the Physics of Information</span>&#8212;on fundamental
+
participants come from both theory and experiment, with a
                                                                                       
+
particular emphasis on those who can constructively bridge the two.
                                                                                       
+
 
definitions of complexity. This workshop and the proceedings that resulted [<a
+
Since the 1989 SFI workshop, a number of distinct strands have developed in
href="#XZure89a">1</a>] stimulated a great deal of
+
the effort to measure complexity. Several of the well-developed strands are
thinking about how to define complexity. In many ways&#8212;some direct, many indirect&#8212;the foundational
+
based on
theme colored much of SFI&#8217;s research planning and, more generally, the evolution of complex system
+
<ul>
science since then. Complex systems science has considerably matured as a field in the intervening
+
<li>Predictive information and excess entropy,
decades and we believe it is now time to revisit fundamental aspects of the field in a workshop format at
+
<li>Statistical complexity and causal structure,
SFI. Partly, this is to take stock; but it is also to ask what innovations are needed for the coming
+
<li>
decades, as complex systems continues to extend its influence in the sciences, engineering, and
+
Logical depth and computational complexity, and
humanities.
+
<li>
<!--l. 90--><p class="indent" >  The goal of the workshop is to bring together workers from a variety of fields to discuss structural and
+
Effective complexity.
dynamical measures of complexity appropriate for their field and the commonality between these
+
</ul>
measures. Some of the questions that we will address in the workshop are:
+
While these measures are broadly based on information theory or the theory of
      <ol  class="enumerate1" >
+
computation, the full set of connections and contrasts between them is not
      <li
+
well developed. Some have sought to clarify the relationship among these
  class="enumerate" id="x1-1002x1">Are there fundamental measures of complexity that can be applied across disciplines or are
+
measures and so another goal of
      measures of complexity necessarily tied to particular domains?
+
the workshop is to foster this kind of comparative work by bringing together
      </li>
+
researchers developing various measures.  
      <li
+
 
  class="enumerate" id="x1-1004x2">How is a system&#8217;s causal organization, reflected in models of its dynamics, related to its
+
A second motivation for the workshop is to bring together workers interested in
      complexity?
+
foundational questions&mdash;who are mainly from the physics, mathematics, and
      </li>
+
computer science communities&mdash;with complex systems scientists in experimental,
      <li
+
data-driven fields who have developed quantitative measures of complexity,
  class="enumerate" id="x1-1006x3">Are  there  universal  mechanisms  at  work  that  lead  to  increases  in complexity or  does
+
organization, and emergence that are useful in their fields. The range of
      complexity arise for qualitatively different reasons in different settings?
+
data-driven fields using complexity measures is impressively broad: ranging
      </li>
+
from molecular excitation dynamics and spectroscopic
      <li
+
observations of the conformational dynamics of single molecules
  class="enumerate" id="x1-1008x4">Can we reach agreement on general properties that all measures of complexity must have?
+
through modeling subgrid structure in turbulent fluid flows
      </li>
+
and new visualization methods for emergent flow patterns
      <li
+
to monitoring market efficiency and the organization of animal
  class="enumerate" id="x1-1010x5">How would the scientific community benefit from a consensus on the properties that measures
+
social structure. The intention is to find relations between the
      of complexity should possess?</li></ol>
+
practically motivated measures and the more general and fundamentally motivated
<!--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
+
measures. Can the practically motivated measures be improved by an
interdisciplinary group with representation from physics, biology, computer science, social science, and
+
appreciation of fundamental principles? Can
mathematics. An important goal is to understand the successes and difficulties in deploying complexity
+
fundamental definitions be sharpened by consideration of how they interact with
measures in practice. And so, participants come from both theory and experiment, with a particular
+
real-world data?
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
+
Overall, the workshop's intention is to re-ignite the efforts that began with
complexity. Several of the well-developed strands are based on
+
''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
      <ul class="itemize1">
+
systems. The meteoric rise of both computer power and machine learning has led
      <li class="itemize">Predictive information and excess entropy&#x00A0;[<a
+
to new algorithms that address many of the original computational difficulties in
href="#XJunc79">2</a>&#8211;<a
+
managing data from complex systems and in estimating various complexity
href="#XCrut01a">7</a>],
+
measures. Given progress on all these fronts, the time is ripe to develop a
      </li>
+
much closer connection between fundamental theory and applications in many
      <li class="itemize">Statistical complexity and causal structure&#x00A0;[<a
+
areas of complex systems science.
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>
 

Latest revision as of 20:04, 17 December 2010

Workshop Navigation


Randomness, Structure, and Causality: Measures of complexity from theory to applications

Organizers

Jim Crutchfield (SFI & UC Davis)

Jon Machta (SFI & UMass Amherst)

Workshop summary

Summary Description (PDF)


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 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:

  • Are there fundamental measures of complexity that can be applied across disciplines or are measures of complexity necessarily tied to particular domains?
  • How is a system's causal organization, reflected in models of its dynamics, related to its complexity?
  • Are there universal mechanisms at work that lead to increases in complexity or does complexity arise for qualitatively different reasons in different settings?
  • Can we reach agreement on general properties that all measures of complexity must have?
  • 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,
  • Statistical complexity and causal structure,
  • Logical depth and computational complexity, and
  • Effective complexity.

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 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 and spectroscopic observations of the conformational dynamics of single molecules through modeling subgrid structure in turbulent fluid flows and new visualization methods for emergent flow patterns to monitoring market efficiency and the organization of animal social structure. 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.