Theoretical Computer Science

TitleTag systems and Collatz-like functions
Publication TypeJournal Article
Year of Publication2008
AuthorsDe Mol, L
JournalTheoretical Computer Science
Volume390
Number1
Pagination92–101
ISSN0304-3975
Abstract

Tag systems were invented by Emil Leon Post and proven recursively unsolvable by Marvin Minsky. These production systems have shown very useful in constructing small universal (Turing complete) systems for several different classes of computational systems, including Turing machines, and are thus important instruments for studying limits or boundaries of solvability and unsolvability. Although there are some results on tag systems and their limits of solvability and unsolvability, there are hardly any that consider both the shift number n, as well as the number of symbols µ. This paper aims to contribute to research on limits of solvability and unsolvability for tag systems, taking into account these two parameters. The main result is the reduction of the 3n + 1-problem to a surprisingly small tag system. It indicates that the present unsolvability line – defined in terms of µ and v – for tag systems might be significantly decreased.

URLhttp://dx.doi.org/1854/12954
Citation Key436211
Download PDF (Author PDF)
PDF author (public):