matrix mortality; small universal Turing machines; time/space computational complexity; models of computation; Post correspondence problem; simple universal models of computation; decidability/undecidability
Cook Matthew, Larsson Urban, Neary Turlough (2017), A cellular automaton for blocking queen games, in Natural Computing
, 16(3), 397.
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
, Turku, Finland.
Neary Turlough, Woods Damien (2015), Tag Systems and the Complexity of Simple Programs, in Kari Jarkko (ed.), 11-16.
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
, Garching, Germany.
Finding simple (Turing) universal models of computation is an important aspect of the foundation of computer science, and there has been much interest in this direction. We find that there is an important subset of the simplest universal models that are used time after time to prove universality in many systems as well as to prove the undecidability of fundamental problems in mathematics and the theory of computing. For example, numerous models of computation have been proved universal by (directly or indirectly) simulating 2-tag systems, and as another example, the well known Post correspondence problem was used to prove numerous undecidability results including the zero-product ("mortality") problem for collections of matrices. While these systems have allowed us to find many new simple universal models and solve many open problems, there are a number of fundamental problems on which progress has stalled. For example, the mortality problem for 2×2 matrices has been open since 1977. This problem is equivalent to the problem of determining if a switched linear systems is controllable, and Bournez relates the reachability problem for piecewise-affine functions to another open problem on 2×2 matrices. Recently we reduced the mortality problem for 2×2 matrix semi-groups to a generalisation of the Collatz problem. It immediately follows that proving decidability of the mortality problem for 2×2 matrices would resolve the famous Collatz conjecture. Many of the gaps in the current theory can be filled by constructing new simple universal models that will give us new tools to make progress on these fundamental questions. We have found this constructive approach to be successful, as the introduction of new simple universal models has allowed us to make significant leaps forward on a number of open problems. We will use our expertise in the area of simple models of computation to develop new universal models that have applications to a wide variety of open problems.Resolving these types of fundamental open problems in mathematics and the theory of computing involves questions both of programmability (undecidability) and of efficiency. We will develop on the work that we have pioneered in the time/space analysis of simple universal models of computation. Given the large body of work devoted to simple models of computation and how important time and memory requirements are in practice, it is surprising that prior to our recent work very little time/space analysis was carried out for simple universal models of computation. The outstanding question in this area is this: Is a smaller and simpler computational model in general likely to be less efficient in terms of its time and space requirements at run-time? We have already solved important open questions in this area and exponentially improved the time efficiency of numerous models of computation. However, this research area is still quite new and many fundamental questions remain. During this project, we will continue to investigate the relationship between the program-size complexity of a model and its computational time/space complexity.In short, this project will develop new insights into models of computation, program complexity, and time/space complexity, as well as aid in the development of new simple efficient computational devices, while helping to solve fundamental open problems in mathematics and the theory of computation.