Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Issue title: Special Issue on Machines, Computations and Universality (MCU 2015)
Guest editors: Jérôme Durand-Lose, Jarkko Kari and Benedek Nagy
Article type: Research Article
Authors: Csuhaj-Varjú, Erzsébeta; * | Freund, Rudolfb | Vaszil, Györgyc
Affiliations: [a] Department of Algorithms and Their Applications, Eötvös Loránd University, Pázmány Péter sétány 1/c, 1117 Budapest, Hungary. [email protected] | [b] Institut of Computer Languages, Technische Universität Wien, Favoritenstraße 9-11, 1040 Wien, Austria. [email protected] | [c] Department of Computer Science, University of Debrecen, Kassai út 26, 4028 Debrecen, Hungary. [email protected]
Correspondence: [*] Address for correspondence: Faculty of Informatics, Eötvös Loránd University, Budapest, Hungary
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.
Keywords: complementary relation, mind change, red-green register machines, red-green Turing machines, Watson-Crick T0L systems
DOI: 10.3233/FI-2017-1578
Journal: Fundamenta Informaticae, vol. 155, no. 1-2, pp. 111-129, 2017
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
[email protected]
For editorial issues, like the status of your submitted paper or proposals, write to [email protected]
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
[email protected]
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office [email protected]
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
[email protected]
For editorial issues, like the status of your submitted paper or proposals, write to [email protected]
如果您在出版方面需要帮助或有任何建, 件至: [email protected]