{"id":1818,"date":"2014-05-27T11:55:20","date_gmt":"2014-05-27T15:55:20","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=1818"},"modified":"2016-12-10T05:04:58","modified_gmt":"2016-12-10T10:04:58","slug":"quantifying-the-rise-and-fall-of-complexity-in-closed-systems-the-coffee-automaton","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=1818","title":{"rendered":"Quantifying the Rise and Fall of Complexity in Closed Systems: The Coffee Automaton"},"content":{"rendered":"

Update (June 3):<\/strong><\/span>\u00a0A few days after we posted this paper online, Brent Werness<\/a>, a postdoc in probability theory at the University of Washington, discovered a serious error in the “experimental” part of the paper. \u00a0Happily, Brent is now collaborating with us on producing a new version of the paper that fixes the error, which we hope to have available within a few months\u00a0(and which will replace the version currently on the arXiv).<\/p>\n

To make a long story short: while the overall idea, of measuring “apparent complexity” by the compressed\u00a0file size of a coarse-grained image, is fine, the “interacting coffee automaton” that we study in the paper is not<\/strong> an example where the apparent complexity becomes large at intermediate times. \u00a0That fact can be deduced as a corollary of a\u00a0result of Liggett from 2009<\/a>\u00a0about the “symmetric exclusion process,” and can be seen as a far-reaching generalization of a result that we prove in our paper’s appendix: namely, that in the non<\/em>-interacting coffee automaton (our “control case”), the apparent complexity after t time steps is upper-bounded by O(log(nt)). \u00a0As it turns out, we were more right than we knew<\/em> to worry about large-deviation bounds giving complete mathematical control over what happens when the cream spills into the coffee, thereby preventing the apparent complexity from ever becoming large!<\/p>\n

But what about our numerical\u00a0results, which showed a small but unmistakable complexity bump for the interacting automaton (figure 10(a) in the paper)? \u00a0It now appears that the complexity bump we saw in our data is likely to be explainable by an incomplete removal of what we called “border pixel artifacts”: that is, “spurious” complexity that arises merely from the fact that, at the border between cream and coffee, we need to round the fraction of cream up or down to the nearest integer to produce a grayscale. \u00a0In the paper, we devoted a whole section (Section 6) to border pixel artifacts and the need to deal with them: something sufficiently non-obvious that in the comments of this post, you can find people arguing with me that it’s a non-issue. \u00a0Well, it now appears that we erred by underestimating<\/em> the severity of border pixel artifacts, and that a better procedure\u00a0to get rid of them would also eliminate the complexity bump for the interacting automaton.<\/p>\n

Once again, this error\u00a0has no effect on either the general idea<\/em> of complexity rising and then falling in closed thermodynamic systems, or<\/em>\u00a0our proposal\u00a0for\u00a0how to quantify that rise and fall—the two aspects of the paper that have generated the\u00a0most interest. \u00a0But we made a bad\u00a0choice of\u00a0model system with which to illustrate those ideas. \u00a0Had I looked more carefully at the data, I could’ve noticed the problem before we posted, and I take responsibility for my failure to do so.<\/p>\n

The good news is that ultimately<\/em>, I think the truth only makes our\u00a0story\u00a0more interesting. \u00a0For it turns out that apparent complexity, as we define it, is not<\/em> something that’s trivial to achieve by just setting loose a bunch of randomly-walking particles, which bump into each other but are otherwise completely independent. \u00a0If you want “complexity” along the approach to thermal equilibrium, you need\u00a0to work a bit harder for it. \u00a0One promising idea, which we’re now exploring, is to consider a cream tendril whose tip<\/em> takes a random walk through the coffee, leaving a trail of cream in its wake. \u00a0Using results in probability theory—closely related, or so I’m told, to the results for which Wendelin Werner<\/a> won his Fields Medal!—it may even be possible to prove analytically<\/em> that the apparent complexity becomes large in thermodynamic systems with this sort of behavior, much as one can prove that the complexity\u00a0doesn’t<\/em> become large in our original coffee automaton.<\/p>\n

So, if you’re interested in this topic, stay tuned for the updated version of our paper. \u00a0In the meantime, I wish to express our deepest imaginable gratitude to Brent Werness for telling us all this.<\/p>\n

\n

Good news! \u00a0After nearly three years of procrastination, fellow blogger Sean Carroll<\/a>, former MIT undergraduate Lauren Ouellette, and yours truly\u00a0finally finished a paper with the above title<\/a>\u00a0(coming soon to an arXiv near you). \u00a0PowerPoint slides<\/a> are also available (as usual, you’re on your own if you can’t open them—sorry!).<\/p>\n

For the background and context of this paper, please see my old post “The First Law of Complexodynamics,”<\/a>\u00a0which discussed Sean’s\u00a0problem of defining a “complextropy” measure that first increases and then decreases in closed thermodynamic systems, in contrast to entropy (which increases monotonically). \u00a0In this exploratory paper, we basically do five\u00a0things:<\/p>\n

    \n
  1. We survey\u00a0several candidate “complextropy” measures: their strengths, weaknesses, and relations to one another.<\/li>\n
  2. We propose\u00a0a model system for studying such\u00a0measures: a probabilistic cellular automaton that models a cup of coffee into which cream has just been poured.<\/li>\n
  3. We report the results of numerical experiments with one of the measures, which we call “apparent complexity” (basically, the gzip file size of a smeared-out image of the coffee cup). \u00a0The results confirm that the apparent complexity does indeed increase, reach a maximum, then turn around and decrease as the coffee and cream mix.<\/li>\n
  4. We discuss a technical issue that one needs to overcome (the so-called “border pixels” problem) before one can do meaningful experiments in this area, and offer a solution.<\/li>\n
  5. We raise the open\u00a0problem of proving analytically<\/em> that the apparent complexity ever becomes large for the coffee automaton. \u00a0To underscore this problem’s difficulty, we prove that the apparent complexity doesn’t<\/em>\u00a0become large in a simplified version of the coffee automaton.<\/li>\n<\/ol>\n

    Anyway, here’s the abstract:<\/p>\n

    In contrast to entropy, which increases monotonically, the “complexity” or “interestingness” of closed systems seems intuitively to increase at first and then decrease as equilibrium is approached. For example, our universe lacked complex structures at the Big Bang and will also lack them after black holes evaporate and particles are dispersed. This paper makes an initial attempt to quantify this pattern. As a model system, we use a simple, two-dimensional cellular automaton that simulates the mixing of two liquids (“coffee” and “cream”). A plausible complexity measure is then the Kolmogorov complexity of a coarse-grained approximation of the automaton’s state, which we dub the “apparent complexity.” We study this complexity measure, and show analytically that it never becomes large when the liquid particles are non-interacting. By contrast, when the particles do interact, we give numerical evidence that the complexity reaches a maximum comparable to the “coffee cup’s” horizontal dimension. We raise the problem of proving this behavior analytically.<\/p><\/blockquote>\n

    Questions and comments more than welcome.<\/p>\n

    \n

    In unrelated news, Shafi Goldwasser has asked me to announce that the Call for Papers<\/a> for the 2015 Innovations in Theoretical Computer Science (ITCS) conference is now available.<\/p>\n","protected":false},"excerpt":{"rendered":"

    Update (June 3):\u00a0A few days after we posted this paper online, Brent Werness, a postdoc in probability theory at the University of Washington, discovered a serious error in the “experimental” part of the paper. \u00a0Happily, Brent is now collaborating with us on producing a new version of the paper that fixes the error, which we […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[31,5,11],"tags":[],"class_list":["post-1818","post","type-post","status-publish","format-standard","hentry","category-announcements","category-complexity","category-nerd-interest"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1818","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1818"}],"version-history":[{"count":4,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1818\/revisions"}],"predecessor-version":[{"id":1852,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1818\/revisions\/1852"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1818"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1818"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1818"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}