-
Models
A Physarum machine is a programmable amorphous biological computer,
experimentally implemented in the vegetative state of Physarum polycephalum (also
called slime mould) [
2
] that is a one-cell organism belonging to the species of
order Physarales, subclass Myxogastromycetidae, class Myxomycetes, and division
Myxostelida. The plasmodium of Physarum polycephalum spread by networks
can be programmable. The ability to perform useful computational tasks, in
propagating and foraging behaviour of the plasmodium, was rstly emphasized
by T. Nakagaki et al. (cf. [
7
]). In Physarum Chip Project: Growing Computers
from Slime Mould [
3
] funded by the Seventh Framework Programme (FP7), we
are going to construct an unconventional computer on programmable behavior
of Physarum polycephalum. The Physarum machine comprises an amorphous
yellowish mass with networks of protoplasmic veins, programmed by spatial
con gurations of attracting and repelling stimuli. The plasmodium looks for
attractants, propagates protoplasmic veins towards them, feeds on them and goes
on. As a result, a transition system is built up. Therefore, Physarum motions
can be treated as a kind of natural transition systems with states presented by
attractants and events presented by plasmodium transitions between attractants
[
2
]. We can de ne the following three basic forms of Physarum transitions
(motions): direct (direction: a movement from one place, where the plasmodium is
located, towards another place, where there is a neighbouring attractant), f use
(fusion of two plasmodia at the place, where they meet the same attractant),
split (splitting plasmodium from one active place into two active places, where
two neighbouring attractants with a similar power of intensity are located).
Formally, a transition system is a quadruple T S = (S; E; T; s0) [
8
], where
S is the non-empty set of states, E is the set of events, T S E S is the
transition relation, s0 is the initial state. Usually transition systems are based on
actions which may be viewed as labelled events. If (s; e; s0) 2 T then the idea is
that T S can go from s to s0 as a result of the event e occurring at s. A transition
system can be presented as a graph structure with nodes corresponding to states
and edges corresponding to transitions.
To program computation tasks for amorphous biological computers, we are
developing a new object-oriented programming language (cf. [
10
]). The proposed
language can be used for developing programs for Physarum polycephalum by
the spatial con guration of stimuli. This con guration of stimuli can be identi ed
with a low-level programming language for Physarum machines. To program
behavior of Physarum polycephalum, we have also proposed to use some
highlevel models, e.g., ladder diagrams, Petri nets, and transition systems [
9
].
We can consider some other operations (instructions) in Physarum machines
like: add node, remove node, add edge, remove edge [
2
]. Adding and removing
nodes can be implemented through activation and deactivation of attractants,
respectively. Adding and removing edges can be implemented by means of
repellents put in proper places in the space. An activated repellent can avoid
a plasmodium transition between attractants. Adding and removing edges can
change dynamically over time. To model such behavior, we propose to add
another high-level model, based on timed transition systems [
4
], to our language.
It is assumed, in transition systems mentioned earlier, that all events happen
instantaneously. In timed transition systems, timing constraints restrict the times
at which events may occur. The timing constraints are classi ed into two
categories: lower-bound and upper-bound requirements.
Let N be a set of nonnegative integers. Formally, a timed transition
system T T S = (S; E; T; s0; l; u) consists of an underlying transition system T S =
(S; E; T; s0) as well as a minimal delay function (a lower bound) l : E ! N
assigning a nonnegative integer to each event and a maximal delay function (an
upper bound) u : E ! N [ f1g assigning a nonnegative integer or in nity to
each event.
Let us consider a simple timed transition system shown as a graph structure
in Figure 1 with the following timing constraints: l(e1) = 0, u(e1) = 1, l(e2) = 0,
u(e2) = 1, l(e3) = 5, u(e3) = 10. The code in our created language has the
following form:
#TRANSITION_SYSTEM
s1=new TS.State("s1");
s1.setAsInitial;
s2=new TS.State("s2");
s3=new TS.State("s3");
e1=new TS.Event("e1");
t1=new TS.Transition(s1,e1,s2);
e2=new TS.Event("e2");
t2=new TS.Transition(s1,e2,s3);
e3=new TS.Event("e3");
e3.setTimingConstraints(5,10);
t3=new TS.Transition(s2,e3,s3);
The default timing constraints are 0 as a lower bound and 1 as an upper bound.
As a result of programming the Physarum machine, we obtain spatial con
gurations of stimuli presented in Figure 2, (a) for the time instant = 4, (b) for
the time instant = 8, where P is Physarum, As1 , As2 , As3 are attractants, and
R is a repellent. It is easy to see that the event e3 is allowed only if actual time
t 2 f5; 6; : : : ; 10g. Therefore, in the model in Figure 2 (a), a repellent, avoiding
the transition between states s2 and s3 as a result of the event e3, is present,
i.e., it is activated.
In a real-life implementation of Physarum machines, attractants are sources
of nutrients or pheromones, on which the plasmodium feeds whereas in case of
repellents the fact that plasmodium of Physarum avoids light and some
thermoand salt-based conditions is used. Repellents can be activated or deactivated for
proper time periods, especially in case of light.
Modelling dynamically changed structures over time is important in some
cases of abstract machines used in non-classical computations. One of them is a
Kolmogorov-Uspensky machine. In [
1
], there was shown that the plasmodium of
Physarum polycephalum is a biological substrate that implements a
KolmogorovUspensky machine (at the beginning called a Kolmogorov complex) - a concept of
an abstract machine de ned on a dynamically changing graph-based structure
outlined by A.N. Kolmogorov and V.A. Uspensky [
5
], [
6
]. The
KolmogorovUspensky machine is a process on a nite undirected connected graph with
distinctly labelled nodes. A computational process travels on the graph, activates
nodes and removes and adds edges. There is only one active node at any step of
development.
Acknowledgments
This research is being ful lled by the support of FP7-ICT-2011-8.