Comparison of the power between reversal-bounded ATMs and reversal-bounded NTMs

AbstractWe study the power of reversal-bounded ATMs (alternating Turing machines). The results obtained are as follows: (1) Every recursively enumerable set can be accepted by a 1-tape-1-counter ATM which runs in constant reversals (which are the number of times a head changes direction) but not by any 1-tape-1-counter NTM (nondeterministic TM) which runs in constant reversals, where a 1-tape-1-counter ATM (NTM, respectively) is a 1-tape ATM (NTM, respectively) with one counter tape. (2) For functions B(n) and R(n) satisfying B(n) ≦ 2O(R(n)) and B(n) R(n) ≧ n, a class of languages accepted by 1-tape ATMs which run in O(R(n)) reversal and O(B(n)) leaf simultaneously is equivalent to a class of languages accepted by NTMs which run in O(B(n) R(n)) space