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 sub- set of Combinatory Logic, SKI#, which is Turing Complete, includes simply Typed Combinatory Logic and contains only combinators whose computations require nitely many dierent redexes. Then, we dene a language of Tiles, SKI-Tile, for the representation and the computation of the terms of SKI# in Self-Assembly. Moreover, we introduce a pro- gram development methodology that given any computable function, ex- pressed in SKI#, provides a nite 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.
DNA Tiles, Wang Tiles and Combinators
BELLIA, MARCO;OCCHIUTO, MARIA EUGENIA
2014-01-01
Abstract
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 sub- set of Combinatory Logic, SKI#, which is Turing Complete, includes simply Typed Combinatory Logic and contains only combinators whose computations require nitely many dierent redexes. Then, we dene a language of Tiles, SKI-Tile, for the representation and the computation of the terms of SKI# in Self-Assembly. Moreover, we introduce a pro- gram development methodology that given any computable function, ex- pressed in SKI#, provides a nite 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
