Research On The Design And Applications Of Algorithmic Tile Assembly Systems

Tile Assembly System (TAS), a novel distributed parallel computing device, has been proved to be Turing-universal that any computable issues could be executed by it theoretically. However, no practicable way is found to be suitable for any computable issues using TAS up to now. That is, nothing useful can be directly obtained from its Turing-universality when solving a specific issue. Thus, four classes of critical issues are investigated in detail to establish connections with TAS in this paper, which are Sorting, Boolean logic computing, the maximum clique and integer factorization of RSA cryptosystem. Detailed programmable TAS and the corresponding algorithms are proposed for these issues respectively. The work provides theoretical foundation for the development of molecular tile assembly computer.Sorting issue will be encountered in information retrieval problems and solving the discrete logarithm problems using Shanks'baby-step giant-step algorithm, etc. A programmable TAS for sorting issue is developed taking full advantage of the huge parallelism inherent in tile assembly. "Modulization" idea is introduced to increase the sorting pairs of integers on the same assembly step and decrease the total number of tile assembly steps. Complexity of the system is investigated. It is shown that the number of tile types is constant, and the total number of tile assembly steps is (?)(mn).Boolean logic computing has extensive applications on mathematical computing and NP hard problems. An algorithmic TAS is raised for any Boolean formulas. The "hierarchy architecture" idea is introduced to the scheme to construct some sub-systems according to the numbers of the statement of the Boolean logic formula. The scheme makes full use of the huge parallelism of TAS, can be applied on solving satisfiability problem and S-box analysis of DES cryptography etc.For the maximum clique problem, which is an NP-complete problem, a nondeterministic TAS is proposed. A class of functional tiles containing the algorithmic rules are designed and the given information about the graph is put into the seed configuration. It is shown that the TAS can produce all the cliques for the graph and the maximum clique can be found by the use of gel electrophoresis. The method deletes the wrong answer step by step to simplify the computing complexity and improves the reliability. The number of tile types required is (?)(mn) and the assembly time is linear with the size of graph.RSA public key cryptosystem, whose security is based on the difficulty of factoring large integer, has broad applications on the e-business and key distribution. Aiming at factoring large integer, two T AS are developed taking full advantage of the huge parallelism inherent in tile assembly. In systemâ… , the bit pairs (pi, qi) are inserted into the seed construction bit by bit. The tile assembly processes yield a pair of bits and examine whether they satisfy the factorization condition. If met, the pair are recorded on a report strand which will be extract out as the result; otherwise, the tile assembly goes to halt. Systemâ…¡is proposed based on the fact that the Euclid algorithm can compute one factor for two integers. A TAS is designed to implement the improved binary Euclid algorithm preliminary. And then, systemâ…¡is raised by introducing a set of stochastic tiles for factorization on the basis of the former TAS.