A universal machine without change of state (Q1100903)

A new model of computation, inspired by Turing machines and equivalent in computational power to them, is considered. The main original characteristic of this model consists in the fact that the control processor always scans a pair of symbols placed in consecutive cells on the working tape but only moves one cell to the right or left. This feature makes state transition superfluous since shifting from one phase to another in an algorithm can be marked by special symbols on the working tape. The main goal of the paper is the detailed presentation of a universal machine for the given model. It is a complex algorithm which has the advantage of allowing the presentation of many programming techniques in the model (but also the deficiency of requiring a tenacious reader).