The halting problem for linear turing assemblers

摘要

Turing assemblers are Turing machines which operate on n-dimensional tapes under restrictions which characterize a procedure of assembly rather than computation, and which are intended as an abstraction of certain algorithmic processes of molecular biology. It has been previously shown that Turing assemblers with n-dimensional tapes can simulate arbitrary Turing machines for all n>1. Here it is shown that for n=1 even nondeterministic Turing assemblers have a sharply restricted computational capability, being able to successfully assemble only regular sets. The halting problem for linear Turing assemblers is therefore algorithmically solvable, and a characterization of the set of achievable final assemblies will be given as a subclass of the context-free languages.