Abstract
We give small universal Turing machines with state-symbol pairs of (6,2), (3,3) and (2,4). These machines are weakly universal, which means that they have an infinitely repeated word to the left of their input and another to the right. They simulate Rule 110 and are currently the smallest known weakly universal Turing machines. Despite their small size these machines are efficient polynomial time simulators of Turing machines.
Turlough Neary is funded by the Irish Research Council for Science, Engineering and Technology and by Science Foundation Ireland Research Frontiers Programme grant number 07/RFP/CSMF641. Damien Woods was supported by a Project of Excellence from the Junta de Andalucía grant TIC-581, and by Science Foundation Ireland grant 04/IN3/1524.
This is a preview of subscription content, log in via an institution to check access.
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
References
Baiocchi, C.: 3N+1, UTM e tag-system. Technical Report Pubblicazione 98/38, Dipartimento di Matematico, Università di Roma (1998) (in Italian)
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)
Cook, M.: Universality in elementary cellular automata. Complex Systems 15(1), 1–40 (2004)
Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to parallel computation: P-completeness theory. Oxford University Press, Oxford (1995)
Hermann, G.: The uniform halting problem for generalized one state Turing machines. In: Proceedings, Ninth Annual Symposium on Switching and Automata Theory (FOCS), pp. 368–372. IEEE, New York (1968)
Hopcroft, J.E., Ullman, J.D.: Introduction to automata theory, languages, and computation. Addison-Wesley, Reading (1979)
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.: Frontier between decidability and undecidability: A survey. Theoretical Computer Science 231(2), 217–251 (2000)
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)
Michel, P.: Small Turing machines and the generalized busy beaver competition. Theoretical Computer Science 326(1-3), 45–56 (2004)
Minsky, M.: A 6-symbol 7-state universal Turing machines. Technical Report 54-G-027, MIT (1960)
Minsky, M.: Size and structure of universal Turing machines using tag systems. In: Recursive Function Theory, Proceedings, Symposium in Pure Mathematics, vol. 5, pp. 229–238. AMS, Provelence (1962)
Neary, T.: Small universal Turing machines. PhD thesis, Department of Computer Science, National University of Ireland, Maynooth (2008)
Neary, T., Woods, D.: P-completeness of cellular automaton Rule 110. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 132–143. Springer, Heidelberg (2006)
Neary, T., Woods, D.: Four small universal Turing machines. Fundamenta Informaticae 91(1), 123–144 (2009)
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) (in Russian)
Priese, L.: Towards a precise characterization of the complexity of universal and non-universal Turing machines. Siam journal of Computing 8(4), 508–523 (1979)
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)
Watanabe, S.: 5-symbol 8-state and 5-symbol 6-state universal Turing machines. Journal of ACM 8(4), 476–483 (1961)
Watanabe, S.: 4-symbol 5-state universal Turing machine. Information Processing Society of Japan Magazine 13(9), 588–592 (1972)
Wolfram, S.: A new kind of science. Wolfram Media, Champaign (2002)
Woods, D., Neary, T.: On the time complexity of 2-tag systems and small universal Turing machines. In: 47\(^{\textrm{th}}\) Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 439–448. IEEE, New York (2006)
Woods, D., Neary, T.: The complexity of small universal Turing machines: A survey. Theoretical Computer Science 410(4–5), 443–450 (2009)
Woods, D., Neary, T.: Small semi-weakly universal Turing machines. Fundamenta Informaticae 91(1), 179–195 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Neary, T., Woods, D. (2009). Small Weakly Universal Turing Machines. In: Kutyłowski, M., Charatonik, W., Gębala, M. (eds) Fundamentals of Computation Theory. FCT 2009. Lecture Notes in Computer Science, vol 5699. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03409-1_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-03409-1_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03408-4
Online ISBN: 978-3-642-03409-1
eBook Packages: Computer ScienceComputer Science (R0)