Affiliations: California Institute of Technology, Pasadena, CA 91125, USA. woods@caltech.edu | Institute for Neuroinformatics, University of Zürich and ETH Zürich, Zürich, Switzerland. tneary@ini.phys.ethz.ch
Note: [] Supported by NASA grant NNX13AJ56G, and National Science Foundation grants 0832824 & 1317694 (The Molecular Programming Project), CCF-1219274 and CCF-1162589. Address for correspondence: California Institute of Technology, Pasadena, CA 91125, USA.
Note: [] Supported by Swiss National Science Foundation grant 200021-141029.
Abstract: In the field of small universal Turing machines, Yurii Rogozhin holds a special prize: he was first to close off an infinite number of open questions by drawing a closed curve that separates the infinite set of Turing machines that are universal from a finite set of small machines for which we don't yet know. Rogozhin did this by finding the smallest known universal Turing machines at the time, both in terms of number of states and number of symbols. This brief note summarises this and a few of Yurii's other contributions to the field, including his work with Manfred Kudlek on small circular Post machines.
