Published 2015
| public
Book Section - Chapter
Maurice Margenstern's Contributions to the Field of Small Universal Turing Machines
- Creators
- Neary, Turlough
- Woods, Damien
- Other:
- Adamatzky, Andrew
Abstract
On the occasion of his 65th birthday we survey some of the work of Maurice Margenstern on small universal Turing machines. Margenstern has been one of the most prolific contributors to this field, having constructed numerous small universal programs for a number of Turing machine models. These positive results are complemented by Margenstern's negative results, or lower bounds, on universal program size. Finally, he has even explored the space in-between the known program size upper and lower bounds by giving small programs that iterate the Collatz function, which suggests that proving negative results on programs of this size will be at least as hard as resolving the Collatz problem.
Additional Information
© 2015 Springer International Publishing Switzerland. Supported by Swiss National Science Foundation grant 200021-141029. Supported by the US National Aeronautics and Space Administration (NASA) grant NNX13AJ56G, and National Science Foundation (NSF) grants 0832824 & 1317694 (The Molecular Programming Project), CCF-1219274 and CCF-1162589.Additional details
- Eprint ID
- 78405
- Resolver ID
- CaltechAUTHORS:20170621-101004917
- 200021-141029
- Swiss National Science Foundation (SNSF)
- NNX13AJ56G
- NASA
- CCF-0832824
- NSF
- CCF-1317694
- NSF
- CCF-1219274
- NSF
- CCF-1162589
- NSF
- Created
-
2017-06-21Created from EPrint's datestamp field
- Updated
-
2021-11-15Created from EPrint's last_modified field
- Series Name
- Emergence, Complexity and Computation
- Series Volume or Issue Number
- 12