DNA Tiles, Wang Tiles and Combinators

Issue title: Concurrency, Specification and Programming

Article type: Research Article

Authors: Bellia, Marco | Occhiuto, M. Eugenia

Affiliations: Dipartimento di Informatica, Università di Pisa, Italy. {bellia,occhiuto}@di.unipi.it

Note: [] Address for correspondence: Dipartimento di Informatica, Università di Pisa, Italy

Abstract: 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.

DOI: 10.3233/FI-2014-1065

Journal: Fundamenta Informaticae, vol. 133, no. 2-3, pp. 105-121, 2014