Cellular Multihead Turing Machine

摘要

The Turing machine is a mathematical model for describing procedures. It can do any calculation that can be done by modern day computers. One disadvantage of the Turing machine is its very slow speed. One way to increase the speed is to increase the number of states of the machine or the number of symbols that the machine can read and write. Another way to increase the speed without increasing the complexity to a great extent is to use a cellular approach and not use a fixed number of heads. New heads will be generated whenever needed and these new heads will generate as many more heads as needed to do the job. Whenever a head completes its assigned task it will disappear. A system that does this is investigated and a few examples are worked out, including a universal type of Multihead Turing Machine. It is shown that the multihead machine is actually doing a parallel type of processing instead of the serial type done by the single head machine. (Author)