Abstract
We survey some work concerned with small universal Turing machines, cellular automata, tag systems, and other simple models of computation. For example it has been an open question for some time as to whether the smallest known universal Turing machines of Minsky, Rogozhin, Baiocchi and Kudlek are efficient (polynomial time) simulators of Turing machines. These are some of the most intuitively simple computational devices and previously the best known simulations were exponentially slow. We discuss recent work that shows that these machines are indeed efficient simulators. In addition, another related result shows that Rule 110, a well-known elementary cellular automaton, is efficiently universal. We also discuss some old and new universal program size results, including the smallest known universal Turing machines. We finish the survey with results on generalised and restricted Turing machine models including machines with a periodic background on the tape (instead of a blank symbol), multiple tapes, multiple dimensions, and machines that never write to their tape. We then discuss some ideas for future work.
This paper is extended and updated from [110]. T. Neary is supported by Science Foundation Ireland, Grant Number 09/RFP/CMS2212. D. Woods is supported by National Science Foundation Grant 0832824, the Molecular Programming Project. We thank Astrid Haberleitner for her tireless work in translating a number of highly technical papers from German to English, and Beverley Henley for her support.
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
Aanderaa, S., Fischer, P.C.: The solvability of the halting problem for 2-state post machines. Journal of the Association for Computing Machinery 14(4), 677–682 (1967)
Aaronson, S.: Book review: A new kind of science. Quantum Information and Computation 2(5), 410–423 (2002)
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)
Bennett, C.H.: Logical reversibility of computation. IBM Journal of Research and Development 17(6), 525–532 (1973)
Brady, A.H.: The determination of the value of Rado’s noncomputable function Σ(k) for four-state Turing machines. Mathematics of Computation 40(163), 647–665 (1983)
Brady, A.H.: The busy beaver game and the meaning of life. In: Herken, R. (ed.) The Universal Turing Machine: A Half-Century Survey, pp. 259–277. Oxford University Press (1988)
Cocke, J., Minsky, M.: Universality of tag systems with P = 2. Journal of the Association for Computing Machinery 11(1), 15–20 (1964)
Cook, M.: Universality in elementary cellular automata. Complex Systems 15(1), 1–40 (2004)
Cook, M.: A Concrete View of Rule 110 Computation. Electronic Proceedings in Theoretical Computer Science 1, 31–55 (2009)
De Mol, L.: Study of Limits of Solvability in Tag Systems. In: Durand-Lose, J., Margenstern, M. (eds.) MCU 2007. LNCS, vol. 4664, pp. 170–181. Springer, Heidelberg (2007)
Fischer, P.C.: On formalisms for Turing machines. Journal of the Association for Computing Machinery 12(4), 570–580 (1965)
Fischer, P.C., Meyer, A.R., Rosenberg, A.L.: Counter machines and counter languages. Mathematical Systems Theory 2(3), 265–283 (1968)
Friedman, J.: A decision procedure for computations of finite automata. Journal of the ACM 9(3), 315–323 (1962)
Gajardo, A., Moreira, A., Goles, E.: Complexity of Langton’s ant. Discrete Applied Mathematics 117, 41–50 (2002)
Green, M.W.: A lower bound on Rado’s sigma function for binary Turing machines. In: Proceedings of the 5th IEEE Annual Symposium on Switching Circuit Theory and Logical Design, pp. 91–94 (1964)
Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to parallel computation: P-completeness theory. Oxford university Press, Oxford (1995)
Harju, T., Margenstern, M.: Splicing Systems for Universal Turing Machines. In: Ferretti, C., Mauri, G., Zandron, C. (eds.) DNA 2004. LNCS, vol. 3384, pp. 149–158. Springer, Heidelberg (2005)
Hermann, G.T.: The uniform halting problem for generalized one state Turing machines. In: Proceedings of the Ninth Annual Symposium on Switching and Automata Theory (FOCS), pp. 368–372. IEEE Computer Society Press, Schenectady (1968)
Hermann, G.T.: The halting problem of one state Turing machines with n-dimensional tape. Mathematical Logic Quarterly 14(7-12), 185–191 (1968)
Hooper, P.: Some small, multitape universal Turing machines. Technical report, Computation Laboratory, Harvard University, Cambridge, Massachusetts (1963)
Hooper, P.: Some small, multitape universal Turing machines. Information Sciences 1(2), 205–215 (1969)
Ikeno, N.: A 6-symbol 10-state universal Turing machine. In: Proceedings, Institute of Electrical Communications, Tokyo (1958)
Kleine-Büning, H.: Über probleme bei homogener Parkettierung von ℤ×ℤ durch Mealy-automaten bei normierter verwendung. PhD thesis, Institut für Mathematische Logik, Münster (1977)
Kleine-Büning, H., Ottmann, T.: Kleine universelle mehrdimensionale Turingmaschinen. Elektronische Informationsverarbeitung und Kybernetik 13(4-5), 179–201 (1977) (in German)
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)
Lafitte, G., Papazian, C.: The Fabric of Small Turing Machines. In: Cooper, S.B., Löwe, B., Sorbi, A. (eds.) CiE 2007. LNCS, vol. 4497, pp. 219–227. Springer, Heidelberg (2007)
Langton, C.: Studying artificial life with cellular automata. Physica D 2(1-3), 120–149 (1986)
Lin, S., Rado, T.: Computer studies of Turing machine problems. Journal of the ACM 12(2), 196–212 (1965)
Lindgren, K., Nordahl, M.G.: Universal computation in simple one-dimensional cellular automata. Complex Systems 4(3), 299–318 (1990)
Margenstern, M.: Surprising areas in the quest for small universal devices. Electronic Notes in Theoretical computer Science 225, 201–220 (2009)
Margenstern, M.: Sur la frontière entre machines de Turing á arrêt décidable et machines de Turing universelles. Technical Report 92-83, LITP Institut Blaise Pascal (1992)
Margenstern, M.: Non-erasing Turing Machines: A Frontier Between a Decidable Halting Problem and Universality. In: Ésik, Z. (ed.) FCT 1993. LNCS, vol. 710, pp. 375–385. Springer, Heidelberg (1993)
Margenstern, M.: Une machine de Turing universelle sur {0,1}, non-effaçante et à trois instructions gauches. Technical Report 94-08, LITP Institut Blaise Pascal (1994)
Margenstern, M.: Non-Erasing Turing Machines: A New Frontier Between a Decidable Halting Problem and Universality. In: Baeza-Yates, R.A., Poblete, P.V., Goles, E. (eds.) LATIN 1995. LNCS, vol. 911, pp. 386–397. Springer, Heidelberg (1995)
Margenstern, M.: Une machine de Turing universelle non-effaçante à exactement trois instructions gauches. C. R. Acad. Sci. Paris, Série I 320, 101–106 (1995)
Margenstern, M.: Decidability and Undecidability of the Halting Problem on Turing Machines, a Survey. In: Adian, S., Nerode, A. (eds.) LFCS 1997. LNCS, vol. 1234, pp. 226–236. Springer, Heidelberg (1997)
Margenstern, M.: The laterality problem for non-erasing Turing machines on {0, 1} is completely solved. Theoretical Informatics and Applications 31(2), 159–204 (1997)
Margenstern, M.: Frontier between decidability and undecidability: a survey. In: Margenstern, M. (ed.) Machines, Computations, and Universality (MCU), France, vol. 1, pp. 141–177 (1998)
Margenstern, M.: Frontier between decidability and undecidability: a survey. Theoretical Computer Science 231(2), 217–251 (2000)
Margenstern, M.: On quasi-unilateral universal Turing machines. Theoretical Computer Science 257(1-2), 153–166 (2001)
Margenstern, M.: An algorithm for building intrinsically universal cellular automata in hyperbolic spaces. In: Proceedings of the 2006 International Conference on Foundations of Computer Science (FCS), Las Vegas, NV, pp. 3–9. CSREA Press (2006)
Margenstern, M., Pavlotskaya, L.: Deux machines de Turing universellesá au plus deux instructions gauches. C. R. Acad. Sci. Paris, Série I 320, 1395–1400 (1995)
Margenstern, M., Pavlotskaya, L.: Vers ue nouvelle approche de l’universalité concernant les machines de Turing. Technical Report 95-58, LITP Institut Blaise Pascal (1995)
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)
Marxen, H., Buntrock, J.: Attacking the Busy Beaver 5. Bulletin of the EATCS 40, 247–251 (1990)
Michel, P.: Busy beaver competition and Collatz-like problems. Archive Mathematical Logic 32(5), 351–367 (1993)
Michel, P.: Small Turing machines and generalized busy beaver competition. Theoretical Computer Science 326, 45–56 (2004)
Michel, P.: The busy beaver competition: a historical survey, arXiv:0906.3749v2 (2010), http://www.logique.jussieu.fr/~michel/ha.html
Minsky, M.: A 6-symbol 7-state universal Turing machines. Technical Report 54-G-027, MIT (1960)
Minsky, M.: Recursive unsolvability of Post’s tag problem. Technical Report 54-G-023, Massachusetts Institute of Technology (1960)
Minsky, M.: Recursive unsolvability of Post’s problem of “tag” and other topics in theory of Turing machines. Annals of Mathematics 74(3), 437–455 (1961)
Minsky, M.: Size and structure of universal Turing machines using tag systems. In: Recursive Function Theory: Proceedings, Symposium in Pure Mathematics, Provelence, vol. 5, pp. 229–238 (1962)
Minsky, M.: Universality of (p=2) tag systems and a 4 symbol 7 state universal Turing machine. In: AIM-33, A.I. memo 33, Computer Science and Artificial Intelligence Laboratory. MIT, Cambridge (1962)
Minsky, M.: Computation, finite and infinite machines. Prentice-Hall, Englewood Cliffs (1967)
Moore, C., Mertens, S.: The Nature of Computation. Oxford University Press (2011)
Moore, C.: Quasi-linear cellular automata. Physica D 103, 100–132 (1997)
Moore, C.: Predicting non-linear cellular automata quickly by decomposing them into linear ones. Physica D 111, 27–41 (1998)
Moore, E.F.: A simplified universal Turing machine. In: ACM National Meeting, Toronto, Canada, pp. 50–54. ACM Press (1952)
Morita, K., Shirasaki, A., Gono, Y.: A 1-tape 2-symbol reversible Turing machine. The Transactions of the IEICE Japan E72(3), 223–228 (1989)
Morita, K., Yamaguchi, Y.: A Universal Reversible Turing Machine. In: Durand-Lose, J., Margenstern, M. (eds.) MCU 2007. LNCS, vol. 4664, pp. 90–98. Springer, Heidelberg (2007)
Neary, T.: Small universal Turing machines. PhD thesis, 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, Part I. LNCS, vol. 4051, pp. 132–143. Springer, Heidelberg (2006)
Neary, T., Woods, D.: Small fast universal Turing machines. Theoretical Computer Science 362(1-3), 171–195 (2006)
Neary, T., Woods, D.: Four Small Universal Turing Machines. In: Durand-Lose, J., Margenstern, M. (eds.) MCU 2007. LNCS, vol. 4664, pp. 242–254. Springer, Heidelberg (2007)
Neary, T., Woods, D.: Small weakly universal Turing machines, arXiv:0707.4489v1 [cs.CC] (2007)
Neary, T., Woods, D.: Small Weakly Universal Turing Machines. In: Kutyłowski, M., Charatonik, W., Gębala, M. (eds.) FCT 2009. LNCS, vol. 5699, pp. 262–273. Springer, Heidelberg (2009)
Neary, T., Woods, D.: Four small universal Turing machines. Fundamenta Informaticae 91(1), 123–144 (2009)
Nozaki, A.: On the notion of universality of Turing machine. Kybernetika Academia Praha 5(1), 29–43 (1969) (English translated version)
Ollinger, N.: The Quest for Small Universal Cellular Automata. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 318–329. Springer, Heidelberg (2002)
Ollinger, N., Richard, G.: Four states are enough? Theoretical Computer Science 412(1-2), 22–32 (2011)
Ottmann, T.: Eine universelle Turingmaschine mit zweidimensionalem band. Elektronische Informationsverarbeitung und Kybernetik 11(1-2), 27–38 (1975) (in German)
Ottmann, T.: Einfache universelle mehrdimensionale Turingmaschinen. Habilitationsschrift, Karlsruhe (1975)
Pavlotskaya, L.: Solvability of the halting problem for certain classes of Turing machines. Mathematical Notes 13(6), 537–541; Translated from Matematicheskie Zametki, 13(6), 899–909 (1973)
Pavlotskaya, L.: O minimal’nom chisle razlichnykh kodov vershin v grafe universal’noj mashiny T’juringa. Disketnyj Analiz, Sbornik Trudov Instituta Matematiki SO AN SSSR 27, 52–60 (1975); On the minimal number of distinct codes for the vertices of the graph of a universal Turing machine (in Russian)
Pavlotskaya, L.: Dostatochnye uslovija razreshimosti problemy ostanovki dlja mashin T’juring. Avtomaty i Mashiny, 91–118 (1978); Sufficient conditions for the halting problem decidability of Turing machines (in Russian)
Pavlotskaya, L.: On machines, universal by extensions. Theoretical Computer Science 168(2), 257–266 (1996)
Post, E.L.: Formal reductions of the general combinatorial decision problem. American Journal of Mathmatics 65(2), 197–215 (1943)
Post, E.L.: Recursive unsolvability of a problem of Thue. Journal of Symbolic Logic 12(1), 1–11 (1947)
Post, E.L.: Absolutely unsolvable problems and relatively undecidable propositions – account of an anticipation. In: Davis, M. (ed.) The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, pp. 340–406. Raven Press, New York (1965); Corrected republication. Dover publications, New York (2004)
Priese, L.: Towards a precise characterization of the complexity of universal and nonuniversal Turing machines. SIAM J. Comput. 8(4), 508–523 (1979)
Rado, T.: On non-computable functions. Bell System Technical Journal 41(3), 877–884 (1962)
Richard, G.: A particular universal cellular automaton, HAL research report (oai:hal.archives-ouvertes.fr:hal-00095821_v1) (2006)
Robinson, R.M.: Undecidability and nonperiodicity for tilings of the plane. Inventiones Mathematicae 12(3), 177–209 (1971)
Robinson, R.M.: Minsky’s small universal Turing machine. International Journal of Mathematics 2(5), 551–562 (1991)
Rogozhin, Y.: Sem’ universal’nykh mashin T’juringa. In: Fifth All Union Conference on Mathematical Logic, Akad. Naul SSSR. Otdel. Inst. Mat., Novosibirsk, p. 27 (1979); Seven universal Turing machines (in russian)
Rogozhin, Y.: Sem’ universal’nykh mashin T’juringa. Systems and Theoretical Programming, Mat. Issled 69, 76–90 (1982); Seven universal Turing machines (in Russian)
Rogozhin, Y.: Universal’naja mashina T’juringa s 10 sostojanijami i 3 simvolami. Izvestiya Akademii Nauk Respubliki Moldova, Matematika 4(10), 80–82 (1992); A universal Turing machine with 10 states and 3 symbols (in Russian)
Rogozhin, Y.: About Shannon’s problem for Turing machines. Computer Science Journal of Moldova 1(3), 108–111 (1993)
Rogozhin, Y.: Small universal Turing machines. Theoretical Computer Science 168(2), 215–240 (1996)
Rogozhin, Y.: A universal Turing machine with 22 states and 2 symbols. Romanian Journal of Information Science and Technology 1(3), 259–265 (1998) (in Russian)
Rogozhin, Y., Verlan, S.: On the Rule Complexity of Universal Tissue P Systems. In: Freund, R., Păun, G., Rozenberg, G., Salomaa, A. (eds.) WMC 2005. LNCS, vol. 3850, pp. 356–362. Springer, Heidelberg (2006)
Rothemund, P.W.K.: A DNA and restriction enzyme implementation of Turing Machines. In: Lipton, R.J., Baum, E.B. (eds.) DNA Based Computers: Proceeding of a DIMACS Workshop. DIMACS, vol. 2055, pp. 75–119. Princeton University, AMS (1996)
Shannon, C.E.: A universal Turing machine with two internal states. Automata Studies, Annals of Mathematics Studies 34, 157–165 (1956)
Siegelmann, H.T., Margenstern, M.: Nine switch-affine neurons suffice for Turing universality. Neural Networks 12(4-5), 593–600 (1999)
Schroeppel, R.: A two counter machine cannot calculate 2n. Technical Report AIM-257, A.I. memo 257, Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA (1972)
Takahashi, H.: Keisankikai II. Iwanami, Tokyo (1958); Computing machine II (in Japanese)
Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society 2(42), 230–265 (1936)
Wagner, K.: Universelle Turingmaschinen mit n-dimensionale band. Elektronische Informationsverarbeitung und Kybernetik 9(7-8), 423–431 (1973); Universal Turing machines with n-dimensional tapes (in German)
Wang, H.: A variant to Turing’s theory of computing machines. Journal of the Association for Computing Machinery 4(1), 63–92 (1957)
Wang, H.: Tag systems and lag systems. Mathematical Annals 152(4), 65–74 (1963)
Watanabe, S.: On a minimal universal Turing machine. Technical report, MCB Report, Tokyo (1960)
Watanabe, S.: 5-symbol 8-state and 5-symbol 6-state universal Turing machines. Journal of the 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.: Statistical mechanics of cellular automata. Reviews of Modern Physics 55(3), 601–644 (1983)
Wolfram, S.: A new kind of science. Wolfram Media, Inc. (2002)
Woods, D., Neary, T.: On the time complexity of 2-tag systems and small universal Turing machines. In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 439–446. IEEE, Berkeley (2006)
Woods, D., Neary, T.: Small Semi-Weakly Universal Turing Machines. In: Durand-Lose, J., Margenstern, M. (eds.) MCU 2007. LNCS, vol. 4664, pp. 303–315. Springer, Heidelberg (2007)
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
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Neary, T., Woods, D. (2012). The Complexity of Small Universal Turing Machines: A Survey. In: Bieliková, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Turán, G. (eds) SOFSEM 2012: Theory and Practice of Computer Science. SOFSEM 2012. Lecture Notes in Computer Science, vol 7147. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-27660-6_32
Download citation
DOI: https://doi.org/10.1007/978-3-642-27660-6_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-27659-0
Online ISBN: 978-3-642-27660-6
eBook Packages: Computer ScienceComputer Science (R0)