Four Small Universal Turing Machines

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

Abstrakty

EN

We present universal Turing machines with state-symbol pairs of (5, 5), (6, 4), (9, 3) and (15, 2). These machines simulate our new variant of tag system, the bi-tag system and are the smallest known single-tape universal Turing machines with 5, 4, 3 and 2-symbols, respectively. Our 5-symbolmachine uses the same number of instructions (22) as the smallest known universal Turing machine by Rogozhin. Also, all of the universalmachines we present here simulate Turing machines in polynomial time.

Słowa kluczowe

EN

small universal Turing machine; 2-tag system; bi-tag systems; Post system; computational complexity; polynomial time

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 91, nr 1
• Strony: 123--144
• Opis fizyczny: bibliogr. 30 poz., tab., wykr.

Twórcy

autor

Neary T.

autor

Woods D.

• Boole Centre for Research in Informatics, University College Cork, Ireland.,

Bibliografia

• [1] C. Baiocchi. Three small universal Turing machines. In M.Margenstern and Y. Rogozhin, editors, Machines, Computations, and Universality (MCU), volume 2055 of LNCS, pages 1-10, Chisinău, Moldova,May 2001. Springer.
• [2] J. Cocke and M. Minsky. Universality of tag systems with P = 2. Journal of the ACM, 11(1):15-20, Jan. 1964.
• [3] M. Cook. Universality in elementary cellular automata. Complex Systems, 15(1):1-40, 2004.
• [4] G. T. Hermann. The uniform halting problem for generalized one state Turing machines. In Proceedings, Ninth Annual Symposium on Switching and Automata Theory, pages 368-372, Schenectady, New York, Oct. 1968. IEEE Computer Society Press.
• [5] M. Kudlek. Small deterministic Turing machines. Theoretical Computer Science, 168(2):241-255, Nov. 1996.
• [6] M. Kudlek and Y. Rogozhin. Small universal circular Post machines. Computer Science Journal of Moldova, 9(1):34-52, 2001.
• [7] M. Kudlek and Y. Rogozhin. A universal Turingmachinewith 3 states and 9 symbols. In W. Kuich, G. Rozenberg, and A. Salomaa, editors, Developments in Language Theory, volume 2295 of LNCS, pages 311-318, Vienna, May 2002. Springer.
• [8] M. Margenstern. Frontier between decidablity and undecidablity: a survey. Theoretical Computer Science, 231(2):217-251, Jan. 2000.
• [9] M. Margenstern. On quasi-unilateral universal Turing machines. Theoretical Computer Science, 257(1-2):153-166, Apr. 2001.
• [10] 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.
• [11] M.Minsky. Size and structure of universal Turingmachines using tag systems. In Recursive Function Theory, Symposium in Pure Mathematics, volume 5, pages 229-238, Provelence, 1962. AMS.
• [12] M. Minsky. Computation, finite and infinite machines. Prentice-Hall, New Jersey, 1967.
• [13] T. Neary. Small universal Turing machines. PhD thesis, Department of Computer Science, National University of Ireland, Maynooth, 2008.
• [14] T. Neary and D. Woods. A small fast universal Turing machine. Technical Report NUIM-CS-TR-2005-12, Department of Computer Science, National University of Ireland, Maynooth, Dec. 2005.
• [15] T. Neary and D.Woods. Small fast universal Turingmachines. Theoretical Computer Science, 362(1-3):171-195, Oct. 2006.
• [16] 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.
• [17] T. Neary and D. Woods. Small weakly universal Turing machines. Technical Report arXiv:0707.4489v1 [cs.CC], arXiv online report, July 2007.
• [18] 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).
• [19] 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 Turing machines. In Russian).
• [20] L. Priese. Towards a precise characterization of the complexity of universal and non-universal Turing machines. SIAM Journal of Computing, 8(4):508-523, Nov. 1979.
• [21] R. Robinson.Minsky's small universal Turingmachine. International Journal of Mathematics, 2(5):551-562, 1991.
• [22] Y. Rogozhin. Sem' universal'nykh mashin T'juringa. In Fifth all union conference on Mathematical Logic, Akad. Naul SSSR. Otdel. Inst. Mat., Novosibirsk, page 27, 1979. (Seven universal Turing machines. In Russian).
• [23] Y. Rogozhin. Small universal Turing machines. Theoretical Computer Science, 168(2):215-240,Nov. 1996.
• [24] C. E. Shannon. A universal Turing machine with two internal states. Automata Studies, Annals of Mathematics Studies, 34:157-165, 1956.
• [25] S. Watanabe. 5-symbol 8-state and 5-symbol 6-state universal Turing machines. Journal of the ACM, 8(4):476-483, Oct. 1961.
• [26] S.Watanabe. 4-symbol 5-state universal Turingmachine. Information Processing Society of JapanMagazine, 13(9):588-592, Sept. 1972.
• [27] S. Wolfram. A new kind of science. Wolfram Media, 2002.
• [28] D. Woods and T. Neary. The complexity of small universal Turing machines. Theoretical computer Science, 410(4-5):443-450, Feb. 2009.
• [29] D. Woods and T. Neary. Small semi-weakly universal Turing machines. Fundamenta Informaticae, 91:161-177, 2009.
• [30] 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.