DNA Tiles, Wang Tiles and Combinators

Abstract

In this paper we explore the relation between Wang Tiles and Schon nkel 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 ts into a grid of tiles of a suitable nite, tile set, and nally, how a program for Self-assembly DNA computing can be obtained. The result is a general methodology that, given any computable function, allows to de ne a Self-assembly program that can be used to construct the computations of the function (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 e ective computations. Each of such structures can be read as the complete trace of a computation, from its start to its end.

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 complementary law and is e ectively governed by various bio-chemical techniques [ 6 ]. However, in terms of computable functions, in the Self-Assembly computation process, it is possible to recognize:

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 nite 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 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 combinators [ 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 de nition of a language for Self-Assembly, SKI-Tiles, and of a general methodology that, given any computable function, allows to de ne 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 nite sets of distinct tiles: What tile sets of F , can cover the in nite plane by using Wang-arrangement on copies of the tiles of the set, obtained by translation (no rotation, no re ection). In 1963, Wang showed that to each Turing Machine M corresponds a nite set TM 2 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 nite tile sets, of covering the in nite plane.

T1  

T2  

T4  

T3   sai. d Wesa  ncogl oTrileed:    A b  uy n Ti1t, s Tq2u,a Tre 3,  w Ti4th     the      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

SKI Combinators

The monoid SKI SKI Combinators [ 14 ] is a formal system that expresses all the computable functions1 without requiring any (bound) variable and by using only one operation: the monadic, functional application. Hence, it is the monoid2 , below: = SjKjIj jXj where the application is represented by juxtaposition of a (left) term, representing a monadic function, to a the (right) term, representing the argument. Currying, higher order functions, and left associativity of application are provided 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 2 :

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 2 be any term, possibly containing a (free) variable x 2 X. Then, we de ne the bracket abstraction of a 2 with x, written [x]a, be the term b 2 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 2 fS; K; Ig [ [ 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. Schon nkel, [ 13 ], the combinator "I", which could be expressed through SKK, was replaced by the combinator "U", in order to express rst 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 2 , 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 ] 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, !, de ned in the following way. Relation ! is called combinatorial reduction. De nition 1 (! ). Relation !

is the re exive and transitive closure of ! .

I a == a

K a b == a

S a b c == a c (b c)   I a → a K a b → 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 2 , 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 con uence 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 De nition2. De nition 2 (The Kleene xed-point combinatorial program calculator, ). Let R S(S(KS)(S(KK)I))(K(SII)). Then, SRR is a combinatorial program. Moreover, is such that, for all pairs of terms G; a 2 , the following holds:

(*) G a G ( G) a The proof of (*) is a trivial exercise. points out the elegance with which Schonnkel monoid expresses the computable functions. In particular, introduces recursively de ned terms on one hand, and computes the least xed point of them, on the other hand. However, in Section 6, we use term equations for dealing with recursive de nitions, because Self-assembly computation has a notion of term replacement that already support recursive de nitions. 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 computation. Then, we show how to use such structures in order to get the de nition and the computation of any combinatorial program. 4 Obviously, n = 0 means that for no b 2 , a ! b

SKI-Tiles: A formalism of Wang Tiles for combinatorial programs The colors that may occur in the tiles, are the combinatorial terms (of ): Di erent terms are di erent 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 nally, with a connection term (which allows to arrange together distinct tiles and distinct parts of the computation grid). When more di erent 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 ve 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, speci c, 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, speci c, 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 di erent 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 corresponds to the (re ection 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.

Introduction Tiles

♠ ♠ ♠ T3 T2 T3 T2 ♠ T2 ♠ ♠ T3

Terminal Tiles

T2 ♠ ♠

♠

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. The combinators are completely de ned 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 rst 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 di er 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 a   ♠  

♠     ♠   K  

Ka  

Ka   ♠   Ka   Ka   b   b   b   a   ♠   ♠  

K  a  b  =  a   3, and in Figure 4 are de ned 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 theorem furnishes a constructive proof and a concrete way to do it. The next section shows how the approach e ectively applies in a computation. 5

Applications and Examples

The section shows how the approach e ectively applies in a computation. Consider 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 di erent ways, according to a use of combinatory programming 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 in uenced 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:           S   ♠   a   Sa   Sa   ♠   ♠  

  ♠    ♠   b   b   b   Sab   Sab  

  ♠   Sa   Sa  

♠   ♠   ♠   ♠   ♠    ♠   Sab   Sab   ♠  

♠   ac(bc)   ♠   c   c   c   c   c     ♠   ♠   b   b   b  

  Sab  

Sab   ♠    ♠   ♠  

♠   Sa   Sa   ♠   ♠     c   c   c   c   c   ♠   ♠   S   ♠   a   Sa   Sa   ♠   ♠   ♠   ♠   ♠    ♠   Sab   Sab   bc   ♠   ac    

S  a  b  c  =  a  c  (b  c)   This way of programming uses the possibility of introducing new combinators and super combinators [ 16 ] in order to obtain a more expressive and neat solution to a possibly, more general problem than the given one. In this case, the problem may be solved by using a family, P roj = ffn : Dn ! Dg, of curried functions, each function being indexed by the arity. We can express each function of P roj by the following combinatorial term: Tp = Ki 1(W IKn 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, Kmg = K(Km 1g) 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 IK2)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)))

Self-assembly Computations with SKI-Tiles

This section discusses the formalism of SKI-Tiles in the context of the SelfAssembly programming and extends the formalism with the notions of program and of computation of the Self-Assembly programming paradigm. Wang Tiles and Self-Assembly share the same fundamental operation for connecting the tiles: Wang-arrangement. Nevertheless, there is a subtle but relevant T = T1c4 T1 = T c

2 3 T2 = T c

3 2 T3 = T c

4 1 T4 = KT5 T5 = ST6T7 T6 = KK T7 = ST6I

Subterms T4,c1,c2, c3,c4, T5,T6c2,T7c2,

Kc2,T8=K(Kc2) Specific Colors ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠

♠

T4 T4 ♠ T4 T4 ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ c1 c1 T5 T5 T5 T5 ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠ ♠

T6c2 T6c2 ♠ c2 c2

Fig. 5. The computation grid of T = (((K(S(KK)(S(KK)I))c1)c2)c3)c4 di erence. The Wang formalism neither has a notion of program nor of computation: The aim is the construction of some computation grid that must be assembled with the tiles of a given tile set. Di erently, Self-assembly is a programming 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 fT; g; g be triple de ning the physics of molecular 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 nite 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 provided 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 satis es 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. De nition 3 (Quasi-grids.). A quasi-grid is a n m grid of tiles with n; m > 1 and such that: The tiles of the rst column, exception for the top tile, have a  as west side; The tiles of the rst 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.

De nition 4 (Sub-grid Property.). Let G be a computation grid and A be an unfold-tile of G. Then A satis es 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, rstly, 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; T6c2; T7c2) (4th tile from the top, of the 3rd column, from the left) of computation grid in Figure 5, is an unfold-tile which satis es 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 (T7c2; 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 (T7c2; ; 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 programming6: { 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 combinators, to include some combinators, C, B, P , that are of general use in combinatorial 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 juxtaposition, is left associative, and has precedence on abstraction. Finally, recursive de nitions 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 unde ned value, P red[0]. { 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 + (CPrI)))I)) { Combinatorial Program for Product:

? = S(BC(S(CZI)I))(B(CS(C(C+)(CC(C ? (CPrI)))))I) { Combinatorial Program for Factorial: Ft = S(B(CZI)[ 1 ])(S(C?I)(CFt(CPrI))) Let N be the the minimal set such that N = f[0]; P Fb[n] j [n] 2 N g. Then, N is the set of (the combinatorial terms for) numbers, whilst B fTb; Fbg is the set of terms for booleans.

Self-Assembly Programs in SKI-Tiles Programs in SKI-Tile, for the predecessor, 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 nite 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, Schon nkel Combinators and Self-Assembly Programming, in order to de ne a high level programming language for Self-assembly and DNA computing. We have de ned 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 computation of combinatorial programs in the Wang Tiles formalism. We have discussed the soundness of SKI-Tiles. We have used the formalism SKI-Tiles as the kernel 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,  PFb  n,  n,  ♠)  

Pr:  A  Program  for  Predecessor     (Ft,  n,  (Z  n)[ 1 ](*n(Ft(Pr  n))),  ♠)   (Ft,  n,  (Z  n)[ 1 ],  *n(Ft(Pr  n)))   (Z  n  [ 1 ],  ♠,  Z  n,  [ 1 ])   (Z  n,  ♠,  Z,  n)   (Z,  n,  b,  ♠)   (b,  [ 1 ],  b  [ 1 ],  ♠)   (Tb  [ 1 ],  *n(Ft(Pr  n)),  [ 1 ],  ♠)   (Fb  [ 1 ],  m,  m,  ♠)   (*n(Ft(Pr  n)),    ♠,  *n,  Ft(Pr  n))   (Pr  n,  ♠,  Pr,  n)  

Ft  :  A  Program  for  factorial   (+,  n,  T,  ♠)   (T,  m,  Z  n  m,  T1)   (Z  n  m,  ♠,  Z  n,  m)   (Z  n,  ♠,  Z,  n)   (Z,  n,  b,  ♠)   (b,  m,  b  m,  ♠)   (Tb  m,  T1,  ♠)   (Fb  m,  T1,  PFb,  +(Pr  n)m)   (+(Pr  n)m,  ♠,  +(Pr  n),  m)   (+(Pr  n),  ♠,  +,  Pr  n)   (Pr  n,  ♠,  Pr,  n)   legenda:       T≡S(C(Z  n)I)(C(PFb)(C(+(Pr  n))I))   T1≡  PFb(+(Pr  n)m)     +:  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

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-speci c 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. Schon nkel, 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, Amsterdam ( 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.: Con uent Reductions: Abstract Properties and Applications to Term Rewriting Systems: Abstract Properties and Applications to Term Rewriting Systems . J. ACM 27 ( 4 ) ( 1980 ) 797 { 821

19. Jones , S.L.P.: The Implementation of Functional Programming Languages . International Series in Computer Science, Prentice-Hall ( 1987 )