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 2015 | public
Book Section - Chapter

Maurice Margenstern's Contributions to the Field of Small Universal Turing Machines

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

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