Turlough Neary
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Turlough Neary has a total of 8 co-authors. Here are the top co-authors by number of shared publications:
- Damien Woods
California Institute of Technology
4 shared publications Matthew Cook
University of Zürich and ETH Zürich
2 shared publications- Urban Larsson
Indian Institute of Technology, Bombay
2 shared publications Anthony K. Seda
1 shared publication- Damien Woods
Maynooth University
1 shared publication - Matthew Cook
Institute of Neuroinformatics University of Zurich ETH Zurich - Barcelona Switzerland Spain
1 shared publication
Latest Publications
- 30 August 2018
- Published by Springer Nature
- p. 103-116
Generalized Tag Systems
- Open Access
- 3 June 2017
- Published by Springer Nature
- p. 274-286
2-State 2-Symbol Turing Machines with Periodic Support Produce Regular Sets
- 3 June 2017
- Published by Springer Nature
- p. 274-286
Open Access2-State 2-Symbol Turing Machines with Periodic Support Produce Regular Sets
- Open Access
- 3 October 2016
- Published by Springer Nature in Natural Computing
- Vol. 16 (3) , 397-410
A cellular automaton for blocking queen games
- 3 October 2016
- Published by Springer Nature in Natural Computing
- Vol. 16 (3) , 397-410
Open AccessA cellular automaton for blocking queen games
- Open Access
- 4 June 2015
- Published by Springer Nature
- p. 11-16
Tag Systems and the Complexity of Simple Programs
- 4 June 2015
- Published by Springer Nature
- p. 11-16
Open AccessTag Systems and the Complexity of Simple Programs
- Open Access
- 4 June 2015
- Published by Springer Nature
- p. 71-84
A Cellular Automaton for Blocking Queen Games
- 4 June 2015
- Published by Springer Nature
- p. 71-84
Open AccessA Cellular Automaton for Blocking Queen Games
- 1 June 2015
- Published by SAGE Publications in Fundamenta Informaticae
- Vol. 138 (1-2) , 251-258
Yurii Rogozhin's Contributions to the Field of Small Universal Turing Machines
In the field of small universal Turing machines, Yurii Rogozhin holds a special prize: he was first to close off an infinite number of open questions by drawing a closed curve that separates the infinite set of Turing machines that are universal from a finite set of small machines for which we don't yet know. Rogozhin did this by finding the smallest known universal Turing machines at the time, both in terms of number of states and number of symbols. This brief note summarises this and a few of Yurii's other contributions to the field, including his work with Manfred Kudlek on small circular Post machines.
- 1 June 2015
- Published by SAGE Publications in Fundamenta Informaticae
- Vol. 138 (1-2) , 251-258
Yurii Rogozhin's Contributions to the Field of Small Universal Turing Machines
In the field of small universal Turing machines, Yurii Rogozhin holds a special prize: he was first to close off an infinite number of open questions by drawing a closed curve that separates the infinite set of Turing machines that are universal from a finite set of small machines for which we don't yet know. Rogozhin did this by finding the smallest known universal Turing machines at the time, both in terms of number of states and number of symbols. This brief note summarises this and a few of Yurii's other contributions to the field, including his work with Manfred Kudlek on small circular Post machines.
- 1 January 2015
- Published by Springer Nature
- p. 117-126
Maurice Margenstern’s Contributions to the Field of Small Universal Turing Machines
- 1 January 2015
- Published by Springer Nature
- p. 117-126
Maurice Margenstern’s Contributions to the Field of Small Universal Turing Machines
- Open Access
Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy
In the 1960's Gisbert Hasenjaeger built Turing Machines from electromechanical relays and uniselectors. Recently, Glaschick reverse engineered the program of one of these machines and found that it is a universal Turing machine. In fact, its program uses only four states and two symbols, making it a very small universal Turing machine. (The machine has three tapes and a number of other features that are important to keep in mind when comparing it to other small universal machines.) Hasenjaeger's machine simulates Hao Wang's B machines, which were proved universal by Wang. Unfortunately, Wang's original simulation algorithm suffers from an exponential slowdown when simulating Turing machines. Hence, via this simulation, Hasenjaeger's machine also has an exponential slowdown when simulating Turing machines. In this work, we give a new efficient simulation algorithm for Wang's B machines by showing that they simulate Turing machines with only a polynomial slowdown. As a second result, we find that Hasenjaeger's machine also efficiently simulates Turing machines in polynomial time. Thus, Hasenjaeger's machine is both small and fast. In another application of our result, we show that Hooper's small universal Turing machine simulates Turing machines in polynomial time, an exponential improvement.
Open AccessWang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy
In the 1960's Gisbert Hasenjaeger built Turing Machines from electromechanical relays and uniselectors. Recently, Glaschick reverse engineered the program of one of these machines and found that it is a universal Turing machine. In fact, its program uses only four states and two symbols, making it a very small universal Turing machine. (The machine has three tapes and a number of other features that are important to keep in mind when comparing it to other small universal machines.) Hasenjaeger's machine simulates Hao Wang's B machines, which were proved universal by Wang. Unfortunately, Wang's original simulation algorithm suffers from an exponential slowdown when simulating Turing machines. Hence, via this simulation, Hasenjaeger's machine also has an exponential slowdown when simulating Turing machines. In this work, we give a new efficient simulation algorithm for Wang's B machines by showing that they simulate Turing machines with only a polynomial slowdown. As a second result, we find that Hasenjaeger's machine also efficiently simulates Turing machines in polynomial time. Thus, Hasenjaeger's machine is both small and fast. In another application of our result, we show that Hooper's small universal Turing machine simulates Turing machines in polynomial time, an exponential improvement.
- Open Access
Undecidability in binary tag systems and the Post correspondence problem for four pairs of words
Since Cocke and Minsky proved 2-tag systems universal, they have been extensively used to prove the universality of numerous computational models. Unfortunately, all known algorithms give universal 2-tag systems that have a large number of symbols. In this work, tag systems with only 2 symbols (the minimum possible) are proved universal via an intricate construction showing that they simulate cyclic tag systems. Our simulation algorithm has a polynomial time overhead, and thus shows that binary tag systems simulate Turing machines in polynomial time. We immediately find applications of our result. We reduce the halting problem for binary tag systems to the Post correspondence problem for 4 pairs of words. This improves on 7 pairs, the previous bound for undecidability in this problem. Following our result, only the case for 3 pairs of words remains open, as the problem is known to be decidable for 2 pairs. As a further application, we find that the matrix mortality problem is undecidable for sets with five $3\times 3$ matrices and for sets with two $15\times 15$ matrices. The previous bounds for the undecidability in this problem was seven $3\times 3$ matrices and two $ 21\times 21$ matrices.Open AccessUndecidability in binary tag systems and the Post correspondence problem for four pairs of words
Since Cocke and Minsky proved 2-tag systems universal, they have been extensively used to prove the universality of numerous computational models. Unfortunately, all known algorithms give universal 2-tag systems that have a large number of symbols. In this work, tag systems with only 2 symbols (the minimum possible) are proved universal via an intricate construction showing that they simulate cyclic tag systems. Our simulation algorithm has a polynomial time overhead, and thus shows that binary tag systems simulate Turing machines in polynomial time. We immediately find applications of our result. We reduce the halting problem for binary tag systems to the Post correspondence problem for 4 pairs of words. This improves on 7 pairs, the previous bound for undecidability in this problem. Following our result, only the case for 3 pairs of words remains open, as the problem is known to be decidable for 2 pairs. As a further application, we find that the matrix mortality problem is undecidable for sets with five $3\times 3$ matrices and for sets with two $15\times 15$ matrices. The previous bounds for the undecidability in this problem was seven $3\times 3$ matrices and two $ 21\times 21$ matrices. - Open Access
- 25 June 2009
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 1, 1-2
Proceedings International Workshop on The Complexity of Simple Programs
This is the first volume of Electronic Proceedings in Theoretical Computer Science (EPTCS), a free international refereed open access venue for the rapid electronic publication of the proceedings of workshops and conferences, and of festschriften, etc, in the general area of theoretical computer science, broadly construed. It contains the proceedings of the International Workshop on The Complexity of Simple Programs, which was hosted at University College Cork on the 6th and 7th of December, 2008. All speakers were invited and all of the papers went through a thorough peer-review process.
- 25 June 2009
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 1, 1-2
Open AccessProceedings International Workshop on The Complexity of Simple Programs
This is the first volume of Electronic Proceedings in Theoretical Computer Science (EPTCS), a free international refereed open access venue for the rapid electronic publication of the proceedings of workshops and conferences, and of festschriften, etc, in the general area of theoretical computer science, broadly construed. It contains the proceedings of the International Workshop on The Complexity of Simple Programs, which was hosted at University College Cork on the 6th and 7th of December, 2008. All speakers were invited and all of the papers went through a thorough peer-review process.