NMNiall Murphy

Niall Murphy

*This is an algorithmically generated author record based on publicly available information.

Niall Murphy has a total of 6 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Uniformity is weaker than semi-uniformity for some membrane systems

    by Niall Murphy, Damien Woods

    We investigate computing models that are presented as families of finite computing devices with a uniformity condition on the entire family. Examples of such models include Boolean circuits, membrane systems, DNA computers, chemical reaction networks and tile assembly systems, and there are many others. However, in such models there are actually two distinct kinds of uniformity condition. The first is the most common and well-understood, where each input length is mapped to a single computing device (e.g. a Boolean circuit) that computes on the finite set of inputs of that length. The second, called semi-uniformity, is where each input is mapped to a computing device for that input (e.g. a circuit with the input encoded as constants). The former notion is well-known and used in Boolean circuit complexity, while the latter notion is frequently found in literature on nature-inspired computation from the past 20 years or so. Are these two notions distinct? For many models it has been found that these notions are in fact the same, in the sense that the choice of uniformity or semi-uniformity leads to characterisations of the same complexity classes. In other related work, we showed that these notions are actually distinct for certain classes of Boolean circuits. Here, we give analogous results for membrane systems by showing that certain classes of uniform membrane systems are strictly weaker than the analogous semi-uniform classes. This solves a known open problem in the theory of membrane systems. We then go on to present results towards characterising the power of these semi-uniform and uniform membrane models in terms of NL and languages reducible to the unary languages in NL, respectively.

  • Open Access

    Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy

    by Turlough Neary, Damien Woods, Niall Murphy, Rainer Glaschick

    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.

  • Uniformity is Weaker than Semi-Uniformity for Some Membrane Systems

    by Niall Murphy, Damien Woods

    We investigate computing models that are presented as families of finite computing devices with a uniformity condition on the entire family. Examples of such models include Boolean circuits, membrane systems, DNA computers, chemical reaction networks