CaltechAUTHORS
  A Caltech Library Service

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

Neary, Turlough and Woods, Damien (2015) Maurice Margenstern’s Contributions to the Field of Small Universal Turing Machines. In: Automata, Universality, Computation. Emergence, Complexity and Computation. No.12. Springer , Cham, pp. 117-126. ISBN 978-3-319-09038-2. https://resolver.caltech.edu/CaltechAUTHORS:20170621-101004917

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170621-101004917

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://dx.doi.org/10.1007/978-3-319-09039-9_5DOIArticle
https://link.springer.com/chapter/10.1007%2F978-3-319-09039-9_5PublisherArticle
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.
Funders:
Funding AgencyGrant Number
Swiss National Science Foundation (SNSF)200021-141029
NASANNX13AJ56G
NSFCCF-0832824
NSFCCF-1317694
NSFCCF-1219274
NSFCCF-1162589
Series Name:Emergence, Complexity and Computation
Issue or Number:12
Record Number:CaltechAUTHORS:20170621-101004917
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20170621-101004917
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:78405
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:21 Jun 2017 17:39
Last Modified:03 Oct 2019 18:08

Repository Staff Only: item control page