The halting problem for linear turing assemblers
R. M. Baer, J. vanLeeuwen · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1975
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 previouslyshown that Turing assemblers with n-dimensional tapes can simulate arbitrary Turing machines for all n > I.Here it is shown that for n = I 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.