Abstract
We are interested by “small” Universal Turing Machines (in short: UTMs), in the framework of 2, 3 or 4 tape—symbols. In particular:
-
tape—symbols. Apart from the old 24—states machine constructed by Rogozhin in 1982, we know two recent examples requiring 22 states, one due to Rogozhin and one to the author.
-
tape—symbols. The best example we know, due to Rogozhin, requires 10 states. It uses a strategy quite hard to follow, in particular because even—length productions require a different treatment with respect to odd—length ones.
-
tape—symbols. The best known machines require 7 states. Among them, the Rogozhin’s one require only 26 commands; the Robinson’s one, though requiring 27 commands, fournishes an easier way to recover the output when the TM halts. In particular, Robinson asked for a 7 × 4 UTM with only 26 commands and an easy treatment of the output.
Here we will firstly construct a 7 × 4 UTM with an easy recover of the output which requires only 25 commands; then we will simulate such a machine by a (simple) 10 × 3 UTM and by a 19 × 2 UTM.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Baiocchi, C. (2001). Three Small Universal Turing Machines. In: Margenstern, M., Rogozhin, Y. (eds) Machines, Computations, and Universality. MCU 2001. Lecture Notes in Computer Science, vol 2055. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45132-3_1
Download citation
DOI: https://doi.org/10.1007/3-540-45132-3_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42121-4
Online ISBN: 978-3-540-45132-7
eBook Packages: Springer Book Archive