A more recent branch of natural computing is DNA computing. At the theoretical level, DNA computing is powerful. This is due to the fact that DNA structure and processing suggest a series of new data structures and op...A more recent branch of natural computing is DNA computing. At the theoretical level, DNA computing is powerful. This is due to the fact that DNA structure and processing suggest a series of new data structures and operations, and to the fact of the massive parallelism. The insertion-deletion system （insdel system） is a DNA computing model based on two genetic operations： insertion and deletion which, working together, are very powerful, leading to characterizations of recursively enumerable lan- guages. When designing an insdel computer, it is natural to try to keep the underlying model as simple as possible. One idea is to use either only insertion operations or only deletion operations. By helping with a weak coding and a morphism, the family INS4^7DEL0^0 is equal to the family of recursively enumerable languages. It is an open problem proposed by Martin-Vide et al. on whether or not the parameters 4 and 7 appearing here can be replaced by smaller numbers. In this paper, our positive answer to this question is that INS2^4DEL0^0 can also play the same role as insertion and deletion. We suppose that the INS2^4DEL0^0 may be the least only-insertion insdel system in this situation. We will give some reasons supporting this conjecture in our paper.展开更多
文摘A more recent branch of natural computing is DNA computing. At the theoretical level, DNA computing is powerful. This is due to the fact that DNA structure and processing suggest a series of new data structures and operations, and to the fact of the massive parallelism. The insertion-deletion system （insdel system） is a DNA computing model based on two genetic operations： insertion and deletion which, working together, are very powerful, leading to characterizations of recursively enumerable lan- guages. When designing an insdel computer, it is natural to try to keep the underlying model as simple as possible. One idea is to use either only insertion operations or only deletion operations. By helping with a weak coding and a morphism, the family INS4^7DEL0^0 is equal to the family of recursively enumerable languages. It is an open problem proposed by Martin-Vide et al. on whether or not the parameters 4 and 7 appearing here can be replaced by smaller numbers. In this paper, our positive answer to this question is that INS2^4DEL0^0 can also play the same role as insertion and deletion. We suppose that the INS2^4DEL0^0 may be the least only-insertion insdel system in this situation. We will give some reasons supporting this conjecture in our paper.
