=Paper=
{{Paper
|id=None
|storemode=property
|title=DNA Tiles, Wang Tiles and Combinators
|pdfUrl=https://ceur-ws.org/Vol-1032/paper-01.pdf
|volume=Vol-1032
|dblpUrl=https://dblp.org/rec/conf/csp/BelliaO13
}}
==DNA Tiles, Wang Tiles and Combinators==
https://ceur-ws.org/Vol-1032/paper-01.pdf
DNA Tiles, Wang Tiles and
Combinators
Marco Bellia and M. Eugenia Occhiuto
Dipartimento di Informatica, Università di Pisa, Italy
{bellia,occhiuto}@di.unipi.it
Abstract. In this paper we explore the relation between Wang Tiles and
Schonfinkel Combinators in order to investigate Functional Combinators
as an programming language for Self-assembly and DNA computing.
We show: How any combinatorial program can be expressed in terms of
Wang Tiles, and again, how any computation of the program fits into a
grid of tiles of a suitable finite, tile set, and finally, how a program for
Self-assembly DNA computing can be obtained. The result is a general
methodology that, given any computable function, allows to define a
Self-assembly program that can be used to construct the computations
of the function
1 Introduction
In the last decade, one of the emerging approaches [1] to DNA Computing, is
Self-Assembly [2]. It describes a computation in terms of a process in which
small components, autonomously and automatically, assemble into larger, more
complex, structures [3–5]. The assembly is based on the Watson-Crick comple-
mentary law and is effectively governed by various bio-chemical techniques [6].
However, in terms of computable functions, in the Self-Assembly computation
process, it is possible to recognize:
(a) The computed application. The computed application is expressed by the
small components to be assembled. In particular, these components include
a representation for the function arguments, if any, i.e. the inputs of the
application, and a representation for the function to be applied.
(b) The computation. The larger and more complex structures, that result at
the end of the SelfAssembly process, form the effective computations. Each
of such structures can be read as the complete trace of a computation, from
its start to its end.
Various kinds of DNA Tiles has been introduced, in the years, in the various
proposals, to be used as the small components of point (a) [7, 8]. In [9] the
relation between DNA Tiles (TX, triple crossover, molecules) and Wang Tiles
has been used to show how to simulate finite state automata with output, i.e. a
transducers, in Wang Tiles. Moreover, by using compositions of transducers and
the relation with Wang Tiles, [9] shows how the computation of general recursive
2 M. Bellia, M. E. Occhiuto
functions can be expressed using self-assembly. This allow to use the formalism
of general recursive functions as a programming language for DNA computing.
With the same aims, [10] introduced DSL as language for programming with the
DNA Tiles of the aTAM model [11].
In this paper we explore the relation between Wang Tiles [12] and SKI combi-
nators [13, 14] in order to investigate Functional Combinators [15, 16] as an High-
/Intermediate level, programming language for Self-Assembly computations. The
result is the definition of a language for Self-Assembly, SKI-Tiles, and of a general
methodology that, given any computable function, allows to define a program, in
SKI-Tiles, that compute each application of the function, by using Self-Assembly
computations.
2 Wang Tiles
Wang Tiles [12] were introduced in 1961. It is a formal system based on the notion
of tile. A tile may be graphically represented by a unit square with colored sides
from a (possibly, denumerable) set T of distinct colors. Figure 1.a shows the
form of a tile such that: West side has color T1 , north has color T2 , south has
color T3 and east has color T4 . Tiles must be arranged side by side on the plane
(computation grid) in a way that adjacent tiles must have the adjacent side of
the same color, see Figure 5: We will name this operation Wang-arrangement.
The interest is on the set F of all the finite sets of distinct tiles: What tile sets of
F, can cover the infinite plane by using Wang-arrangement on copies of the tiles
of the set, obtained by translation (no rotation, no reflection). In 1963, Wang
showed that to each Turing Machine M corresponds a finite set TM ∈ F such
that the computation of M on a tape D can be emulated by a covering, with the
(copies of) tiles of TM , of a plane containing an initial row of tiles that describes
D. Finally, Wang proved that the halting problem of Turing Machines can be
reduced to the undecidability, for finite tile sets, of covering the infinite plane.
T2
T1
T4
T3
a.
Wang
Tile:
A
unit
square
with
the
colored
b
y
T1,
T2,
T
3,
T4
sides
b.
DNA
Tile:
4
strands
of
DNA,
T1,
T2,
T3,
T4,
are
kept
together
by
a
suitable
DNA
structure,
Z.
Fig. 1. Wang Tiles and DNA Tiles
DNA Tiles, Wang Tiles and Combinators 3
3 SKI Combinators
3.1 The monoid SKI
SKI Combinators [14] is a formal system that expresses all the computable func-
tions1 without requiring any (bound) variable and by using only one operation:
the monadic, functional application. Hence, it is the monoid2 Σ, below:
Σ = S|K|I|Π|X|ΣΣ
where the application is represented by juxtaposition of a (left) term, repre-
senting a monadic function, to a the (right) term, representing the argument.
Currying, higher order functions, and left associativity of application are pro-
vided for non-monadic functions. The symbols S, K, I are combinators (but other
ones could be added in [15]), X is a set of (free) variable symbols, Π is a set of
constant symbols. The terms of Σ are also called combinatorial terms, and the
terms built by using the application operator, namely those in ΣΣ, are called
(combinatorial) application term. Combinators obey to the following application
laws, for a, b, c ∈ Σ:
I a == a
K a b == a
S a b c == a c (b c)
3.2 Bracket Abstraction and Bound Variables
The combinators S, K, I express the bracket abstraction in the following way
(other characterizations are in [15]). Let a ∈ Σ be any term, possibly containing
a (free) variable x ∈ X. Then, we define the bracket abstraction of a ∈ Σ with
x, written [x]a, be the term b ∈ Σ such that: b x = a. Such a term3 always exists
in Σ and can be obtained by using the following rules:
[x]x = I
[x]u = Ku, for u ∈ {S, K, I} ∪ Π ∪ X and u 6= x
[x](a b) = S([x]a)([x]b)
Hence, all the closed terms of the calculus are all the terms of Σ that do not
contain variables.
3.3 Program, Computation, Recursion
Noting that in the application ΣΣ, there is no distinction between the terms that
are functions (driving the computation to be done) and those that are arguments
(forming the values). Any term becomes the function to be applied, when it is
1
in its original formulation, in 1924, by Moses I. Schonfinkel, [13], the combinator
”I”, which could be expressed through SKK, was replaced by the combinator ”U”,
in order to express first order predicates without the use of bound variables.
2
Also Wang Tiles is a monoid, on Tiles as terms, with Wang-arrangement as the only
operation
3
moreover, for all terms c ∈ Σ, we have b c = a[x ← c], i.e. b behaves like one λ-
abstraction and when applied to c reduces according to Church’s β-axiom [17]
4 M. Bellia, M. E. Occhiuto
in the left side, whilst it behaves as a value when it is in the right side of the
application. A (combinatorial) program is any term of Σ. A program computes
according according to the application laws of the SKI calculus. In order to
obtain a notion of computation, we can encapsulate the application laws into
the reduction system obtained by the binary relation on combinatorial terms,
→, defined in the following way. Relation → is called combinatorial reduction.
Definition 1 (→∗ ). Relation →∗ is the reflexive and transitive closure of →∗ .
I a == a K a b == a S a b c == a c (b c)
Ia→a Kab→a S a b c → a c (b c)
a → a’ b → b’
a b → a’ b a b → a b’
Given a program a, a computation of a is any sequence, for n ≥ 04 :
a → a1 → ... → an
Whenever an is such that for no b ∈ Σ, an → b, then we say that: Program a has
one terminating computation; a → a1 → ... → an is a terminating computation
of a; Program a computes an , or equally, an is the ”value” computed by a.
Relation → has Church-Rosser confluence property, since if a → a1 → ... → an
is a terminating computation of a then an ≡ bm for any other terminating
computation a → b1 → ... → bm [18]. However, Σ contains nonterminating
programs. As a matter of the fact consider the term Ψ of Definition2.
Definition 2 (The Kleene fixed-point combinatorial program calcula-
tor, Ψ ). Let R ≡ S(S(KS)(S(KK)I))(K(SII)). Then, Ψ ≡ SRR is a combi-
natorial program. Moreover, Ψ is such that, for all pairs of terms G, a ∈ Σ, the
following holds:
(*) Ψ G a ≡ G (Ψ G) a
The proof of (*) is a trivial exercise. Ψ points out the elegance with which Schon-
finkel monoid expresses the computable functions. In particular, Ψ introduces
recursively defined terms on one hand, and computes the least fixed point of
them, on the other hand. However, in Section 6, we use term equations for deal-
ing with recursive definitions, because Self-assembly computation has a notion
of term replacement that already support recursive definitions.
4 The Approach
We start introducing the structures and the properties that the Wang tiles must
have in order to be used for expressing the combinatorial terms and their com-
putation. Then, we show how to use such structures in order to get the definition
and the computation of any combinatorial program.
4
Obviously, n = 0 means that for no b ∈ Σ, a → b
DNA Tiles, Wang Tiles and Combinators 5
4.1 SKI-Tiles: A formalism of Wang Tiles for combinatorial
programs
The colors that may occur in the tiles, are the combinatorial terms (of Σ):
Different terms are different colors. In addition, a special color ♠ is used for
combining the terms within a tile and for arranging the tiles in the computation
grids. The sides of a tile may be colored with an input (i.e. the right part of an
application term) or with a function (i.e. the left part of an application term)
or with an output (the result of an application) or finally, with a connection
term (which allows to arrange together distinct tiles and distinct parts of the
computation grid). When more different colors occur in a tile, their arrangement
in the tile sides obeys properties based on the combinatorial reduction. According
to how colors are used in the tile sides, the tiles fall in one of the following five
classes, shown in Figure 2.
– Introduction Tiles are the tiles that introduce the components, namely
function and arguments, see Figure 2, of the computation to be made. These
tiles may occur in the top line of a computation grid. No, specific, property
is required to the color used in the tile.
– Terminal Tiles are the tiles that collect the result of a computation, see
Figure 2. These tiles may occur in the bottom line of a computation grid.
No, specific, property is required to the color used in the tile.
– Application Fold-tiles deal with the reduction of applicative terms that
do not require any reduction on their subterms. Color T1 is used for the
function, color T2 for the argument, whilst colors T3 or T4 for the reduced
term: It obeys the properties that are indicated at the bottom of the tile in
Figure 2.
– Application Unfold-tiles deal with the reduction of applicative terms that
require some subterm reduction. Color T1 is used for the function and color
T2 , if any, for the argument, exactly as in the fold-tile s, but the reduced term
is an application T3 T4 . This tile structure allows to use two distinct tiles,
one for reducing the color T3 and one for reducing the color T4 , separately.
Constraints on the colors are indicated at the bottom of the tile in Figure 2.
– Connection Tiles they furnish tiles that are suitable to connect different
parts of the computation grids and in some cases they may involve simple
term reductions. Constraints on the colors are indicated at the bottom of
the tile in Figure 2.
4.2 Soundness of SKI-Tiles
Apart from the introduction and the terminal tiles, all other tiles of SKI-Tiles,
are combinatorial term reductions of →∗ . The Wang-arrangement operation cor-
responds to the (reflection and) transitivity of →∗ . Hence, computation grids
contain only sound reductions on the combinatorial terms that are involved in
the tiles, and in particular from the terms of the introduction tiles up to the
term of the terminal tile of the grid.
6 M. Bellia, M. E. Occhiuto
Introduction Tiles Terminal Tiles
♠ T2
♠ ♠ ♠ ♠
T3 ♠
Application Fold Tiles Application Unfold Tiles
T2 T2 T2 ♠
T1 ♠ T1 T4 T1 T4 T1 T4
T3 ♠ T3 T3
T1T2 →* T3 T1T2 →* T4 T1T2 →* T3T4 T1 →* T3T4
Connections Tiles
T2 ♠ ♠ T2
♠ T4 T1 ♠ T1 T4 ♠ ♠
♠ T3 ♠ T4
T2 →* T4 T1 →* T3 T1 →* T4 T2 →* T4
Legenda. T1, T2, T3, T4 are colors for combinatorial terms; →* is the reflexive, transitive closure of
the combinatorial reduction.; The colors must obey the property, if any, that is put below the tile.
Fig. 2. The classes of tiles of SKI-Tiles for the Combinatorial Terms
4.3 The Computation Grids of S, K and I in SKI-Tiles
The combinators are completely defined in the Wang Tile formalism by the
computation grids in Figure 3, for I and K, and in Figure 4, for S. The grid for
I consists of only one fold-tile that switches the input on the output. The grid
for K consists of 4 tiles: The tile on the left top corner is a fold-tile that collects
the first argument and has ”a” as output. The tiles on the right top and the left
bottom corners are connection tiles. They are used for connecting the fold-tile
on the bottom right corner of the grid. The latter tile contains, as output, the
output of the grid. Actually, for S we give two grids of 9 tiles: Both are correct.
The two grids differ for the tile on the right bottom corner. Both contains the
same fold-tile on left top corner, and the same 7 connection tiles. The other tile
is a fold-tile in the left grid, whilst it is an unfold-tile in the right one. The choice
of the right grid may depend on the input terms, if a and b do not require any
reduction then the left grid may be the best grid to be used. The grids in Figure
DNA Tiles, Wang Tiles and Combinators 7
a
b
a
K
♠
♠
♠
I
♠
Ka
b
a
Ka
b
♠
Ka
Ka
♠
I
a
=
a
♠
a
K
a
b
=
a
Fig. 3. The computations of K and I in the SKI-Tiles formalism
3, and in Figure 4 are defined for being used as grid components, hence do not
contain any introduction or terminal tile.
Theorem 1. The SKI calculus can be expressed in Wang Tiles
Proof. The proof is easily obtained by induction on the pure combinatorial terms
(i.e. Σ−(Π+X)) and by using suitable grid compositions. The extension to the
entire Σ comes immediately since each symbol in Π+X is an uninterpreted
symbol.
The Theorem above is not surprising since Wang’s result [12], but the theo-
rem furnishes a constructive proof and a concrete way to do it. The next section
shows how the approach effectively applies in a computation.
5 Applications and Examples
The section shows how the approach effectively applies in a computation. Con-
sider the function P roj24 that selects the second argument, from a sequence of
four arguments. We write a program that, given four arbitrary terms, c1 , c2 , c3 , c4 ,
as inputs, computes c2 as output. In combinatorial programming, the program
can be obtained two different ways, according to a use of combinatory program-
ming as an intermediate level or as a higher level programming language. We
consider both view and for each of them we show the corresponding computation
grid in the tile formalism of the previous section.
5.1 Combinatorial programming at an Intermediate Level
This way of programming is widely influenced by the use of combinators in the
implementation of functional languages [19]. In order to obtain a combinatorial
term for P roj24 , we start giving a formulation of P roj24 in a functional language.
In this case, we can express it by the lambda term:
8 M. Bellia, M. E. Occhiuto
a
b
c
a
b
c
S
♠
♠
♠
♠
♠
S
♠
♠
♠
♠
♠
Sa
b
c
Sa
b
c
Sa
b
c
Sa
b
c
♠
Sa
Sa
♠
♠
♠
♠
Sa
Sa
♠
♠
♠
♠
Sab
c
♠
Sab
c
♠
Sab
c
♠
Sab
c
♠
♠
♠
Sab
Sab
♠
♠
♠
♠
Sab
Sab
bc
♠
♠
ac(bc)
♠
♠
ac
S
a
b
c
=
a
c
(b
c)
Fig. 4. Two different computations of S in the SKI-Tiles formalism
λ x1 .λ x2 .λ x3 .λ x4 . x2 .
Then, by using the technique for removing bound variables from lambda terms5 ,
we obtain the combinatorial term:
K(S(KK)(S(KK)I)).
Eventually, we have the combinatorial term T and its computation grid, in
Figure5.
5.2 Combinatorial programming at an High Level
This way of programming uses the possibility of introducing new combinators
and super combinators [16] in order to obtain a more expressive and neat solu-
tion to a possibly, more general problem than the given one. In this case, the
problem may be solved by using a family, P roj = {fn : Dn → D}, of curried
functions, each function being indexed by the arity. We can express each func-
tion of P roj by the following combinatorial term: Tp = K i−1 (W IK n−i ), where
n is the arity of fn , 0 < i ≤ n is the position of the argument to be selected, I
is the corresponding combinator of SKI calculus. Finally, K m g = K(K m−1 g) is
a variant of combinator K (for m > 1), whilst W is an additional combinator
that obeys the following application law: W abc = b(ac). Then, the combinatorial
program is now expressed by T = (((K(W IK 2 )c1 )c2 )c3 )c4 , and its computation
grid can be obtained by using the same methodology of Section 5.1.
5
it roughly corresponds [15, 19] to the computation of [x1 ]([x2 ]([x3 ]([x4 ]x2 )))
DNA Tiles, Wang Tiles and Combinators 9
6 Self-assembly Computations with SKI-Tiles
This section discusses the formalism of SKI-Tiles in the context of the Self-
Assembly programming and extends the formalism with the notions of program
and of computation of the Self-Assembly programming paradigm.
6.1 Wang Tiles vs. Self-Assembly
Wang Tiles and Self-Assembly share the same fundamental operation for con-
necting the tiles: Wang-arrangement. Nevertheless, there is a subtle but relevant
♠ ♠ ♠ ♠ ♠ ♠
♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠
T4 c1 c2 c3 c4 ♠
T4 c1 c2 c3 c4 ♠
♠ T4 T4 ♠ ♠ ♠ ♠ ♠ ♠ c4 c4 ♠
♠ T5 c2 c3 ♠ c4
T = T1c4
♠ T5 c2 c3 ♠ c4
T1 = T2c3
c3 c3 ♠
T2 = T3c2 ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠
T3 = T4c1 ♠ T5 c2 ♠ c3 c4
T4 = KT5 T5 c2 c3 c4
♠ ♠
T5 = ST6T7
♠ ♠ ♠ T5 T5 T 7 c2 T 7 c2 ♠ ♠ ♠ ♠ ♠
T6 = KK
♠ ♠ T 6 c2 Kc2 c3 c4
T7 = ST6I
Subterms ♠ ♠ T 6 c2 Kc2 c3 c4
♠ ♠ ♠ ♠ ♠ K K ♠ ♠ ♠ ♠ ♠
♠ ♠ ♠ T8 c3 c4
♠ ♠ ♠ T8 c3 c4
T4,c1,c2, c3,c4, ♠ ♠ ♠ ♠ ♠ ♠ ♠ T8 T8 ♠ ♠ ♠
T5,T6c2,T7c2, ♠ ♠ ♠ ♠ Kc2 c4
Kc2,T8=K(Kc2)
♠ ♠ ♠ ♠ Kc2 c4
Specific Colors
♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ Kc2 Kc2 ♠
♠ ♠ ♠ ♠ ♠ c2
♠ ♠ ♠ ♠ ♠ c2
♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠
♠ ♠ ♠ ♠ ♠ ♠
Fig. 5. The computation grid of T = (((K(S(KK)(S(KK)I))c1 )c2 )c3 )c4
10 M. Bellia, M. E. Occhiuto
difference. The Wang formalism neither has a notion of program nor of com-
putation: The aim is the construction of some computation grid that must be
assembled with the tiles of a given tile set. Differently, Self-assembly is a pro-
gramming paradigm with a notion of program, semantics and computation, that
consider all the grids that can be assembled by applying Wang-arrangement to
the tiles of the program.
6.2 The SKI-Tiles language for Self-Assembly programming
The section formalizes the notions of program and of computation in order to
make SKI-Tiles a language for Self-Assembly programming. Then, it introduces
a (combinatorial) formulation of conditional, booleans and numbers for the use
of programs, for arithmetic programming, in SKI-Tiles.
Chemical Context Let H ≡ {T, g, τ } be triple defining the physics of molec-
ular self-assembly [5] of the programs. We assume that for all programs, the set
of color T , the binding strength function g and the temperature parameter τ are
chosen in a way that Wang-arrangement can apply always and only when the
tiles abut on sides that are colored by a same color.
Programs. A program is a finite sequence of quadruples of the form (T1 , T2 , T3 , T4 ).
The use of quadruples introduces a convenient, linear notation for tiles [4], in
particular the quadruple (T1 , T2 , T3 , T4 ) corresponds to the tiles in Figure 1 pro-
vided that T1 , T2 , T3 , T4 are colors of the SKI-Tiles formalism.
Semantics. Let P be a program. The semantics of P is the set of all sound
computation grids that can be obtained from P by τ -stable derivation.
Seed and τ -stable Derivation. Let P be a program. Let s be the seed tile of
A0 , i.e. the only tile of the grid A0 . Then, A0 →P ... →P An is a computation.
Moreover, →P is the τ -stable Derivation (of P in H) and is such that A →P B
if and only if B is obtained from A by Wang-arrangement, with a (copy of a)
tile of P, which satisfies the chemical context H.
Sound Computation Grid. Unfortunately, the Wang-arrangement does not
always produce meaningful computation grids when unfold tiles are admitted.
Hence, a computation grid is said sound if and only if the property hold:
– The topmost row contains only introduction tiles and only one of them, the
seed, has color T3 6= ♠, and
– The bottom row, if any, contains only terminal tiles and only one of them
has color T2 6= ♠, and
– The leftmost column, if any, contains only tiles with a ♠ as east side, and
– The rightmost column, if any, contains only tiles with a ♠ as west side, and
– No unfold-tile occurs in the grid, or
– The unfold-tiles satisfy the sub-grid property.
DNA Tiles, Wang Tiles and Combinators 11
Definition 3 (Quasi-grids.). A quasi-grid is a n×m grid of tiles with n, m > 1
and such that: The tiles of the first column, exception for the top tile, have a ♠
as west side; The tiles of the first raw, exception for the leftmost one, have a ♠
as north side; The tiles of the last column, exception for the bottom tile, have
a ♠ as east side; Finally, the tiles of last raw, exception for the rightmost one,
have a ♠ as south side.
Definition 4 (Sub-grid Property.). Let G be a computation grid and A be
an unfold-tile of G. Then A satisfies the sub-grid property if A is the left top
corner of a quasi-grid of G.
It is worth noting, that the unfold-tiles involve the reduction of combinatorial
terms of the form a b with the aim of reducing, firstly, a to some a0 and b to some
b0 , separately, and then, of reducing a0 b0 . Hence, this leads to a sub-computation
that behaves like a quasi-grid. As an example, the tile A ≡ (T5 , c2 , T6 c2 , T7 c2 )
(4th tile from the top, of the 3rd column, from the left) of computation grid in
Figure 5, is an unfold-tile which satisfies the sub-grid property: In particular,
the tile is the left top corner of a quasi-grid of 4 tiles. Moreover, even if the tile
B ≡ (T7 c2 , c3 , c2 , ♠) was in the program, the sub-grid property would forbid to
put it on the east side of A, i.e. the replacing of (T7 c2 , ♠, Kc2 , ♠) with B.
Booleans, Conditional, Numbers in Functional Programming. We list
some usefull functional structures for arithmetic calculus, including Barendregt
numbers [17] and use them in writing arithmetic programs in functional pro-
gramming6 :
– T rue ≡ λx.λy. x
– F alse ≡ λx.λy. y
– Conditional is implicitly expressed by T rue and F alse
– P air ≡ λx.λy.λz. z x y
– The number 0 is [0] = P air T rue (P red [0]) 7
– The successor of n is [n + 1] = P air F alse [n], for n > 0
– Program for Test on 0: Zero = λx. x T rue
– Program for Predecessor: P red = λx. x F alse
– Program for Addition: Add = λx.λy. (Zero x) y (P air F alse (Add (P red x) y))
– Program for Product: P rod = λx.λy. (Zero x) x (Add (P rod (P red x) y) y)
– Program for Factorial: F act = λx. (Zero x) [1] (P rod x (F act (P red x)))
Additional Combinators for SKI-Tiles This section extends the set of com-
binators, to include some combinators, C, B, P , that are of general use in com-
binatorial programming [15], and some other that are convenient in expressing,
in SKI-Tiles, the programs listed above.
6
We use λ-notation to express the terms: In particular application is term juxta-
position, is left associative, and has precedence on abstraction. Finally, recursive
definitions use equations of the form x = E, where E is an abstraction and x is a
functional variable that cannot occur bound in E
7
In the original formulation [17], [0] is P air T rue F alse. Here, we extend the domain
of the numbers with the undefined value, P red[0].
12 M. Bellia, M. E. Occhiuto
– Left application combinator is B: B a b c == a c b
– Right application combinator is C: C a b c == a (b c)
– Combinator for Pair is: P a b c == c a b
– Combinator for True is: Tb a b == a
– Combinator for False is: Fb a b == b
– Combinator for Pred is: Pr a == a Fb
– Combinator for test on 0 is: Z a == a Tb
– Combinatorial term for 0 is: [0] = P Tb (Pr [0])
– Combinatorial term for n + 1 (with n > 0) is: [n + 1] = P Fb [n]
– Combinatorial Program for Addition:
+ = S(CS(B(CC(CZI))I))(C(C(P Fb ))(B(CC(C + (CPr I)))I))
– Combinatorial Program for Product:
? = S(BC(S(CZI)I))(B(CS(C(C+)(CC(C ? (CPr I)))))I)
– Combinatorial Program for Factorial: Ft = S(B(CZI)[1])(S(C?I)(CFt (CPr I)))
Let N be the the minimal set such that N = {[0], P Fb [n] | [n] ∈ N }. Then, N
is the set of (the combinatorial terms for) numbers, whilst B ≡ {Tb , Fb } is the
set of terms for booleans.
Self-Assembly Programs in SKI-Tiles Programs in SKI-Tile, for the prede-
cessor, the addition, and the factorial, have the listing in Figure 6: The listing
contains only the application tiles. Each program must be completed adding (as
by default) the suitable, connection tiles, introduction tiles, and terminal tiles.
About the connection tiles, each program includes connection tiles of whatever
kind but that involve only one of the program colors (the program colors are
all the colors, but ♠, that occur in the program). For instance, the connection
tile (+(P r [2])m, ♠, +(P r [2])m, ♠) is included, but (+(P r [2])m, ♠, +[1]m, ♠)
is not, in the program for +. About the terminal tiles, these programs compute
numbers, hence numbers are the only colors that can be contained in a terminal
tile to be included in the programs. Finally, the introduction tiles must contain
only colors for numbers and for the name of the program.
In SKI-Tiles, the colors are the combinatorial terms that occur in the program
tiles. But the terms occurring in the tiles of the programs in Figure6are not
always combinatorial terms because of the the symbols n, m, b. Symbols n ad m
are variables ranging on a finite subset of N , whilst b is ranging over N , and the
tiles of the programs are in fact, tile schemata.
Finally, note that the program Pr has no computation grid for computing Pr [0].
7 Conclusions
We have investigated three computation formalisms, Wang Tiles, Schonfinkel
Combinators and Self-Assembly Programming, in order to define a high level
programming language for Self-assembly and DNA computing. We have defined
the formalism SKI-Tiles: It states the structures and the properties that the
Wang tiles must have in order to express combinatorial terms and the computa-
tion of combinatorial programs in the Wang Tiles formalism. We have discussed
DNA Tiles, Wang Tiles and Combinators 13
the soundness of SKI-Tiles. We have used the formalism SKI-Tiles as the ker-
nel of a language for Self-Assembly programming. In order to do it we have
revised the notion of computation and introduced the sound computation grid.
We called this language the SKI-Tiles language. We have shown programs for
Self-Assembly programming that are written in the SKI-Tiles language. These
programs compute a partial function for predecessor on naturals, and functions
for addition and factorial.
(Pr,
[0],
Pr,
[0])
(+,
n,
T,
♠)
(T,
m,
Z
n
m,
T1)
(Pr,
PFb
n,
n,
♠)
Pr:
A
Program
for
Predecessor
(Z
n
m,
♠,
Z
n,
m)
(Ft,
n,
(Z
n)[1](*n(Ft(Pr
n))),
♠)
(Z
n,
♠,
Z,
n)
(Ft,
n,
(Z
n)[1],
*n(Ft(Pr
n)))
(Z,
n,
b,
♠)
(Z
n
[1],
♠,
Z
n,
[1])
(b,
m,
b
m,
♠)
(Z
n,
♠,
Z,
n)
(Tb
m,
T1,
♠)
(Z,
n,
b,
♠)
(Fb
m,
T1,
PFb,
+(Pr
n)m)
(b,
[1],
b
[1],
♠)
(+(Pr
n)m,
♠,
+(Pr
n),
m)
(Tb
[1],
*n(Ft(Pr
n)),
[1],
♠)
(+(Pr
n),
♠,
+,
Pr
n)
(Fb
[1],
m,
m,
♠)
(Pr
n,
♠,
Pr,
n)
legenda:
(*n(Ft(Pr
n)),
♠,
*n,
Ft(Pr
n))
T≡S(C(Z
n)I)(C(PFb)(C(+(Pr
n))I))
T1≡
PFb(+(Pr
n)m)
(Pr
n,
♠,
Pr,
n)
Ft
:
A
Program
for
factorial
+:
A
Program
for
addition
Legenda:
The
Tiles
are
schemata
where
n,
m
are
ranging
on
a
finite
subset
of
N
and
b
is
ranging
on
B.
Programs
specify
only
the
application
tiles
(The
other
tiles
may
be
added,
by
default).
Fig. 6. Self-Assembly Programs for Predecessor, Addition and Factorial in SKI-Tile
14 M. Bellia, M. E. Occhiuto
References
1. Doty, D.: Theory of Algorithmic Self-Assembly. Comm. ACM 55(12) (2012)
2. Winfree, E.: On the Ccomputational Power of DNA Annealing and Ligation. In:
2th DIMACS Meeting on DNA Based Computers. (June 1996)
3. Winfree, E., Liu, F., Wenzler, L.A., Seeman, N.C.: Design and Self-Assembly of
Two-Dimensional DNA Crystals. Nature 394 (1998) 539–544
4. Adleman, L.: Towards a mathematical theory of self-assembly. Technical report
00-722, Department of Computer Science, University of Southern California (2000)
5. Rothemund, P., Winfree, E.: The Program Size Complexity of Self-Assembled
Squares - extended abstract. In: ACM Symposium on Theory of Computing. (2000)
459468
6. Rothemund, P.: Using lateral capillary forces to compute by self-assembly. PNAS
97(3) (2000) 984–989
7. LaBean, T., Yan, H., Kopatsch, J., Liu, F., Winfree, E., Reif, J., Seeman, N.: The
construction, analysis, ligation and self-assembly of dna triple crossover complexes.
J. Am. Chem. Soc. 122 (2000) 1848–1860
8. Mao, C., LaBean, T., Reif, J., Seeman, N.: Logical computation using algorithmic
self-assembly of DNA triple-crossover molecules. Nature 407 (2000) 493–496
9. Jonoska, N., Liao, S., Seeman, N.: Transducers with programmable input by dna
self-assembly. In: Molecular Computing. LNCS 2950 (2004) 219240
10. Doty, D., Patitz, M.: A domain-specific language for programming in the tile
assembly model. In: Proceedings of DNA. (2009) 2534
11. Winfree, E.: Simulations of Computing by Self-Assembly. In: 4th DIMACS Meeting
on DNA Based Computer. (June 1998)
12. Robinson, R.M.: The Undecidability and Nonperiodicity for Tilings of the Plane.
Inventiones math. 12 (1972) 177–209
13. Schonfinkel, M.: On the Building Blocks of Mathematical Logic. in From Frege to
Gdel - A Source Book in Mathematical Logic 1879-1931Harvard University Press,
1967 (1924)
14. H.B.Curry, R.Feys: Combinatory Logic. North-Holland Publishing Company, Am-
sterdam (1956)
15. Turner, D.: Another algorithm for bracket abstraction. The Journal of Symbolic
logic 44(2) (1979)
16. Hughes, J.: Graph reductions with super-combinators. Technical monograph
prg-28, Oxford University Computing Laboratory, Programming Research Group
(1982)
17. Barendregt, H.P.: Functional Programming and Lambda Calculus. in Handbook of
Theoretical Computer Science: Formal Models and Semantics, Elsevier-The MIT
Press (1990)
18. Huet, G.: Confluent Reductions: Abstract Properties and Applications to Term
Rewriting Systems: Abstract Properties and Applications to Term Rewriting Sys-
tems. J. ACM 27(4) (1980) 797–821
19. Jones, S.L.P.: The Implementation of Functional Programming Languages. Inter-
national Series in Computer Science, Prentice-Hall (1987)