Computing ability of a developmental model for filamentous organisms

Abstract

An automata-theoretical model is investigated for the development of filamentous organisms (due to Lindenmayer) from the point of view of its computing ability. It is found that, provided information is allowed to pass in the filaments in both directions, this model is general enough to realize any effective procedure. In particular it is proved that it is capable of simulating any given Turing machine. This results in the unsolvability of certain problems relating to the mortality and other properties of filaments and we discuss some of these. Finally, it is shown that allowing information to pass only in one direction within the filaments does not restrict the computing ability of the model, but further restrictions on the information flow results in a reduced computing power and in the solvability of mortality problems. © 1997 Elsevier Science Ltd. All rights reserved.