{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,31]],"date-time":"2023-08-31T04:54:03Z","timestamp":1693457643956},"reference-count":23,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":15625,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1971,6]]},"abstract":"<jats:p>The aim of this paper is to study tag systems as defined by Post [Post 1943, pp. 203\u2013205 and Post, 1965, pp. 370\u2013373]. The existence of a tag system with unsolvable halting problem was proved by Minsky by constructing a universal tag system [Minsky 1961, see also Cocke and Minsky 1964, Wang 1963, and Minsky 1967, pp. 267\u2013273]. Hence the halting problem of a tag system can be of the complete degree <jats:bold>0\u2032<\/jats:bold>. We shall prove that the halting problem for a tag system can have an arbitrary (recursively enumerable) degree of undecidability (Corollary III).<\/jats:p><jats:p>A related problem arises when we ask if there exists a uniform procedure for determining, given a tag system, whether or not there is any word on which the tag system does not halt, an \u201cimmortal\u201d word in the system. The alternative, of course, being that the system eventually halts on every (finite) word. It is shown here that this problem, the immortality problem for tag systems, is recursively unsolvable of degree <jats:bold>0\u2033<\/jats:bold> (Corollary II).<\/jats:p>","DOI":"10.2307\/2270257","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T21:07:49Z","timestamp":1146949669000},"page":"229-239","source":"Crossref","is-referenced-by-count":5,"title":["Decision problems for tag systems"],"prefix":"10.1017","volume":"36","author":[{"given":"St\u00e5l","family":"Aanderaa","sequence":"first","affiliation":[]},{"given":"Dag","family":"Belsnes","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200083201_ref021","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200083201_ref017","doi-asserted-by":"publisher","DOI":"10.2307\/1970290"},{"key":"S0022481200083201_ref016","first-page":"57","article-title":"On E. L. Post's \u201ctag problem\u201d","volume":"72","author":"Maslov","year":"1964","journal-title":"Trudy Matemati\u010deskogo Instituta im. V. A. Steklova"},{"key":"S0022481200083201_ref014","doi-asserted-by":"publisher","DOI":"10.1145\/321341.321344"},{"key":"S0022481200083201_ref013","first-page":"219","volume":"31","author":"Hooper","year":"1966","journal-title":"The undecidability of the Turing machine immortality problem"},{"key":"S0022481200083201_ref022","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19650110210"},{"key":"S0022481200083201_ref020","unstructured":"Post E. L. , Absolutely unsolvable problems and relatively undecidable propositions\u2014account of an anticipation, M. Davis, The Undecidable (ms. unpublished, 1941)."},{"key":"S0022481200083201_ref008","first-page":"267","volume":"30","author":"Cudia","year":"1965","journal-title":"Post's correspondence problem and degrees of unsolvability; Degrees of unsolvability in automata and grammars"},{"key":"S0022481200083201_ref010","doi-asserted-by":"publisher","DOI":"10.1145\/321479.321490"},{"key":"S0022481200083201_ref006","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-10808"},{"key":"S0022481200083201_ref005","doi-asserted-by":"publisher","DOI":"10.2307\/1970478"},{"key":"S0022481200083201_ref019","doi-asserted-by":"publisher","DOI":"10.2307\/2371809"},{"key":"S0022481200083201_ref003","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19690150401"},{"key":"S0022481200083201_ref004","article-title":"Decision problems for tag systems","volume":"14","author":"Belsnes","year":"1967","journal-title":"Notices of the American Mathematical Society"},{"key":"S0022481200083201_ref002","first-page":"640","article-title":"Decision problems for monogenie Post normal systems","volume":"13","author":"Axt","year":"1966","journal-title":"Notices of the American Mathematical Society"},{"key":"S0022481200083201_ref001","article-title":"Some recursively undecidable problems in automata theory and quantification theory","volume":"13","author":"Aanderaa","year":"1966","journal-title":"Notices of the American Mathematical Society"},{"key":"S0022481200083201_ref009","first-page":"418","volume":"33","author":"Cudia","year":"1968","journal-title":"The Post correspondence problem"},{"key":"S0022481200083201_ref015","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321367"},{"key":"S0022481200083201_ref007","doi-asserted-by":"publisher","DOI":"10.1145\/321203.321206"},{"key":"S0022481200083201_ref018","volume-title":"Computation: finite and infinite machines","author":"Minsky","year":"1967"},{"key":"S0022481200083201_ref012","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19690151302"},{"key":"S0022481200083201_ref023","doi-asserted-by":"publisher","DOI":"10.1007\/BF01343730"},{"key":"S0022481200083201_ref011","first-page":"167","volume-title":"Automata Studies","author":"Davis","year":"1956"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200083201","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T20:05:58Z","timestamp":1559333158000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200083201\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1971,6]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1971,6]]}},"alternative-id":["S0022481200083201"],"URL":"https:\/\/doi.org\/10.2307\/2270257","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1971,6]]}}}