Yurii Rogozhin’s Contributions to the Field of Small Universal Turing Machines

• Autorzy: Woods D. , Neary T.

Identyfikatory

DOI

10.3233/FI-2015-1210

• Języki publikacji: EN

Abstrakty

EN

In the field of small universal Turing machines, Yurii Rogozhin holds a special prize: he was first to close off an infinite number of open questions by drawing a closed curve that separates the infinite set of Turing machines that are universal from a finite set of small machines for which we don’t yet know. Rogozhin did this by finding the smallest known universal Turing machines at the time, both in terms of number of states and number of symbols. This brief note summarises this and a few of Yurii’s other contributions to the field, including his work with Manfred Kudlek on small circular Post machines.

Słowa kluczowe

EN

turing machines; set theory; number theory; computational complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 138, nr 1/2
• Strony: 251--258
• Opis fizyczny: Bibliogr. 48 poz., wykr.

Twórcy

autor

Woods D.

• California Institute of Technology Pasadena, CA 91125, USA

autor

Neary T.

• Institute for Neuroinformatics University of Zürich and ETH Zürich Zürich, Switzerland

Bibliografia

• [1] Artiom Alhazov, Manfred Kudlek, and Yurii Rogozhin. Nine universal circular Post machines. Computer Science Journal of Moldova, 10(3):247–262, 2002.
• [2] Claudio Baiocchi. 3n + 1, UTM e tag-system. Technical Report Pubblicazione 98/38, Dipartimento di Matematico, Universit`a di Roma, 1998. (In Italian).
• [3] Claudio Baiocchi. Three small universal Turing machines. In Maurice Margenstern and Yurii Rogozhin, editors, Machines, Computations, and Universality (MCU), volume 2055 of LNCS, pages 1–10, Chişinău, Moldova,May 2001. Springer.
• [4] John Cocke and Marvin Minsky. Universality of tag systems with P = 2. Journal of the Association for Computing Machinery (ACM), 11(1):15–20, January 1964.
• [5] Matthew Cook. Universality in elementary cellular automata. Complex Systems, 15(1):1–40, 2004.
• [6] Martin Davis. The undecidable: basic papers on undecidable propositions, unsolvable problems and computable functions. Raven Press, New York, 1965.
• [7] Liesbeth DeMol. On the complex behavior of simple tag systems - an experimental approach. Theoretical Computer Science, 412(1–2):97–112, 2011.
• [8] Raymond Greenlaw, H. James Hoover, andWalter L. Ruzzo. Limits to parallel computation: P-completeness theory. Oxford University Press, Oxford, 1995.
• [9] Gabor T Hermann. The uniform halting problem for generalized one state Turing machines. In Proceedings, Ninth Annual Symposium on Switching and Automata Theory (FOCS), pages 368–372, Schenectady, New York, October 1968. IEEE Computer Society Press.
• [10] Manfred Kudlek. Small deterministic Turing machines. Theoretical Computer Science, 168(2):241–255, November 1996.
• [11] Manfred Kudlek and Yurii Rogozhin. New small universal circular Post machines. In Rusins Freivalds, editor, Fundamentals of Computation Theory (FCT), volume 2138 of LNCS, pages 217–227, Riga, Latvia, August 2001. Springer.
• [12] Manfred Kudlek and Yurii Rogozhin. Small universal circular Post machines. Computer Science Journal of Moldova, 9(1):34–52, 2001.
• [13] Manfred Kudlek and Yurii Rogozhin. A universal Turing machine with 3 states and 9 symbols. In Werner Kuich, Grzegorz Rozenberg, and Arto Salomaa, editors, Developments in Language Theory (DLT) 2001, volume 2295 of LNCS, pages 311–318, Vienna, May 2002. Springer.
• [14] Jeffrey C Lagarias. The 3x + 1 problem and its generalizations. American Mathematical Monthly, pages 3–23, 1985.
• [15] Jeffrey C Lagarias. The 3x + 1 problem: An annotated bibliography (1963–1999). Technical Report arXiv:math/0309224 [math.NT], 2003.
• [16] Jeffrey C Lagarias. The 3x + 1 problem: An annotated bibliography, II (2000-2009). Technical Report arXiv:math/0608208 [math.NT], 2006.
• [17] Maurice Margenstern. Frontier between decidability and undecidability: a survey. In Maurice Margenstern, editor,Machines, Computations, and Universality (MCU) volume 1, pages 141–177, France,May 1998. IUT, Metz.
• [18] Maurice Margenstern. Frontier between decidability and undecidability: a survey. Theoretical Computer Science, 231(2):217–251, September 2000.
• [19] PascalMichel. Busy beaver competition and Collatz-like problems. ArchiveMathematical Logic, 32(5):351–367, 1993.
• [20] Pascal Michel. Small Turing machines and the generalized busy beaver competition. Theoretical Computer Science, 326:45–56, 2004.
• [21] Pascal Michel. Simulation of the Collatz 3x + 1 function by Turing machines. Technical Report arXiv:1409.7322v1 [math.LO], September 2014.
• [22] Pascal Michel and Maurice Margenstern. Generalized 3x + 1 functions and the theory of computation. In Jeffrey C. Lagarias, editor, The Ultimate Challenge: The 3x + 1 Problem, pages 105–130. American Mathematical Society, 2010.
• [23] Marvin Minsky. A 6-symbol 7-state universal Turing machines. Technical Report 54-G-027, Licoln Laboratory, MIT, Cambridge,Massachusetts, August 1960.
• [24] Marvin 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. American Mathematical Society.
• [25] Marvin Minsky. Universality of (p=2) tag systems and a 4 symbol 7 state universal Turing machine, 1962. AIM-33, A.I. memo 33, Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, Massachusetts.
• [26] Turlough Neary and Damien Woods. P-completeness of cellular automaton Rule 110. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, International Colloquium on Automata Languages and Programing 2006, (ICALP) Part I, volume 4051 of LNCS, pages 132–143, Venice, July 2006. Springer.
• [27] Turlough Neary and Damien Woods. Four small universal Turing machines. Fundamenta Informaticae, 91(1):123–144, 2009.
• [28] Turlough Neary and Damien Woods. Small weakly universal Turing machines. In Mirosław Kutyłowski, Witold Charatonik and Maciej Gebala, editors, Fundamentals of Computation Theory (FCT), 17th International Symposium, volume 5699 of LNCS, pages 262–273,Wrocław, Poland, September 2009. Springer.
• [29] Turlough Neary and Damien Woods. The complexity of small universal Turing machines: a survey. In SOFSEM 2012: Theory and Practice of Computer Science, volume 7147 of LNCS, pages 385–405. Springer, 2012.
• [30] Liudmila Pavlotskaya. Solvability of the halting problem for certain classes of Turing machines. Mathematical Notes (Springer), 13(6):537–541, June 1973. (Translated from Matematicheskie Zametki, Vol. 13, No. 6, pages 899–909, June, 1973.).
• [31] Liudmila Pavlotskaya. Dostatochnye uslovija razreshimosti problemy ostanovki dlja mashin T’juring. Problemi Kibernetiki, 27:91–118, 1978. (Sufficient conditions for the halting problem decidability of Turing machines. In Russian).
• [32] Emil Post. Absolutely unsolvable problems and relatively undecidable propositions - account of an anticipation. In [6], pages 340–406.
• [33] Emil Post. Formal reductions of the general combinatorial decision problem. American Journal of Mathmatics, 65(2):197–215, April 1943.
• [34] Emil Post. Recursive unsolvability of a problem of Thue. The Journal of Symbolic Logic, 12(1):1–11,March 1947. (Also to be found in [6] pages 293–303).
• [35] Raphael Robinson. Minsky’s small universal Turing machine. International Journal of Mathematics, 2(5):551–562, 1991.
• [36] Yurii 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).
• [37] Yurii Rogozhin. Sem’ universal’nykhmashin T’juringa. Systems and theoretical programming,Matematicheskie Issledovanija, 69:76–90, 1982. (Seven universal Turing machines. In Russian).
• [38] Yurii Rogozhin. 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).
• [39] Yurii Rogozhin. About Shannon’s problem for Turing machines. Computer Science Journal of Moldova, 1(3):108–111, November 1993.
• [40] Yurii Rogozhin. On the notion of universality and Shannon’s problem for Turing machines. In International Workshop on Universal Machines and Computations (UMC, renamed to MCU), pages 36–39, Paris, March 1995.
• [41] Yurii Rogozhin. Small universal Turing machines. Theoretical Computer Science, 168(2):215–240,November 1996.
• [42] Yurii Rogozhin. A universal Turing machine with 22 states and 2 symbols. Romanian Journal of Information Science and Technology, 1(3):259–265, 1998. (In Russian).
• [43] Claude Elwood Shannon. A universal Turing machine with two internal states. Automata Studies, Annals of Mathematics Studies, 34:157–165, 1956.
• [44] Shigeru Watanabe. On a minimal universal Turing machine. Technical report, MCB Report, Tokyo, August 1960.
• [45] ShigeruWatanabe. 5-symbol 8-state and 5-symbol 6-state universal Turing machines. Journal of the Association for Computing Machinery (ACM), 8(4):476–483, 1961.
• [46] Shigeru Watanabe. Four-symbol five-state universal Turing machine. Information Processing Society of Japan Magazine, 13(9):588–592, September 1972. (In Japanese).
• [47] Damien Woods and Turlough 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–448, Berkeley, California, October 2006. IEEE.
• [48] DamienWoods and Turlough Neary. Small semi-weakly universal Turing machines. Fundamenta Informaticae, 91(1):179–195, 2009.