models of computation; small universal Turing machines; simple universal models of computation; biologically inspired models of computation ; time/space complexity of simple machines
Cook Matthew, Larsson Urban, Neary Turlough (2015), A Cellular Automaton for Blocking Queen Games, in Cellular Automata and Discrete Complex Systems - 21st IFIP WG 1.5 International Workshop, AUTOMATA
Neary Turlough, Woods Damien (2015), Maurice Margenstern’s Contributions to the Field of Small Universal Turing Machines, in Adamatzky Andrew (ed.), 117-126.
Neary Turlough, Woods Damien (2015), Tag Systems and the Complexity of Simple Programs, in Kari Jarkko (ed.), 11-16.
Neary Turlough (2015), Three small universal spiking neural P systems, in Theoretical Computer Science
, 567, 2-20.
Neary Turlough (2015), Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words, in 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
, 30, 30.
Woods Damien, Neary Turlough (2015), Yurii Rogozhin's Contributions to the Field of Small Universal Turing Machines, in Fundamenta Informaticae
, 138(1-2), 251-258.
Neary Turlough, Woods Damien, Murphy Niall, Glaschick Rainer (2014), Hasenjaeger’s electromechanical small universal Turing machine is time-efficient, in Turing in Context
, Royal Flemish Academy for the Sciences and Arts.
Neary Turlough, Woods Damien, Murphy Niall, Glaschick Rainer (2014), Wang’s B machines are efficiently universal, as is Hasenjaeger’s small universal electromechanical toy, in Journal of Complexity
, 30(5), 634-646.
In terms of computational power, the term universality indicates computing power equivalent to that of a modern personal computer with infinite memory or to the Java programming language. For many years now, there has been much interest in finding simple universal models of computation. However, there has been rather little analysis of the time/space computational complexity of simple universal models of computation. Hence, we intend to investigate the relationship between the program-size complexity of a model and its computational time/space complexity. For instance, if we simplify our model, will it become more inefficient in terms of its time and space requirements?We wish to investigate the effect of varying the different parameters (e.g. the states or symbols in a Turing machine) that restrict each model. For instance, some parameters may have a greater effect on time/space complexity or on the computational power than others. We also wish to look for universality boundaries in different models. We take a parameter (or a set of parameters) in our model and ask the question: what is the smallest value of this parameter for which the model remains universal? For example, a universality boundary value for single-tape Turing machines is two states. Universality boundary values allow us to determine when it is not possible to further simplify an existing simple universal model.In recent years there has been huge growth in the study of biologically inspired models of computation. We wish to apply our research into the time/space efficiency of simple universal models to many of these biologically inspired models of computation. With more attempts being made in the direction of implementation of biologically inspired models of computation discovering these trade-offs is becoming more and more important. Our research will help answer many of the questions relevant to this developing area. This project will give new insight into classical and biologically inspired models of computation, program complexity, and time/space complexity, and will aid in the development of new simple efficient computational devices.