Alternating multicounter machines with constant number of reversals
The alternating multicounter machines with constant number of reversals are investigated in relation to Turing machines. It is shown that two-way and one-way versions of these machines working in polynomial time define precisely the class P of languages recognized by Turing machines in deterministic polynomial time. Further, it is proved that one-way alternating 4-counter machines with one reversal allowed for each counter are as powerful as Turing machines.
scientific article; zbMATH DE number 3928352