Project

Back to overview

Undecidability and efficiency in foundational models of computation

Applicant Cook Matthew
Number 153295
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.09.2014 - 31.08.2016
Approved amount 239'691.00
Show all

Keywords (7)

matrix mortality; small universal Turing machines; time/space computational complexity; models of computation; Post correspondence problem; simple universal models of computation; decidability/undecidability

Lay Summary (German)

Lead
Ein (Turing) universelles Rechenmodell kann jedes Problem lösen, das ein Algorithmus lösen kann. Vergleichsweise kann man sagen, dass die Mächtigkeit eines universellen Rechenmodelles derjenigen eines modernen Computers entspricht, wenn man praktische Einschränkungen wie Schnelligkeit oder Speicher-Gebrauch ausser Acht lässt. Einfache universelle Rechenmodelle haben wichtige Anwendungen, indem sie uns helfen, neue universelle Rechenmodelle zu finden, und indem sie die Unentscheidbarkeit grundlegender Probleme der Mathematik und der Rechentheorie beweisen. Wir werden neue einfache universelle Rechenmodelle entwickeln, die sich bei verschiedenen ungelösten Problemen der Mathematik und der Rechentheorie anwenden lassen. Ergänzend dazu werden wir die Effizienz der Resourcen Zeit und Speicher bei einfachen Rechenmodellen untersuchen. Dieses Projekt wird helfen, einfache effiziente Rechengeräte zu entwickeln und grundlegende ungelöste Probleme der Mathematik und der Rechentheorie zu lösen.
Lay summary
Einige der einfachsten universellen Rechenmodelle werden immer wieder gebraucht, um Universalität von vielen Systemen und die Unentscheidbarkeit grundlegender Probleme der Mathematik und der 
Rechentheorie zu beweisen. Obwohl diese Systeme es erlaubt haben, viele neue einfache universelle Rechenmodelle zu finden und viele ungelöste Probleme zu lösen, gibt es mehrere grundlegende Probleme, bei denen der Fortschritt abgerissen hat. Viele Lücken der aktuellen Theorie können geschlossen werden, indem neue einfache universelle Rechenmodelle konstruiert werden, die uns neue Werkzeuge geben, um bei diesen grundlegenden Problemen wieder Fortschritte zu machen. Wir werden unsere Kompetenz auf dem Gebiet der einfachen Rechenmodelle verwenden, um neue 
universelle Rechenmodelle zu entwickeln, die Anwendungen bei verschiedenen ungelösten Problemen haben.

Viele der grundlegenden ungelösten Probleme der Mathematik und der Rechentheorie, die wir lösen wollen, beinhalten nicht nur Fragen der Programmierbarkeit (Unentscheidbarkeit), aber auch Fragen der Effizienz. Aufgrund der Menge von Arbeiten, die über einfache Rechenmodelle geschrieben wurden, und der Wichtigkeit der Anforderungen an Schnelligkeit und Speicher in der Praxis ist es erstaunlich, dass für einfache universelle Rechenmodelle bis vor unserer neuesten Arbeit wenig Schnelligkeit/Speicher Analyse durchgeführt wurde. Die bedeutende Frage in diesem Gebiet ist folgende: Ist ein kleineres und einfacheres Rechenmodell im Allgemeinen bei Laufzeit eher weniger effizient, was Anforderungen an Schnelligkeit und Speicher betrifft? In diesem Projekt werden wir unsere bahnbrechende Arbeit über Schnelligkeit/Speicher Analyse von einfachen universellen Rechenmodellen weiterentwickeln.

Kurz gesagt, dieses Projekt wird neue Einblicke in Rechenmodelle, Programmkomplexität, Effizienz der Resourcen Zeit und Speicher gewähren und dabei auch helfen, grundlegende ungelöste Probleme der Mathematik und der Rechentheorie zu lösen.
Direct link to Lay Summary Last update: 28.08.2014

Lay Summary (English)

Lead
A (Turing) universal model of computation has the ability to solve any algorithmically solvable problem. To put this in a more familiar setting, we say that a universal model of computation has computing power equivalent to that of a modern personal computer ignoring the practical considerations of time or memory usage. Simple universal models of computation have important applications in helping us find new universal models of computation and in proving the undecidability of fundamental problems in mathematics and the theory of computing. We will develop new simple universal models that have applications to a wide variety of open problems in mathematics and the theory of computing. As a complementary aim we will also investigate the time/memory resource efficiency of simple models of computation. This project will aid in the development of new simple efficient computational devices, and help to solve fundamental open problems in mathematics and the theory of computation.
Lay summary
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. 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. 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 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.
 
Many of the fundamental open problems in mathematics and the theory of computing which we wish to resolve not only involve question of programmability (undecidability) but also questions of efficiency.  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/memory 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 memory requirements at run-time?  During this project, we will develop on the work that we have pioneered in the time/memory analysis of simple universal models of computation.

In short, this project will develop new insights into models of computation, program complexity, and time/memory resource efficiency, while helping to solve fundamental open problems in mathematics and the theory of computation.
Direct link to Lay Summary Last update: 28.08.2014

Responsible applicant and co-applicants

Employees

Publications

Publication
A cellular automaton for blocking queen games
Cook Matthew, Larsson Urban, Neary Turlough (2017), A cellular automaton for blocking queen games, in Natural Computing, 16(3), 397.
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, Turku, Finland.
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.
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, Garching, Germany.

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


Self-organised

Title Date Place

Associated projects

Number Title Start Funding scheme
141029 Time/Space Efficiency of Simple Classical and Biological Models of Computation 01.07.2012 Project funding
166231 Nondeterminism and NP-completeness in Simple Models of Computation 01.09.2016 Project funding

Abstract

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