UCNC day 4

UCNC day 4, with an embarrassment of riches in the form of invited talks.

We kicked off with an invited talk from Friedrich Simmel on “Chemical Communication Between Cell-Sized Reaction Compartments”. This was a fascinating account about a series of experiments sending signals between cells, droplets, and “genelets” (droplets containing cellular “naked” genetic machinery), based on the ideas of quorum sensing: when a high enough chemical signal concentrations is produced, because there are enough producers around, it invokes a response. We saw droplets signalling the chemicals, inducing bacteria to react, and that signal propagating through multiple droplets. Apparently there is a “bacterial Turing test”: can you make a droplet that a bacterium will interact with (through chemical signals) just as if it were another bacterium? These systems pass it. Through a clever use of microfluidics, we saw videos of sheets of bacteria interacting, via fluorescent protein production. The fluorescence increases both due to the being switched on by the signalling, and due to the bacteria reproducing, two process with similar timescales. The possibilities of this approach include forming spatial and temporal patterns through reaction-diffusion systems of interacting genetically programmed droplets. If all this wasn’t enough, Simmel finished his talk with a description of using electron lithography to etch chips, deposit gene-length strands of DNA in a controlled manner, which could then be manipulated to stick together (condense) into linear bundles. It’s early days yet; next on the agenda is using gene expression to control the condensation. Heady stuff!

Next was the workshop on Physics and Computation. Gilles Dowek started with an invited talk on “Quantitative Informational Aspects in Discrete Physics”. Gandy has shown that if a system (1) is homogeneous in space and time; (2) has a bounded speed of information transport; (3) has a bounded density of information, then it can be simulated by a cellular automaton. Since physics appears to satisfy these properties, it should be so simulable. Then came a short but necessary digression on Planck’s constant. The physical constant c has the dimensions of a speed, and it is the speed of light. Planck’s constant has the dimension of an action; what action is it? After a bit of discussion, it turns out that it is (a small multiple of) the area of a bit of information (in a particular choice of units where everything has a dimension that is some power of length) as given by the Bekenstein bound. Then Dowek went through how to build a CA in Newtonian physics, special relativity, and general relativity, that models free fall (subject to some assumptions). It can’t be done in Newtonian physics, because there is no bound on speed. In SR it can be done, with particles that contain 320 bits of information (using the Planck area); in GR they only need 168 bits. This is an existence proof, but the CAs defined are not very satisfactory, for several reasons. The task is to do better! Listening to this, I recalled Randal Beer’s Game of Life talk from ALife last week: looking at a CA in terms of processes rather than cells gives a much more natural formulation. I wonder if that would work here? 

Then we had a talk about “The Information Content of Systems in General Physics Theories”. The idea here is to look at a broad range of probabilistic theories, of which quantum mechanics is one instance. Investigating their computational complexity of the “advice” given by a physical system can shed light on what makes QM special, different from just a general theory.

After lunch Ana Belén Sainz gave an invited talk on “Postquantum Steering”. This was in the same vein as the previous talk: look at a general theory, then compare with QM. Here the idea was applied to one particular kind of system: how much can Bob “steer” distant Alice’s state, by making measurements on his own state?

Next came some more talks. The first, on “Sequent Calculus Representations for Quantum Circuits”, was an approach to making reasoning about quantum circuits look like proof theoretic reasoning in other branches of computer science, by finding an appropriate set of axioms. Next was a talk on “Physical Computation, P/poly and P/log*”, looking at the computational complexity of physical computing as an unconventional co-processor, in terms of its advice complexity. After coffee we had a talk on “Local Searches Using Quantum Annealers: How to Beat Noise and Take Advantage of the Classical Algorithms we Already Have, or, Modernising Quantum Annealing using Local Search”. This contrasted classical simulated annealing, including its two improvements of parallel tempering and population annealing, with the quantum version: quantum annealing. Each has is strengths and weakeness; here was a suggestion of how to use the quantum annealing as a “subroutine”, getting the best of both approaches. The final workshop talk was on “Quantum Probability as an Application of Data Compression Principles”, a philosophical look at probabilities in general, and branching world probabilities in particular.

The day was then completed with a further invited talk, Bob Coecke talking “In Pictures: From Quantum Foundations to Natural Language Processing”. He zipped through a beautiful, formal, diagrammatic notation for quantum systems, and how the power of this notation makes many complicated quantum puzzles ad proofs essentially vanish. There will be a book, Picturing Quantum Processes, from Cambridge University press covering this published soon.  It's 922pp: pictures take a lot of space!  After all this the quantum mechanics, he went off in an unexpected direction, by showing how the very same notation could be used to calculate the meaning of sentences from their underlying grammar and the meaning of the individual words. Some modern meaning systems use high dimensional vectors to encapsulate word meanings. Adding the grammar via the diagrams improves the calculated meaning enormously. Thinking about the mathematical structures needed leads to the suggestion of using density matrices rather than vectors, to cope with ambiguous meanings. I love this kind of work: a deep piece of work in one domain that is not only applicable in a seemingly unrelated domain, but that suggests advances there, too.

