Symmetric Instruction Machines and Symmetric Turing Machines

Symmetric instruction machines (SIAs) and symmetric Turing machines (STMs) are models of computation involving concepts derived from those of classical Turing machines such as tape (memory) and head (processor), but with different functional and structural characteristics. The former model (SIAs) introduced in this paper and preferred by Mark Burgin is a result of a reformulation of the latter model (STMs) published in several articles by the second author in the past. The properties of both models are analyzed and compared. The word “symmetric” in both cases represents the feature of the design which is distinct from classical Turing machines where only cells on the tape change under the action of the head. In both models, symmetric computing involves changes of the tape and parallel (“symmetric”) changes of instructions listed in the head. The key difference between SIAs and STMs is in the dynamic of the changes, which in the former model has the form of compound one-way actions and in the latter model, it has the form of uniform mutual interactions, which only in specific realizations can be separated into a pair of actions. Because of the untimely passing of Mark Burgin, the discussion of the two models and cooperation on the paper has never been finished. For this reason, the arguments of both authors are reported even though, in some cases, they are mutually inconsistent or even contradictory.