Published June 4, 2015
| public
Book Section - Chapter
Tag Systems and the Complexity of Simple Programs
- Creators
- Neary, Turlough
- Woods, Damien
- Other:
- Kari, Jarrko
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
- Eprint ID
- 63061
- Resolver ID
- CaltechAUTHORS:20151218-092251630
- 200021-141029
- Swiss National Science Foundation (SNSF)
- 200021-153295
- Swiss National Science Foundation (SNSF)
- NNX13AJ56G
- NASA
- CCF-0832824
- NSF
- CCF-1317694
- NSF
- CCF-1219274
- NSF
- Created
-
2015-12-19Created from EPrint's datestamp field
- Updated
-
2021-11-10Created from EPrint's last_modified field
- Series Name
- Lecture Notes in Computer Science
- Series Volume or Issue Number
- 9099