UCNC day 3

UCNC day 3. Well, only half a day, as the afternoon was reserved for exploring Manchester.

We started with a super invited tutorial on “Self-Assembling Adaptive Structures with DNA”, by Rebecca Schulman. Rather than trying to assemble arbitrary structures, let’s just look at what can be done with 1D systems: filaments of DNA nanotubes than can controllably be built into strings, trees, and network structures. She pointed out that it doesn’t make sense to build every structure from weaving pure DNA: a human-size object would need about 3 light years of it. But smaller things can sensibly be built this way. This approach doesn’t include only static structures: movement can be achieved by growing at the front and dissolving at the back. This is the way the cytoskeleton in cells works to move them around. DNA nanotube growth can be controlled by a variety of chemical processes, but it’s hard to design different systems: there’s no good enough model or simulation of how it all works.  Currently things are a mixture of approximate yet expensive simulations, and lab experiments. But this is clearly a very powerful and rich area.

This was followed by the technical session: three talks related to DNA computing. The first was implementing a circuit model in a 2D gellular automaton. Next was another gellular automaton system: a maze solver. We finished the morning with a description of implementing a stack (the push-pop data structure) in DNA: the design is fascinating, and it has been implemented, at least for stack sizes of three. Again, this work is just a hint of things to come.

Then off to explore the wilds of Manchester…

UCNC day 2

UCNC day 2, a full day of talks.

First up was Masami Hagiya with an invited tutorial on “Gellular Automata”. These are a form of cellular automata implemented using gels and chemical reactions. The walls between cells can be “decomposed” or “composed” using chemical reactions – or instead can “swell” or “unswell” forming a valve. This allows chemicals to move between cells. There are theoretical results demonstrating these systems can in principle implement certain kinds of CAs. The tutorial moved on to talking about implementations. Most of the manipulations involve a form of DNA chemical computing: using complementary strands to form networks of polymers, or to control diffusion by attaching anchors. These processes can be controlled by the DNA technique of “strand displacement” that breaks the bonds between the complementary strands. There are some initial prototype implementations. These are still rather complicated, needing multiple chemical species to implement relatively simple state transitions. However, it is early days yet, and more efficient approaches may well be discovered.

Next was the workshop on Membrane systems (mostly P-Systems). Rudolf Freund started off with a tutorial, helping to introduce the concepts to people not that familiar with the area. Then on to the technical talks, covering a wide set of membrane computing topics.

Finally was the afternoon technical session. We started with a talk on Affine Automata: these use an underlying logic that is partway between classical probabilistic automata and quantum automata. Next was a talk about languages (sets of strings) arising from finite walks on Sierpinsky gaskets. And finally we had a talk on Matrix Ins-del (insertion deletion) systems (although I think a better name would be List Ins-del systems). These three combined nicely as a range of different ways of looking at language (in the CS sense) recognisers.

Then off to The Great Wall Chinese restaurant, for a very nice duck in ginger.

UCNC day 1

Another week, another conference.

I have moved from Cancun, Mexico, at the ALife conference, to Manchester, UK, for the conference on Unconventional Computation and Natural Computation (UCNC). It is very weird for me to be at a conference in the UK with “wrong way” jet lag!

The first day was a half day, starting with lunch – very civilised. The first talk was a tutorial from Jon Timmis on Swarm Robotics. This subject has multiple simple automomous robots working together with no global control, to produce an emergent behaviour and capability that none has individually. The tutorial covered the history of the subject, showing how some of the original constraints have become irrelevant: today’s “simple” robots are actually quite sophisticated compared to those at the discipline’s inception; and the original “nature inspiration” is no longer so prominent: use it if it helps, ignore it if it doesn’t. There are a couple of issues that make the subject difficult. The first is, how to design the local, individual robot rules that produce the desired emergent behaviour (and doesn’t produce undesired behaviours also)? This often reduces to an iterative design: suggest, test, refine, which can be automated in a search algorithm, such as an evolutionary search. This leads to the second issue: this search is most efficiently done in simulation, but there is a “reality gap” in simulation: the simulated physics is often too simplistic, leading to “overfitting” to the simulation and the solution then not working on the embodied physical robots. There are lots of fascinating results addressing these issues: the next challenge is moving this research out of the lab into the real world.

