On reversal bounded alternating Turing machines

AbstractIt is known that, for one-tape nondeterministic Turing machines, S(n)-space and S(n)-reversal bounded machines (S(n) ⩾ n) recognize the same class of languages. We present a simulation of S(n)-space bounded alternating Turing machines (ATM) by one-tape lg∗ S(n)-reversal bounded ATMs. We also show that ATMs making a constant number of reversals recognize only regular languages. This shows that there is a striking difference in computational power between machines making a constant number of reversals and those making an ‘almost’ constant (i.e., lg∗n) number of reversals