Project

Back to overview

Time/Space Efficiency of Simple Classical and Biological Models of Computation

Applicant Cook Matthew
Number 141029
Funding scheme Project funding
Research institution Institut für Neuroinformatik Universität Zürich Irchel und ETH Zürich
Institution of higher education University of Zurich - ZH
Main discipline Information Technology
Start/End 01.07.2012 - 31.03.2015
Approved amount 246'315.00
Show all

Keywords (5)

models of computation; small universal Turing machines; simple universal models of computation; biologically inspired models of computation ; time/space complexity of simple machines

Lay Summary (English)

Lead
Lay summary
When speaking of computational power, the term ‘universal’ indicates having computing ability equivalent to that of a modern personal computer, or to a programming language such as Java, ignoring the practical considerations of time or memory usage. For many years now, there has been much interest in finding simple universal models of computation. However, given how important time and memory requirements are in practice, it is surprising that analysis of these issues in simple universal models of computation has only recently begun to receive attention. 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? Put another way, does there exist a trade-off between the complexity of a computational model and its performance?

We will investigate the relationship between the program-size complexity of a model and its computational time/space complexity. We will evaluate the effect of varying the different parameters 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 will also look for universality boundaries in different models. We take a parameter (or a set of parameters) in a model and ask the question: what is the smallest value of this parameter for which the model remains universal? Universality boundary values provide valuable information concerning the minimum size that a system can be while remaining arbitrarily programmable. In recent years there has been huge growth in the study of biologically inspired models of computation. Our proposed research into the time/space efficiency of simple universal models includes such biologically inspired models of computation. As experimentalists are developing implementations of these new styles of computation, our work finding the theoretical trade-offs in such systems will have more and more practical applications, providing the experimentalists with programmable-system targets that are computationally powerful yet experimentally reachable. 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.

Direct link to Lay Summary Last update: 21.02.2013

Responsible applicant and co-applicants

Employees

Publications

Publication
A Cellular Automaton for Blocking Queen Games
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.
Maurice Margenstern’s Contributions to the Field of Small Universal Turing Machines
Neary Turlough, Woods Damien (2015), Maurice Margenstern’s Contributions to the Field of Small Universal Turing Machines, in Adamatzky Andrew (ed.), 117-126.
Tag Systems and the Complexity of Simple Programs
Neary Turlough, Woods Damien (2015), Tag Systems and the Complexity of Simple Programs, in Kari Jarkko (ed.), 11-16.
Three small universal spiking neural P systems
Neary Turlough (2015), Three small universal spiking neural P systems, in Theoretical Computer Science, 567, 2-20.
Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words
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.
Yurii Rogozhin's Contributions to the Field of Small Universal Turing Machines
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.
Hasenjaeger’s electromechanical small universal Turing machine is time-efficient
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.
Wang’s B machines are efficiently universal, as is Hasenjaeger’s small universal electromechanical toy
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.

Collaboration

Group / person Country
Types of collaboration
Srinivas Turaga, Janelia Farm Research Campus United States of America (North America)
- in-depth/constructive exchanges on approaches, methods or results
Piotr Dudek, University of Manchester Great Britain and Northern Ireland (Europe)
- in-depth/constructive exchanges on approaches, methods or results

Scientific events

Active participation

Title Type of contribution Title of article or contribution Date Place Persons involved
The 21st annual international workshop on cellular automata and discrete complex systems AUTOMATA 2015 Talk given at a conference Tag Systems and the Complexity of Simple Programs 08.06.2015 Department of Mathematics and Statistics at the University of Turku, Turku, Finland Neary Turlough;
The 21st annual international workshop on cellular automata and discrete complex systems AUTOMATA 2015 Talk given at a conference A Cellular Automaton for Blocking Queen Games 08.06.2015 Department of Mathematics and Statistics at the University of Turku, Turku, Finland Cook Matthew;
The 32nd Symposium on Theoretical Aspects of Computer Science Talk given at a conference Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words 04.03.2015 Technische Universität München, Germany Neary Turlough;
Turing in Context II Talk given at a conference Hasenjaeger’s electromechanical small universal Turing machine is time efficient 10.10.2012 Royal Flemish Academy of Belgium for the Sciences and Arts, Brussels, Belgium Neary Turlough;


Self-organised

Title Date Place
Machines, Computations and Universality 2013 09.09.2013 Zurich, Switzerland

Associated projects

Number Title Start Funding scheme
153295 Undecidability and efficiency in foundational models of computation 01.09.2014 Project funding

Abstract

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.
-