Abstract
In this paper we establish a connection between two concepts of unconventional computing, namely Watson-Crick T0L systems (schemes) and red-green Turing machines or red-green register machines. Our research was inspired by the conceptual similarity of a mind change of a red-green Turing or register machine and of a turn to the complementary string in Watson-Crick T0L systems as well as by the fact that both red-green Turing or register machines and Watson-Crick T0L systems define infinite computations on finite inputs. We define language recognition for Watson-Crick T0L systems based on the infinite sequences they generate, and we show that the sets of (vectors of) natural numbers which can be recognized by so-called standard Watson-Crick T0L schemes (with a context-free trigger) include the sets recognized by red-green register machines (or red-green Turing machines). The obtained results imply that using Watson-Crick T0L schemes we may “go beyond Turing” as the red-green register machines and red-green Turing machines can do. Furthermore, we also show that for any deterministic Watson-Crick 0L scheme with a regular trigger the recognizability problem of a word is decidable.