Abstract
We present small polynomial time universal Turing machines with state-symbol pairs of (5,5), (6,4), (9,3) and (18,2). These machines simulate our new variant of tag system, the bi-tag system and are the smallest known universal Turing machines with 5, 4, 3 and 2-symbols respectively. Our 5-symbol machine uses the same number of instructions (22) as the smallest known universal Turing machine by Rogozhin.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Baiocchi, C.: Three small universal Turing machines. In: Margenstern, M., Rogozhin, Y. (eds.) MCU 2001. LNCS, vol. 2055, pp. 1–10. Springer, Heidelberg (2001)
Cocke, J., Minsky, M.: Universality of tag systems with P= 2. Journal of the ACM 11(1), 15–20 (1964)
Hermann, G.: The uniform halting problem for generalized one state Turing machines. In: Proceedings, Ninth Annual Symposium on Switching and Automata Theory, New York, October 1968, pp. 368–372. IEEE, Los Alamitos (1968)
Kudlek, M.: Small deterministic Turing machines. Theoretical Computer Science 168(2), 241–255 (1996)
Kudlek, M., Rogozhin, Y.: A universal Turing machine with 3 states and 9 symbols. In: Kuich, W., Rozenberg, G., Salomaa, A. (eds.) DLT 2001. LNCS, vol. 2295, pp. 311–318. Springer, Heidelberg (2002)
Margenstern, M., Pavlotskaya, L.: On the optimal number of instructions for universality of Turing machines connected with a finite automaton. International Journal of Algebra and Computation 13(2), 133–202 (2003)
Minsky, M.: Size and structure of universal Turing machines using tag systems. In: Recursive Function Theory, Symposium in Pure Mathematics, Provelence, vol. 5, pp. 229–238. AMS (1962)
Minsky, M.: Computation, finite and infinite machines. Prentice-Hall, Englewood Cliffs (1967)
Neary, T.: Small polynomial time universal Turing machines. In: Hurley, T., Seda, A., et al. (eds.) 4th Irish Conference on the Mathematical Foundations of Computer Science and Information Technology(MFCSIT), Cork, Ireland, August 2006, pp. 325–329 (2006)
Neary, T., Woods, D.: A small fast universal Turing machine. Technical Report NUIM-CS-TR-2005-12, National university of Ireland, Maynooth (2005)
Neary, T., Woods, D.: Small fast universal Turing machines. Theoretical Computer Science 362(1–3), 171–195 (2006)
Pavlotskaya, L.: Solvability of the halting problem for certain classes of Turing machines. Mathematical Notes (Springer) 13(6), 537–541 (1973)
Pavlotskaya, L.: Dostatochnye uslovija razreshimosti problemy ostanovki dlja mashin T’juring. Problemi kibernetiki, 91–118 (1978) (Sufficient conditions for the halting problem decidability of Turing machines) (in Russian))
Robinson, R.: Minsky’s small universal Turing machine. International Journal of Mathematics 2(5), 551–562 (1991)
Rogozhin, Y.: Small universal Turing machines. Theoretical Computer Science 168(2), 215–240 (1996)
Shannon, C.E.: A universal Turing machine with two internal states. Automata Studies, Annals of Mathematics Studies 34, 157–165 (1956)
Woods, D., Neary, T.: On the time complexity of 2-tag systems and small universal Turing machines. In: FOCS. 47th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, California, October 2006, pp. 132–143. IEEE, Los Alamitos (2006)
Woods, D., Neary, T.: The complexity of small universal Turing machines. In: Cooper, S.B., Lowe, B., Sorbi, A. (eds.) Computability in Europe 2007. CIE, Sienna, Italy, June 2007. LNCS, vol. 4497, pp. 791–798. Springer, Heidelberg (2007)
Woods, D., Neary, T.: Small semi-weakly universal Turing machines. In: Durand-Lose, J., Margenstern, M. (eds.) Machines, Computations, and Universality (MCU), Orélans, France, September 2007. LNCS, vol. 4664, pp. 306–323. Springer, Heidelberg (2007)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Neary, T., Woods, D. (2007). Four Small Universal Turing Machines. In: Durand-Lose, J., Margenstern, M. (eds) Machines, Computations, and Universality. MCU 2007. Lecture Notes in Computer Science, vol 4664. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74593-8_21
Download citation
DOI: https://doi.org/10.1007/978-3-540-74593-8_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74592-1
Online ISBN: 978-3-540-74593-8
eBook Packages: Computer ScienceComputer Science (R0)