Small universal Turing machines. (English) Zbl 0874.68106

Summary: Let UTM\((m,n)\) be the class of universal Turing machine with \(m\) states and \(n\) symbols. Universal Turing machines are proved to exist in the following classes: UTM(24,2), UTM(10,3), UTM(7,4), UTM(5,5), UTM(4,6), UTM(3,10) and UTM(2,18).


68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI


[1] Davis, M., The definition of the universal Turing machine, (Proc. Amer. Math. Soc., 8 (1957)), 1125-1126 · Zbl 0084.01003
[2] Davis, M. D.; Weyuker, E. J., Computability, Complexity, and Languages (1983), Academic Press: Academic Press New York · Zbl 0569.68042
[3] Diekert, V.; Kudlek, M., Small deterministic Turing machines, (Papers on Automata and Languages (1989), Dep. of.Math., Karl Marx Univ. of Economics: Dep. of.Math., Karl Marx Univ. of Economics Budapest), 77-87, 188-4
[4] Herman, G. T., A new hierarchy of elementary functions, (Proc. Amer. Math. Soc., 20 (1969)), 557-562 · Zbl 0181.01201
[5] Kudlek, M., Small deterministic Turing machines, Theoret. Comput. Sci., 168, 241-255 (1996), (this Vol.) · Zbl 0876.03019
[6] Maltsev, A. I., The Algorithms and Recursive Functions (1986), Nauka: Nauka Moskva, (Russian)
[7] Margenstern, M., Non erasing Turing machines: a frontier between a decidable halting problem and universality, (Proc. FCT’93. Proc. FCT’93, Lecture Notes in Computer Science, Vol. 710 (1993)), 375-385 · Zbl 0794.68047
[8] Minsky, M. L., Size and structure of universal Turing machines using tag systems, (Recursive Function Theory, Symp. in Pure Mathematics, Vol. 5 (1962), Amer. Mathematical Soc: Amer. Mathematical Soc Provelence, RS), 229-238 · Zbl 0192.06601
[9] Nozaki, A., On notion of universality of turing machine, Kybernetika, 5, 29-42 (1969) · Zbl 0167.01504
[10] Pavlotskaya, L. M., (Problemi kibernetiki, Vol. 33 (1978), Nauka: Nauka Moskva), 91-118, (Russian)
[11] Priese, L., Towards a precise characterization of the complexity of the universal and nonuniversal Turing machines, SIAM J. Comput., 8, 508-523 (1979) · Zbl 0426.68024
[12] Robinson, R. M., Minsky’s small universal Turing machine, Internat. J. Math., 2, 551-562 (1991) · Zbl 0792.68040
[13] Rogozhin, Yu. V., Seven universal Turing machines, (Systems and Theoretical Programming. Systems and Theoretical Programming, Mat. Issled. no.69 (1982), Academiya Nauk Moldavskoi SSR: Academiya Nauk Moldavskoi SSR Kishinev), 76-90, (Russian) · Zbl 0515.03020
[14] Rogozhin, Yu. V., A universal Turing machine with 10 states and 3 symbols, Izvestiya Akademii Nauk Respubliki Moldova, Matematika, 4, 10, 80-82 (1992), (Russian) · Zbl 0900.68210
[15] Rogozhin, Yu. V., About Shannon’s problem for Turing machines, Comput. Sci. J. Moldova, 1, 3, 108-111 (1993), (3)
[16] Rogozhin, Yu. V., On the notion of universality and Shannon’s problem for Turing machines, (MCU/UMC’95, International Workshop ‘Universal Machines and Computations’. MCU/UMC’95, International Workshop ‘Universal Machines and Computations’, Lecture Abstracts (29-31 March 1995)), 36-39, Paris
[17] Shannon, C. E., A universal Turing machine with two internal states, (Automata Studies. Automata Studies, Ann. Math. Stud., Vol. 34 (1956), Princeton Univ.Press: Princeton Univ.Press Princeton), 157-165
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.