A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Splicing systems for universal turing machines
Tekijät: Harju T, Margenstern M
Julkaisuvuosi: 2005
Lehti:: Lecture Notes in Computer Science
Tietokannassa oleva lehden nimi: DNA COMPUTING
Lehden akronyymi: LECT NOTES COMPUT SC
Vuosikerta: 3384
Aloitussivu: 149
Lopetussivu: 158
Sivujen määrä: 10
ISBN: 3-540-26174-5
ISSN: 0302-9743
Tiivistelmä
It turns out that starting from a Turing machine M with alphabet A and finite set of states Q which generates a given recursively enumerable language L, we need around 2x/I/+2 rules in order to define an extended H system H which generates L, where I is the set of instructions of Turing machine M. Next, coding the states of Q and the non-terminal symbols of,C, we obtain, an extended H system H-1 which generates L using /A/+2 symbols. At last, by encoding the alphabet, we obtain a splicing system U which generates a universal recursively enumerable set using only two letters.
It turns out that starting from a Turing machine M with alphabet A and finite set of states Q which generates a given recursively enumerable language L, we need around 2x/I/+2 rules in order to define an extended H system H which generates L, where I is the set of instructions of Turing machine M. Next, coding the states of Q and the non-terminal symbols of,C, we obtain, an extended H system H-1 which generates L using /A/+2 symbols. At last, by encoding the alphabet, we obtain a splicing system U which generates a universal recursively enumerable set using only two letters.
Turun yliopiston Tutkimustietojärjestelmän portaali