Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 4, 2015 | public
Book Section - Chapter

Tag Systems and the Complexity of Simple Programs

Abstract

In this mini-survey we discuss time complexity and program size results for universal Turing machines, tag systems, cellular automata, and other simple models of computation. We discuss results that show that many of the simplest known models of computation including the smallest known universal Turing machines and the elementary cellular automaton Rule 110 are efficient simulators of Turing machines. We also recall a recent result where the halting problem for tag systems with only 2 symbols (the minimum possible) is proved undecidable. This result has already yielded applications including a significant improvement on previous undecidability bounds for the Post correspondence problem and the matrix mortality problem.

Additional Information

© 2015 Springer. Turlough Neary is supported by Swiss National Science Foundation grants 200021-141029 and 200021-153295. Damien Woods is supported by NASA grant NNX13AJ56G, and National Science Foundation grants 0832824 & 1317694 (The Molecular Programming Project), CCF-1219274 and CCF-1162589.

Additional details

Created:
August 20, 2023
Modified:
January 13, 2024