Small Semi-Weakly Universal Turing Machines

• Autorzy: Woods D. , Neary T.
• Języki publikacji: EN

Abstrakty

EN

We present three small universal Turing machines that have 3 states and 7 symbols, 4 states and 5 symbols, and 2 states and 13 symbols, respectively. These machines are semi-weakly universal which means that on one side of the input they have an infinitely repeated word, and on the other side there is the usual infinitely repeated blank symbol. This work can be regarded as a continuation of early work by Watanabe on semi-weak machines. One of our machines has only 17 transition rules, making it the smallest known semi-weakly universal Turing machine. Interestingly, two of our machines are symmetric withWatanabe's 7-state and 3-symbol, and 5-state and 4-symbol machines, even though we use a different simulation technique.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 91, nr 1
• Strony: 179--195
• Opis fizyczny: bibliogr. 34 poz.

Twórcy

autor

Woods D.

autor

Neary T.

• Department of Computer Science and Artificial Intelligence University of Seville, Spain,

Bibliografia

• [1] C. Baiocchi. 3N+1, UTMe tag-system. Technical Report Pubblicazione 98/38, Dipartimento di Matematico, Università di Roma, 1998. (In Italian).
• [2] C. Baiocchi. Three small universal Turing machines. In M. Margenstern and Y. Rogozhin, editors, Machines, Computations, and Universality, volume 2055 of LNCS, pages 1-10, Chisinău, Moldova, May 2001. MCU, Springer.
• [3] J. Cocke and M. Minsky. Universality of tag systems with P = 2. Journal of the Association for Computing Machinery, 11(1):15-20, Jan. 1964.
• [4] M. Cook. Universality in elementary cellular automata. Complex Systems, 15(1):1-40, 2004.
• [5] G. T. Hermann. The uniform halting problem for generalized one state Turing machines. In Proceedings of the ninth annual Symposium on Switching and Automata Theory (FOCS), pages 368-372, Schenectady, New York, Oct. 1968. IEEE Computer Society Press.
• [6] M. Kudlek. Small deterministic Turing machines. Theoretical Computer Science, 168(2):241-255, 1996.
• [7] M. Kudlek and Y. Rogozhin. A universal Turing machine with 3 states and 9 symbols. In Developments in Language Theory (DLT) 2001, volume 2295 of LNCS, pages 311-318, Vienna, May 2002. Springer.
• [8] M. Margenstern. Frontier between decidability and undecidability: a survey. Theoretical Computer Science, 231(2):217-251, Jan. 2000.
• [9] M. Margenstern and L. Pavlotskaya. 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, Apr. 2003.
• [10] P. Michel. Small Turing machines and generalized busy beaver competition. Theoretical Computer Science, 326:45-56, Oct. 2004.
• [11] M. Minsky. A 6-symbol 7-state universal Turing machines. Technical Report 54-G-027,MIT, Aug. 1960.
• [12] M. Minsky. Size and structure of universal Turing machines using tag systems. In Recursive Function Theory: Proceedings, Symposium in Pure Mathematics, volume 5, pages 229-238, Provelence, 1962. AMS.
• [13] T. Neary. Small polynomial time universal Turing machines. In Fourth Irish Conference on the Mathematical Foundations of Computer Science and Information Technology (MFCSIT'06), pages 325-329, Ireland, 2006. University College Cork.
• [14] T. Neary. Small universal Turing machines. PhD thesis, National University of Ireland, Maynooth, 2008.
• [15] T. Neary and D. Woods. Four small universal Turing machines. Fundamenta Informaticae. 91:105-126. 2009
• [16] T. Neary and D. Woods. P-completeness of cellular automaton Rule 110. In M. Bugliesi et al., editor, International Colloquium on Automata Languages and Programming (ICALP), volume 4051 (Part I) of Lecture Notes in Computer Science, pages 132-143. Springer, July 2006.
• [17] T. Neary and D.Woods. Small fast universal Turingmachines. Theoretical Computer Science, 362(1-3):171-195, Oct. 2006.
• [18] T. Neary and D. Woods. Four small universal Turing machines. In J. Durand-Lose and M. Margenstern, editors, Machines, Computations and Universality (MCU), volume 4664 of LNCS, pages 242-254, Orléans, France, Sept. 2007. Springer.
• [19] T. Neary and D. Woods. Small weakly universal Turing machines, July 2007. arXiv:0707.4489v1 [cs.CC].
• [20] L. Pavlotskaya. Solvability of the halting problem for certain classes of Turing machines. Mathematical Notes (Springer), 13(6):537-541, June 1973. (Translated fromMatematicheskie Zametki, Vol. 13, No. 6, pp. 899-909, June, 1973).
• [21] L. Pavlotskaya. Dostatochnye uslovija razreshimosti problemy ostanovki dlja mashin T'juring. Problemy Kibernetiki, 33:91-118, 1978. (Sufficient conditions for the halting problem decidability of Turingmachines. In Russian).
• [22] L. Pavlotskaya. On machines, universal by extensions. Theoretical Computer Science, 168(2):257-266,Nov. 1996.
• [23] L. Priese. Towards a precise characterization of the complexity of universal and nonuniversal Turing machines. SIAM Journal on Computing, 8(4):508-523, 1979.
• [24] R.M. Robinson. Minsky's small universal Turing machine. International Journal of Mathematics, 2(5):551-562, 1991.
• [25] Y. Rogozhin. Sem' universal'nykh mashin T'juringa. Systems and theoretical programming, Mat. Issled., 69:76-90, 1982. (Seven universal Turing machines. In Russian).
• [26] Y. Rogozhin. Small universal Turing machines. Theoretical Computer Science, 168(2):215-240,Nov. 1996.
• [27] C. E. Shannon. A universal Turing machine with two internal states. Automata Studies, Annals of Mathematics Studies, 34:157-165, 1956.
• [28] S. Watanabe. On a minimal universal Turing machine. Technical report, MCB Report, Tokyo, Aug. 1960.
• [29] S. Watanabe. 5-symbol 8-state and 5-symbol 6-state universal Turing machines. Journal of the ACM, 8(4):476-483, Oct. 1961.
• [30] S.Watanabe. 4-symbol 5-state universal Turingmachine. Information Processing Society of Japan Magazine, 13(9):588-592, Sept. 1972.
• [31] S. Wolfram. A new kind of science. Wolfram Media, Inc., 2002.
• [32] D. Woods and T. Neary. The complexity of small universal Turing machines. Theoretical computer Science, 410(4-5):443-450, Feb. 2009.
• [33] D. Woods and T. Neary. On the time complexity of 2-tag systems and small universal Turing machines. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 439-446, Berkeley, California, Oct. 2006. IEEE.
• [34] D. Woods and T. Neary. Small semi-weakly universal Turing machines. In J. Durand-Lose and M. Margenstern, editors, Machines, Computations and Universality (MCU), volume 4664 of LNCS, pages 303-315, Orléans, France, Sept. 2007. Springer.