Tag systems and Collatz-like functions |
| |
Authors: | Liesbeth De Mol |
| |
Affiliation: | Gent University, Centre for Logic and Philosophy of Science, Blandijnberg 2, 9000 Gent, Belgium |
| |
Abstract: | 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 v and 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. |
| |
Keywords: | Tag systems Limits of solvability and unsolvability Universality 3n+1-problem Collatz-like functions |
本文献已被 ScienceDirect 等数据库收录! |
|