Source author record

Turlough Neary

Turlough Neary appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms Formal Languages and Automata Theory math.CO math.DS

Catalog footprint

What is connected

7works

5topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2015arXiv

A Cellular Automaton for Blocking Queen Games

We show that the winning positions of a certain type of two-player game form interesting patterns which often defy analysis, yet can be computed by a cellular automaton. The game, known as {\em Blocking Wythoff Nim}, consists of moving a queen as in chess, but always towards (0,0), and it may not be moved to any of $k-1$ temporarily "blocked" positions specified on the previous turn by the other player. The game ends when a player wins by blocking all possible moves of the other player. The value of $k$ is a parameter that defines the game, and the pattern of winning positions can be very sensitive to $k$. As $k$ becomes large, parts of the pattern of winning positions converge to recurring chaotic patterns that are independent of $k$. The patterns for large $k$ display an unprecedented amount of self-organization at many scales, and here we attempt to describe the self-organized structure that appears.

preprint2014arXiv

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.

preprint2013arXiv

Proceedings Machines, Computations and Universality 2013

This volume contains the papers presented at the 6th conference on Machines, Computations and Universality (MCU 2013). MCU 2013 was held in Zurich, Switzerland, September 9-11, 2013. The MCU series began in Paris in 1995 and has since been concerned with gaining a deeper understanding of computation through the study of models of general purpose computation. This volume continues in this tradition and includes new simple universal models of computation, and other results that clarify the relationships between models.

preprint2013arXiv

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.

preprint2011arXiv

The complexity of small universal Turing machines: a survey

We survey some work concerned with small universal Turing machines, cellular automata, tag systems, and other simple models of computation. For example it has been an open question for some time as to whether the smallest known universal Turing machines of Minsky, Rogozhin, Baiocchi and Kudlek are efficient (polynomial time) simulators of Turing machines. These are some of the most intuitively simple computational devices and previously the best known simulations were exponentially slow. We discuss recent work that shows that these machines are indeed efficient simulators. In addition, another related result shows that Rule 110, a well-known elementary cellular automaton, is efficiently universal. We also discuss some old and new universal program size results, including the smallest known universal Turing machines. We finish the survey with results on generalised and restricted Turing machine models including machines with a periodic background on the tape (instead of a blank symbol), multiple tapes, multiple dimensions, and machines that never write to their tape. We then discuss some ideas for future work.

preprint2010arXiv

A boundary between universality and non-universality in spiking neural P systems

In this work we offer a significant improvement on the previous smallest spiking neural P systems and solve the problem of finding the smallest possible extended spiking neural P system. Paun and Paun gave a universal spiking neural P system with 84 neurons and another that has extended rules with 49 neurons. Subsequently, Zhang et al. reduced the number of neurons used to give universality to 67 for spiking neural P systems and to 41 for the extended model. Here we give a small universal spiking neural P system that has only 17 neurons and another that has extended rules with 5 neurons. All of the above mentioned spiking neural P systems suffer from an exponential slow down when simulating Turing machines. Using a more relaxed encoding technique we get a universal spiking neural P system that has extended rules with only 4 neurons. This latter spiking neural P system simulates 2-counter machines in linear time and thus suffer from a double exponential time overhead when simulating Turing machines. We show that extended spiking neural P systems with 3 neurons are simulated by log-space bounded Turing machines, and so there exists no such universal system with 3 neurons. It immediately follows that our 4-neuron system is the smallest possible extended spiking neural P system that is universal. Finally, we show that if we generalise the output technique we can give a universal spiking neural P system with extended rules that has only 3 neurons. This system is also the smallest of its kind as a universal spiking neural P system with extended rules and generalised output is not possible with 2 neurons.

preprint2006arXiv

On the time complexity of 2-tag systems and small universal Turing machines

We show that 2-tag systems efficiently simulate Turing machines. As a corollary we find that the small universal Turing machines of Rogozhin, Minsky and others simulate Turing machines in polynomial time. This is an exponential improvement on the previously known simulation time overhead and improves a forty year old result in the area of small universal Turing machines.