Tag systems and Collatz-like functions
Tag systems were invented by Emil Leon Post and proven recursively unsolvable by Marvin Minsky. These production systems have proved to be 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 nu and the number of symbols mu. 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 mu and nu - for tag systems might be significantly decreased. (C) 2007 Elsevier B.V. All rights reserved.
tag systems collatz-like functions universality limits of solvability and unsolvability 3n+1-problem