SKI# is a Turing complete, language for programming in the aTAM model. A compilation technique provides a mapping from SKI# into finite sets of DNA Tiles that self-assemble in the aTAM model. Though such sets are always finite, the number of Tiles may be relevant, the construction of the Tiles may be heavy and the self-assembly can produce wrong molecular growth. In this paper we discuss the construction of a DNA Universal Machine as an aTAM interpreter for the entire Combinatory Logic, comparing it with the compiler based approach. Finally, Consensus is considered as a case study in distributed programming in the aTAM model and a further step in the design of SKI# and in the expressivity of aTAM (Wang Tiling) compared to Combinatory Logic and π-calculus.
!"#$% !!!!!!!!!!!!!!!"#$%&$%#%&'! % &$%% #$% %&%
#%
%
%
!"&$%
%
%
other formalisms have been studied for providing languages for programming
Self-Assembly of DNA Tiles. Given any computable problem, these languages
must provide a development environment for formalizing a solution to the
problem and obtaining an aTAM program that Self-Assembles the Tiles according
to such a solution. In [
Introduction Tiles
! !
! a3 Application Fold Tiles a1 a2 a3 a1a2 "* a3 ! a2 ! a2 "* a4 ! a4
Terminal Tiles
a2 !
! ! a2 "* a2*
Application Unfold Tiles a2
a2 a1
a4 ! a3 a4 a3 a3 a1 "* a3a4 a1a2 "* a3a4 a1 "* a3a4 Connections Tiles a1 !
a4 !
! a1
a3 a1 "* a3 a1
a4 ! ! a1 "* a4 a2 a4 !
! a2 "* a4
SKI# leads to the definition of a language of Tile, SKI-Tile, that has the 5
kinds of Tiles of Figure 2, and each kind is designed to support the emulation of
combinatory reduction. In [
A DNA Universal Machine for Combinatory Logic In this section we describe the definition of a DNA Universal Machine for the programs of the entire Combinatory Logic, including SKI#. The machine consists in a Turing Machine that interprets combinatory programs, and is expressed as an aTAM system (program).
The full machine is too complicated to be presented in this paper, hence we
show a simplified version in which the input combinatory term does not contain
brackets. Such a simplification allows to understand the fundamentals of the
interpretation process, without getting lost in complicated details for dealing
with combinators having non atomic arguments. Following [
The Structure of SKI-TM The machine M we define is such that Γ = {S, K, I, }∪X ∪Π∪{$, ↓, , S, K, I(, )}, F = {Halt}, δ is defined in Table 2,3,4,5,6. The other components can be derived from Table 2,3,4,5,6, in particular the set of states Q. The initial tape of M is assumed to be constituted of blank symbols except for a finite sequence. The sequence is supposed to consist of the combinatory program to be reduced, in left associative form, LAF, (without brackets) and delimited by symbol $ (on both sides). Table 1 defines the tape syntax. C are the combinator symbols (we consider only the main combinators), V are constant and variable symbols, D are all SKI symbols and M are markers. Markers include the blank symbol , but do not include $ since this symbol cannot appear in the sequence2 Initially the machine is in Start and the head is pointing immediately after the leftmost symbol $. The notation for the rules resorts to the use of set expressions defining a finite set of symbols. A set expression has the form e1 . . . ek (k ≥ 1), where ei is either a single symbol of D ∪ M ∪ {$} or the letters c or v. Each single symbol stands for the singleton containing itself, while c stands for the set {S, K, I} and v for V. Finally, the set expression e1 . . . ek stands for the set union of the sets denoted by e1 . . . ek. Hence rule (TK, cv) → (TKa, cv, R) in Table 3, is expressing the set of rules {(TK, u) → (TKa, u, R) |∀u ∈ D}. Set expressions are also used in expressing set of states. For instance TSc : cv is expressing any state in the set {TSu | u ∈D}. As a matter of fact the rule (TSc : cv1, cv() → (TSc : cv1, cv(, L), in Table 5 stands for the set of rules:
(TSu1, u) → (TSu1, u, L) ∀u1 ∈ D ∧ u ∈ D ∪ {(}
2 Round brackets are included since though our assumption on the form of the input
program, non atomic arguments are introduced during reduction of combinator S.
Quintuples looking f or a K redex
(TK, $) → (FF, $, L) (Attempt f ails)
(TK, ) → (TK, , R) (Skip blanks)
(TK, cv) → (TKa, cv, R) (1st arg has been read)
(TKa, $) → (FF, $, L) (Attempt f ails)
(TKa, ) → (TKa, , R) (Skip blanks)
(TKa, cv) → (TKaE, , L) (Reduction 2nd Atomic arg)
(TKaE, cv )() → (TKaE, cv )(, L) (going back to K )
(TKaE, K) → (Start, , R) (M arker K is deleted)
Quintuples looking f or an I redex
(TI, $) → (FF, $, L) (attempt f ails)
(TI, ) → (TI, , R) (Skip blanks)
(TI, cv) → (TIE, cv, L) (arg has been f ound)
(TIE, ) → (TIE, , L) (Skip blanks)
(TIE, I) → (Start, , R) (M arker I is deleted)
Blank insertion is omitted
(TS, cv ) → (BKStart, cv , L) (A redex is f ound)
(BKend, cv) → (TSa, cv, R) (F irst argument f ound)
(TSa, ) → (TSb, ↓, R) (Insert marker f or third argument)
(TSb, cv) → (TSb : cv, (, R) (Substitute second argument with()
(TSb : cv, ) → (TSbc, cv, R) (Rewrite second argument af ter()
(TSbc, cv) → (TSbc1, cv, R) (T hird argument f ound)
(TSbc1, ) → (TSbc2, ), L) (Insert ) af ter third argument)
(TSbc2, cv) → (TSc : cv, cv, L) (Go lef t to marker f or the third argument)
(TSc : cv1, cv() → (TSc : cv1, cv(, L) (Skip second argument and ()
(TSc : cv, ↓) → (TSS, cv, L) (Substitute marker with third argument)
(TSS, cv) → (TSS, cv, L) (Skip f irst argument)
(TSS, ) → (BSend, , L) (Skip blank)
(BSend, S) → (Start, , R) (Delete marker f or S combinator)
The rules in Table 5 deal with the S-redex. In this case, the redex is firstly
transformed (by inserting/shifting #) into a more convenient form, then the
reduction applies to that form. Let ω $ uk S i a j b h c m un $ ω be
a the tape and S i a j b h c be the leftmost S-redex to be reduced. The
transformation modifies the tape into ω $ u˜k S a b c u˜n $ ω, where the
arguments of the S-redex are separated by exactly 1 blank symbol and u˜k and
uk are the same sequence provided that symbols are ignored. State BKstart
starts the transformation which ends in state BKend (if a S-redex is effectively
found. Otherwise, it ends in the state FF to deal with failure). Eventually, Table
5 contains the rules for computing the S-redex of the transformed form and omit
the rules of the transformation. The rules in Table 6 are concerned with the
state FF that deals with failures in the search of a redex and is responsible for
elimination of markers introduced in the attempt of reduction.
To use M , we need to compile it into a program (i.e. a DNA Tile system) for
aTAM. It can be accomplished (at least in principle) by using the technique
introduced in [
>8%'&?! "#! "#($!
"! >.%'&?! "! $! "#($!
"+! ,!
We conclude this section noting that a different way exists for implementing
SKI-TM in aTAM. It consists in compiling a Universal Turing Machine and then
provide for the encoding of SKI-TM into the program representation of such a
machine. This way is particularly interesting in view of [
Pros and Cons of M compared with SKI# and its compiler Even if the compiler for SKI# has some remarkable aspects, its use has also, some practical limitations which include: – Deterministic growth. Since M uses a specific (complete) reduction strategy, the grid grows deterministically using M . The same does not hold for the use of the compiler. Even limiting the set of the redex-reductum pairs to those of the outermost redexes we may have a pair that applies to a non-outermost redex of an intermediate reduced term; – Construction in aTAM, of all the Tiles in the object finite set. M requires always the same set of Tiles. In SKI#, the number of different Tiles depends on the specific program. – Reuse and/or modification of programs. M requires always to change the Tiles of the first row of the grid. SKI# programs are function applications hence when the input changes the program must be re-compiled. However the new Tile set may have a relevant set intersection with the previous application. – Errors due to the violation of the grid property. The computation grids of
M do not need grid property. – Control of the shape of the computation grid. The computation grid, in M , is very far from the source program and contains symbols of the emulator. In the computation grids of SKI# the Tiles contain only terms of the source programs.
– Expressivity. M has the expressivity of CL, whilst SKI# of a subset of CL. 4
Consensus in DNA Tile Self-Assembly
Starting from the definition of Consensus in DNA Tile Self-Assembly, we
consider distributed computation, extend our approach mixing SKI calculus with
process algebras, introduce an alternative compilation of SKI# into SKI-Tile.
We introduce and discuss it through the example of the algorithm of consensus
[
In distributed computing, Consensus is the well known problem in which a
fixed number of agents require to agree on 1 among a finite set S of values.
In the version of [
P(c) := cp.c(x).P (c, x) + c(x).cp.P (c, x)
P (c, x) := [x = p]P(c) + [x = n]U(c) + [x = u]P(c) N(c) := cn.c(x).N (c, x) + c(x).cn.N (c, x)
N (c, x) := [x = p]U(c) + [x = n]N(c) + [x = u]N(c) U(c) := cu.c(x).U (c, x) + c(x).cu.U (c, x)
U (c, x) := [x = p]P(c) + [x = n]N(c) + [x = u]U(c)
A(c) := P(c) | . . . | P(c) | N(c) | . . . | N(c) | U(c) | . . . | U(c) where, capital case symbols {P, P , N, N , U, U } are names for process definitions, all lower case symbols {p, n, u} are names for process links/channels, finally x is the only variable symbol. P+Q is the choice operator, P|Q is distributed operator, [x=y]P is match operator, P:=Q is recursive process definition. Since it uses a finite set of values, a re-formulation of A(c) in the system B below, can be obtained. System B consists in a syntactic transliteration of A(c) which introduces 3 distinct channels for sending and receiving, and can execute without resorting to the variable substitution mechanism.
P := pp.P + np.U + up.P + p(x).P + n(x)U + u(x)P N := pn.U + nn.N + un.N + p(x).U + n(x)N + u(x)N U := pu.P + nu.N + uu.U + p(x).P + n(x)N + u(x)U
B := P | . . . | P | N | . . . | N | U | . . . | U The use of distinct channels allows an instantaneous state transition of both the agents at each communication of an agent pair (the formulation B required two distinct communications in sequence). Figure 6 contains a first (uncompleted) formulation in DNA Tile of system B. Each process is expressed by 6 different Tiles, one for each of the 6 terms occurring in the + expression defining a process in system B. In Figure 6, the east side of the tile is assumed to be used for receiving whilst the west side for sending. This results into an asymmetry in the communication of the agent pairs (which is not present in the latter πformulation), in addition the computation grid of the aTAM model is too rigid in ”selecting” the tiles to be considered for the grid growth (in contrast to the terms of a | expression which can be coupled in any way). Figure 7 contains the additional Tiles that a process requires to get in contact with any process in the system and arbitrarily positioned in a column of the computation grid.
Proving equivalence between the π-calculus formulation of system B and its formulation in aTAM is out of the scope of the paper. However, we have shown lines along which we can pass from algebraic formulations of some distributed systems to the DNA Tiles for the execution of such systems by self-assembly in ncpm
P U (P2) PU UU2 (P5) np ! ! up
P P (P3) P P (P6) up ! P := p*p.P + n*p.P + u*p.U + p(x).P + n(x).U + u(x).P N := p*n.U + n*n.N + u*n.N + p(x).U + n(x).N + u(x).N U := p*u.P + n*u.N + u*u.U + p(x).P + n(x).N + u(x).U
B = P | ... | P | N | ... | N | U | ... | U the aTAM model. Figure 7 shows on its right part, the behavior of 3 contiguous agents in a computation grid of the consensus system.
! pxn !
pxu P N (P7)
P nxp !
U N (P8)
P U (P9)
P uxp !
U (P10) !
! P P (P0) … P
U
N P9 U1 P6 P0 P2
P? U? … … …
U10 N0
N0 N5 U? … … …
We conclude the paragraph, recalling that concurrent computation is a mix of
distributed and parallel computation. Since the structure of programs (namely,
finite sets of DNA Tiles) and the properties of the basic computation mechanism
(namely, Tile self-assembly in a grid), the aTAM model copes with distributed
computation but it is a sequential computation model. This limitation is the
result of various considerations on some bio-chemical aspects of DNA molecular
interactions [
Conclusions
The paper introduced an aTAM Universal Machine for CL. Apart from the
interest in itself, its use is compared with the one of the language SKI# and of its
interpreter [