DNA Tiles, Wang Tiles and Combinators

• Autorzy: Bellia M. , Occhiuto M. E.

Identyfikatory

DOI

10.3233/FI-2014-1065

• Języki publikacji: EN

Abstrakty

EN

We investigate the relation between Combinatory Logic and Wang Tiles with the aim of studying Combinators as a programming language for Self-Assembly and DNA computing. We introduce a subset of Combinatory Logic, SKI^#, which is Turing Complete, includes simply Typed Combinatory Logic and contains only combinators whose computations require finitely many different redexes. Then, we define a language of Tiles, SKI-Tile, for the representation and the computation of the terms of SKI^# in Self-Assembly. Moreover, we introduce a program development methodology that given any computable function, expressed in SKI^#, provides a finite set of Tiles that self-assemble to return the computations of the function applications. Finally, the methodology is applied to the derivation of a SKI-Tile program that self-assemble to compute the factorial function.

Słowa kluczowe

EN

combinatory logic; combinatorial analysis; programming languages; set theory; nonclassical mathematical logic

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 133, nr 2/3
• Strony: 105--121
• Opis fizyczny: Bibliogr. 33 poz., rys.

Twórcy

autor

Bellia M.

• Dipartimento di Informatica, Università di Pisa, Italy

autor

Occhiuto M. E.

• Dipartimento di Informatica, Università di Pisa, Italy

Bibliografia

• [1] Winfree, E.: On the Ccomputational Power of DNA Annealing and Ligation. In: 2th DIMACS Meeting on DNA Based Computers. (June 1996).
• [2] Doty, D.: Theory of Algorithmic Self-Assembly. Comm. ACM 55(12) (2012).
• [3] Patitz, M.J.: An Introduction to Tile-Based Self-assembly. In: 11th Unconventional Computation and Natural Computation. LNCS 7445 (2012) 34–62.
• [4] LaBean, T.H., Yan, H., Kopatsch, J., Liu, F., Winfree, E., Reif, J.H., Seeman, N.C.: The construction, analysis, ligation and self-assembly of dna triple crossover complexes. J. Am. Chem. Soc. 122 (2000) 1848–1860.
• [5] Mao, C., LaBean, T.H., Reif, J.H., Seeman, N.C.: Logical computation using algorithmic selfassembly of DNA triple-crossover molecules. Nature 407 (2000) 493–496.
• [6] Jonoska, N., Liao, S., Seeman, N.C.: Transducers with programmable input by dna self-assembly. In: Aspects of Molecular Computing. LNCS 2950 (2004) 219240.
• [7] Demaine, E.D., Demaine, M.L., Fekete, S.P., Patitz, M.J., Schweller, R.T., Winslow, A., Woods, D.: One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a Single Puzzle Piece. Technical report, arXiv:1212.4756 [cs.DS] (2012).
• [8] Rothemund, P.W.K., Winfree, E.: The Program Size Complexity of Self-Assembled Squares - [revised may 20 - 2000]. In: ACM Symposium on Theory of Computing (as Extended Abstract). (2000) 459–468.
• [9] Wang, H.: Proving Theorems by Pattern Recognition - ii. Bell Systems Technical Journal 40 (1961).
• [10] Woods, D.: Intrinsic Universality and the Computational Power of Self-Assembly. EPTCS 128 (2013) 16–22.
• [11] Winfree, E., Yang, X., Seeman, N.: Universal Computation via Self-Assembly of DNA: Some Theory and Experiments. In: 2th DIMACS Meeting on DNA Based Computers. (June 1998).
• [12] Winfree, E., Liu, F.,Wenzler, L.A., Seeman, N.C.: Design and Self-Assembly of Two-Dimensional DNA Crystals. Nature 394 (1998) 539–544.
• [13] Winfree, E.: Simulations of Computing by Self-Assembly. In: 4th DIMACS Meeting on DNA Based Computer. (June 1998).
• [14] Adleman, L.: Towards a mathematical theory of self-assembly. Technical report 00-722, Department of Computer Science, University of Southern California (2000).
• [15] Wang, H.: Dominoes and the AEA case of the Decision Problem. In: Symp. on Mathematical Theory of Automata. (1963) 23–55.
• [16] Wolfengagen, V.E.: Combinatory Logic in Programming - 2-nd edition. Series: Computer Science and Information Technologies, Center ”JurInfoR”, Moscow, 2003, ISBN 5-89158-101-9 (2003).
• [17] Schönfinkel, M.I.: On the Building Blocks of Mathematical Logic. in From Frege to Gdel – A Source Book in Mathematical Logic 1879-1931, Harvard University Press, 1967 (1924).
• [18] Curry, H.B., Feys, R.: Combinatory Logic. North-Holland Publishing Company, Amsterdam (1956).
• [19] Berger, R.: The Undecidability of the Domino Problem. Memoirs AMS 66 (1966).
• [20] Robinson, R.M.: The Undecidability and Nonperiodicity for Tilings of the Plane. Inventiones math. 12 (1972) 177–209.
• [21] Hindley, J.R., Seldin, J.P.: Lambda-Calculus and Combinators, an Introduction. Cambridge University Press (2008).
• [22] Turner, D.A.: Another algorithm for bracket abstraction. The Journal of Symbolic logic 44(2) (1979).
• [23] Hughes, J.: Graph Reductions with Super-Combinators. Tech Monograph PRG-28, Oxford University Computing Laboratory, Programming Research Group (1982).
• [24] Patitz, M.J.: Simulation of self-assembly in the abstract tile assembly model with ISU TAS (2009) http://www.cs.iastate.edu/~ lnsa/software.html.
• [25] Kleene, S.C.: General recursive functions of natural numbers. Mathematische Annalen 112 (1936) 727–742.
• [26] Chakraborty, B., Jonoska, N., Seeman, N.C.: A Programmable Transducer Self-Assembled from DNA. Chemical Science 3(1) (2012) 168–176.
• [27] Peyton-Jones, S.L., Lester, D.R.: Implementing Functional Languages: a Tutorial. http://research.microsoft.com/en-us/um/people/simonpj/Papers/papers.html (2000).
• [28] Jonoska, N., SA-Ardyen, P., Seeman, N.C.: Computation by Self-Assembly of DNA Graphs. Genetic Programming and Evolvable Machines 4 (203) 123137.
• [29] Carbone, A., Seeman, N.: Molecular Tiling and DNA self-assembly. In: Aspects of Molecular Computing. LNCS 2950 (2004) 6183.
• [30] Rothemund, P.W.K.: Folding DNAto create nanoscale shapes and patterns. Nature 440 (2006) 297–302.
• [31] Ran, T., Kaplan, S., Shapiro, E.: Molecular implementation of simple logic programs. Nature Nanotechnology 4 (2009) 642–648.
• [32] Zhao, Z., Liu, Y., Yan, H.: Organizing DNA Origami Tiles into Larger Structures Using Preformed Scaffold Frames. Nano Lett. - ACS 11 (2011) 2997–3002.
• [33] Jonoska, N., Seeman, N.C.: Computing by Molecular Self-Assembly. Interface Focus 2 (2012) 504511.