Then on to the technical session, with four talks. First up was my student, talking about using reservoir computing as an unconventional virtual machine for computing with carbon nanotubes: evolving the carbon nanotube system into a “good” reservoir, then training that reservoir to perform various tasks, rather than evolving the tasks directly. Next was another carbon nanotube talk, here having them in liquid crystal rather than frozen in polymer, allowing them to move to form clusters, to help their computational performance. The third talk changed tack, on to memristor logic. It appears that memristors natural support a ternary logic rather than the classical binary logic, and naturally implement different kinds of gates.  Finally, we had a talk that started with Zuse’s mechanical computer, and ended up with a “three cog, one gate” universal computer.

A great start to the conference.

film review: Inside Out

11-year-old Riley and her family move from their home in Minnesota to San Francisco. Riley leaves behind all her friends, and her beloved ice hockey. It is an emotional time for her.

Like everyone else, Riley is guided/controlled by her five emotion homunculi: Joy, Sadness, Disgust, Anger, and Fear. The young Riley is mostly governed by Joy, and is a cheerful child. But Joy has a hard time keeping her human happy after the move. Then disaster strikes: an accident sucks Joy and Sadness out of headquarters, and they become lost in long term memory. Now Fear, Anger and Disgust are left in charge, and Riley turns into a surly brat. Then it gets worse: in their attempt to help Riley, the remaining emotions get locked out of their control panel, and now Riley can’t feel anything at all.

After a slow start with a lot of info-dumping about how the interior world works (as a sort of cross between a child’s fairy tale and a cognitive neuroscience text), things ramp up once Joy and Sadness are lost, and trying to get home. The adventure is wildly imaginative, with memory stores, dream sequences, imaginary friends, forgetting, the subconscious, abstraction, and trying to catch the train of thought. In the end, Joy learns an important lesson about Sadness, becoming a more mature emotion, and Riley grows up, as her homunculi’s control console is upgraded to parallel working.

At several points in the internal journey, Joy feels some Sadness of her own, and also Fear (or at least Alarm). Embodied emotions having emotions! Does this mean that Joy has five even smaller emotion homunculi in her own head? My brain kept trying to infinitely regress at several points.

This passes the Bechdel test: Joy and Sadness are female, and spend nearly all the time talking about Riley. In the external world, Riley’s teacher is female (although I don’t believe she is named?), and speaks to Riley, asking her to introduce herself; also Riley video chats with her friend Meg back in Minnesota about their hockey team.

Yet there is a curious asymmetry here. During the film we see inside three other human heads: Riley’s mother and father, with more mature homunculi, and briefly a boy of Riley’s age, whose juvenile homunculi are freaked by being close to a girl. The end credits give us views into a few more people, a dog, and, hysterically, a cat. All these other homunculi are the same sort as their “owners”: five mature females guiding the mother, five arguably less mature and somewhat stereotypical males for the father, five young males for the boy, five very cat-like cats in the cat, and so on. Yet in Riley, although Joy, Sadness and Disgust are female, both Fear and Anger are portrayed as male. If the film had a boy main character, would any of his emotions have been portrayed as female, I wonder?

Overall, after that slow start, this is a marvellously imaginative romp through a brain, and it is interesting that the obligatory happy ending is one of growing up and the realisation that Sadness is important.

---

For all my film reviews, see my main website.

ALife day 5

ALife day 5; last but not least.

The day started as usual with a fascinating keynote: today it was Linda Smith on “We need a developmental theory of environments”. Linda’s work is on development in human babies. She has gathered a rich corpus of information on babies’ perceived environments over their first two years of life. This has been gathered from head-mounted cameras (which today are so small they are just a chip in a headband), and demonstrate convincingly that the baby’s perceived environment changes dramatically over time, and that those changes are deeply embedded in its development. Early on, there are lots of close up faces, of a few adults. Later on, the baby’s view moves to hands: watching others, and its own, manipulating objects. Different experiments demonstrate the essential nature of the body / brain / environment feedback loop.  What is in this loop changes as the baby grows, and we need to understand when and how. And, of course (unless you are purely into how to experiment on babies for fun and profit), what does this tell us about developmental artificial life? The (perceived) environment is crucial to development.

