Abstract
With an UTM(3,9) we present a new small universal Turing machine with 3 states and 9 symbols, improving a former result of an UTM(3,10).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
C. Baiocchi, Three Small Universal Turing Machines. Proc. MCU’2001, ed. M. Margenstern, Yu. Rogozhin, Springer, LNCS 2055, pp. 1–10, 2001.
M.D. Davis and E.J. Weyuker, Computability, Complexity, and Languages. Academic Press, Inc., 1983.
M. Kudlek, Small deterministic Turing machines. Theoretical Computer Science, Elsevier Science B.V., vol. 168 (2), 1996, pp. 241–255.
M. Margenstern, Frontier between decidability and undecidability: a survey. Proc. of 2nd International Colloquium Universal Machines and Computations, vol.1, March 23–27, 1998, Metz, France, pp. 141–177.
M.L. Minsky, Size and structure of universal Turing machines using tag systems. Recursive Function Theory, Symp. in pure mathematics, Amer. Math. Soc., 5, 1962, pp. 229–238.
Gh. Păun,DNAComputing Based on Splicing: Universality Results. Proc. of 2nd International Colloquium Universal Machines and Computations, vol.1, March 23–27, 1998, Metz, France, pp. 67–91.
L.M. Pavlotskaya, Sufficient conditions for halting problem decidability of Turing machines. Avtomati i mashini (Problemi kibernetiki), Moskva, Nauka, 1978, vol. 33, pp. 91–118, (Russian).
R.M. Robinson, Minsky’s small universal Turing machine. International Journal of Mathematics, vol.2, N.5, 1991, pp. 551–562.
Yu. Rogozhin, Seven universal Turing machines. Systems and Theoretical Programming, Mat. Issled. no.69, Academiya Nauk Moldavskoi SSR, Kishinev, 1982, pp. 76–90, (Russian).
Yu. Rogozhin,A universal Turing machine with 10 states and 3 symbols. Izvestiya Akademii Nauk Respubliki Moldova, Matematika, 1992, N 4(10), pp. 80–82 (Russian).
Yu. Rogozhin, About Shannon’s problem for Turing machines. Computer Science Journal of Moldova, vol.1, no 3(3), 1993, pp. 108–111.
Yu. Rogozhin, Small universal Turing machines. Theoretical Computer Science, Elsevier Science B.V., vol. 168 (2), 1996, pp. 215–240.
Yu. Rogozhin,A Universal Turing Machine with 22 States and 2 Symbols. Romanian Journal of Information Science and Technology, vol. 1, N. 3, 1998, pp. 259–265.
C.E. Shannon, A universal Turing machine with two internal states. Automata studies, Ann. of Math. Stud. 34, Princeton, Princeton Univ.Press, 1956, pp. 157–165.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kudlek, M., Rogozhin, Y. (2002). A Universal Turing Machine with 3 States and 9 Symbols. In: Kuich, W., Rozenberg, G., Salomaa, A. (eds) Developments in Language Theory. DLT 2001. Lecture Notes in Computer Science, vol 2295. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46011-X_27
Download citation
DOI: https://doi.org/10.1007/3-540-46011-X_27
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43453-5
Online ISBN: 978-3-540-46011-4
eBook Packages: Springer Book Archive