@article {436211, title = {Tag systems and Collatz-like functions}, journal = {Theoretical Computer Science}, volume = {390}, number = {1}, year = {2008}, pages = {92{\textendash}101}, 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 {\textmu}. 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 {\textmu} and v – for tag systems might be significantly decreased.

}, issn = {0304-3975}, url = {http://dx.doi.org/1854/12954}, author = {De Mol, Liesbeth} } @phdthesis {PhD_Liesbeth, title = {Tracing Unsolvability. A Mathematical, Historical and Philosophical Analysis with a Special Focus on Tag Systems}, year = {2007}, month = {May 23}, publisher = {Ghent University}, type = {phd}, author = {De Mol, Liesbeth} } @article {detheory, title = {Theory and Experiment in the work of {A}lonzo {C}hurch and {E}mil {P}ost}, journal = {unpublished}, year = {2006}, abstract = {

While most mathematicians would probably agree that ‘experimentation’ together with an ‘empirical’ attitude – both understood in their most general sense – can be important methods of mathematical discovery, this is often obscured in the final presentation of the results for the sake of mathematical elegance. In this paper it will be shown how this “method” has played a significant role in the work of two major contributors to the rather abstract discipline called mathematical logic, namely Alonzo Church and Emil Post.

}, author = {De Mol, Liesbeth} }