Project

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

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

Active participation

Self-organised

Number	Title	Start	Funding scheme

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.