Finite-state molecular computing

In this paper we explore the molecular computation model based on a splicing system and implemented in vitro by Shapiro. This paper presents two implementations, one implementing an FSA with two states, and the other one with three states, using enzymes BseMII and BseXI, respectively, which are different from only the one - FokI - used by Shapiro, et al. for their two-state FSA. The model of three-state, two-input symbol machine supports 1.835.001 syntactically distinct programs in comparison with 765 programs in Shapiro's approach.