I then went to the morning technical session on Artificial Chemistries, a potential substrate for ALife. We started with a talk on a novel replicator system based on a chemistry of functional combinators, with conservation of mass. The crucial design tradeoff is not to make the underlying artificial physics so strong that replication is trivial (a “copy organism” operation in the physics), nor to make it so sparse that replication is computationally infeasible. One way to strike the happy medium is to ensure the “functional units” are composed of a few “primitive units”, giving the system a small but crucial distance from the “atoms”. Next we heard about an extension of Hutton’s original replicator AChem, adding kinetics under the Gillespie algorithm, to find a “sweet spot” where a rich set of reaction occur in a computationally feasible time. Then we heard about “messy chemistries”, those that produce a wide range of uncontrolled products, and the conditions for one of the products to come to dominate, suggesting a “selection-first” AChem route to ALife. Then we had a description of a reaction-diffusion system incorporating energetics, and how a combination of exothermic and endothermic reaction systems can stabilise temperature across a region. Finally, we heard about taking mathematics seriously in order to use algebraic concepts, particularly non-associative algebras, to design a novel sub-symbolic AChem.

Then on to the closing keynote of the conference: Katie Bentley on “Do Endothelial Cells Dream of Eclectic Shape?” She explained the title: her work is about computational modelling of real biological systems, based on computational complex systems approaches. She had been warned biologists wouldn’t read something with the word “computational” in the title, so needed to use just biological words. But she wanted to signal to the CS-types that this might be of interest to them too, so used the punning title. She asked us if we got the pun: all but one hand went up. She then asked that person if they had seen the film; yes. She told us that if this was a straight biological conference, no one would have got the pun, and hardly anyone would have seen the film. Divided communities indeed. She went on to describe her computational model of vascular growth, in normal tissue and in tumours. Agent Based modelling, combined with real data and close interactions with biologists (who know which published results to trust, and which not), have resulted in several predictions that have been tested and confirmed in the wet lab. Mostly information flows from biology to ALife; this work demonstrates a great feedback from ALife into biology.

Then it was all over bar the closing ceremony: information about the International Society for ALife, the next two ALife conferences (ECAL 2017 in Lyon, France; ALife 2018 in Japan), and a variety of awards for best papers, lifetime achievements, and contributions to the community.

A truly excellent conference, in content and in organisation. I had a wonderful time, and my head is buzzing with ideas and connections. My neural pathways have been exercised and reconfigured. I need to go home and process all this information further.

Next year in Lyon.

ALife day 4

ALife day 4. I’m at that point in conference-going where I keep having to check what day it is, as I’ve lost track.  Apparently it’s Thursday.  I never could get the hang of Thursdays.

This particular Thursday started brilliantly. Keynote speaker Randall Beer talked about “Autopoiesis and Enaction in the Game of Life”. Autopoiesis, or system self-production and self-maintenance, can be a slippery concept to explain. Beer takes the Game of Life, and uses it as a “toy” system, to get a handle on the concepts. The key is to look at the GoL from a process perspective (a toy “chemistry”), rather than from the more usual automaton perspective (the lower-level GoL toy “physics”). (This new modelling perspective is emergent under our definition, as it is actually a new meta-model.) In this different view, a glider can be seen as a very primitive autopoietic system, a network of processes constituting a well-defined identity that is self-maintained. In a marvellous tour de force, Beer showed how all the components fit together, and how GoL can be used to explain and illuminate concepts from autopoiesis in a beautifully clear and elegant manner.

The morning technical session was on Development (although not all the papers were). We started off with a discussion of the relationship between developmental encodings and hierarchical modular structure. Next; simulation is crucial for many ALife experiments, and MecaCell is one being built for developmental experiments. Then our paper; Bioreflective architectures generalise and combine the concepts of computational reflection and von Neumann’s Universal Constructor. Finally; it can be difficult to evolve heterogeneous specialist cooperative behaviours unless the specialists can recognise their partners.

The afternoon keynote was Francisco Santos talking about “Climate Change Governance, Cooperation and Self-organization”. This was an application of game theory in large finite populations to cooperation and coordination problems. He showed some counter-intuitive results: it is easier to get global cooperation via small groups initially, and it is better for small groups to invoke actions than to leave enforcement to a global organisation. In the end, the results show the old adage: think globally, act locally”, and that there is yet hope for cooperation.

I then went to the technical session on “Living technology and Human-Computer interaction”. First there were a couple of talks on the EvoBot, a modular liquid handling robot, covering both the hardware and the software. This system, being built as part of the EvoBliss EU project, is an open source design that costs two orders of magnitude less than current laboratory systems. It allows programmable chemical experiments, with precise, repetitive, complex operations. Real-time droplet identification allows complex operations to be specified. For example, it can be programmed to apply a droplet, wait for the droplet to start moving with a certain speed, then suck the droplet back up again; or to apply a chemical once an array of droplets has clustered. Next we learned about developing a computational agent to “play” a cooperative herding game with novice humans: some of the humans learned how to play from the agent, some never did, and most thought they were playing with another person. Finally we heard about a NetLogo-based approach to teaching school children about complex systems principles.

My brain is full, and there is still a day to go!