Solvability of the Halting and Reachability Problem for Binary 2-tag Systems

• Autorzy: De Mol L.
• Języki publikacji: EN

Abstrakty

EN

In this paper a detailed proofwill be given of the solvability of the halting and reachability problem for binary 2-tag systems.

Słowa kluczowe

EN

v--Tag systems; halting problem; reachability problem; non-universality

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 99, nr 4
• Strony: 435--471
• Opis fizyczny: Bibliogr. 22 poz., tab.

Twórcy

autor

De Mol L.

• Centre for Logic and Philosophy of Science Gent University Blandijnberg 2, 9000 Gent, Belgium,

Bibliografia

• [1] Church, A.: An unsolvable problem of elementary number theory, American Journal of Mathematics, (58), 1936, 345-363, Also published in [5], 88-107.
• [2] Cocke, J., Minsky, M.: Universality of Tag systems with P = 2, 1963, Artificial Intelligence Project - RLE and MIT Computation Center, memo 52.
• [3] Cocke, J., Minsky, M.: Universality of Tag systems with P = 2, Journal of the ACM, 11(1), 1964, 15-20.
• [4] Cook, M.: Universality in Elementary Cellular Automata, Complex Systems, 15(1), 2004, 1-40.
• [5] Davis, M.: The Undecidable. Basic papers on undecidable propositions, unsolvable problems and computable functions, Raven Press, New York, 1965, Corrected republication (2004), Dover publications, New York.
• [6] Davis, M.: Why Gödel didn't have Church's thesis, Information and Control, 54, 1982, 3-24.
• [7] Davis, M.: Emil L. Post. His life and work, 1994, In: [17], xi-xviii.
• [8] Margenstern, M.: Frontier between Decidability and Undecidability: A survey, Theoretical Computer Science, 231(2), 2000, 217-251.
• [9] Maslov, S. J.: On E. L. Post's 'Tag' Problem. (Russian), Trudy Matematicheskogo Instituta imeni V.A. Steklova, (72), 1964b, 5-56, English translation in: American Mathematical Society Translations Series 2, 97, 1-14, 1971.
• [10] Minsky, M.: Recursive unsolvability of Post's problem of tag and other topics in the theory of Turing machines, Annals of Mathematics, 74, 1961, 437-455.
• [11] Minsky, M.: Size and Structure of Universal Turing Machines using Tag systems: a 4-symbol 7-state machine, Proceedings Symposia Pure Mathematics, American Mathematical Society, 5, 1962, 229-238.
• [12] De Mol, L.: Closing the circle: An analysis of Emil Post's early work., The Bulletin of Symbolic Logic, 12(2), 2006, 267-289.
• [13] DeMol, L.: Study of limits of solvability in tag systems, Machines, Computations, and Universality. Fifth International Conference, MCU 2007 Orléans (J. Durand-Lose,M.Margenstern, Eds.), 4664, Springer, Berlin, 2007.
• [14] De Mol, L.: Tag systems and Collatz-like functions, Theoretical Computer Science, 390(1), 2008, 92-101.
• [15] Post, E. L.: Formal Reductions of the General Combinatorial Decision Problem, American Journal of Mathematics, 65(2), 1943, 197-215.
• [16] Post, E. L.: Absolutely unsolvable problems and relatively undecidable propositions - account of an anticipation, 1965, In: [5], 340-433. Also published in [17].
• [17] Post, E. L.: Solvability, Provability, Definability: The collected works of Emil L. Post, Birkhauser, Boston, 1994, Edited by Martin Davis.
• [18] Stillwell, J.: Emil Post and His Anticipation of Gödel and Turing, MathematicsMagazine, 77(1), 2004, 3-14.
• [19] Turing, A. M.: On computable numbers with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, (42), 1936-37, 230-265, A correction to the paper was published in the same journal, vol. 43, 1937, 544-546. Both were published in [5], 116-151.
• [20] Wang, H.: Tag systems and lag systems, Mathematische Annalen, 152, 1963a, 65-74.
• [21] Woods, D., Neary, T.: On the time complexity of 2-tag systems and small universal Turing machines, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006.
• [22] Woods, D., Neary, T.: Small semi-weakly Universal TuringMachines, Machines, Computations, and Universality.Fifth International Conference, MCU 2007 Orl'eans (J. Durand-Lose, M. Margenstern, Eds.), 4664, Springer, 2007.