Turing Machines and Automatic Functions as Models of Computation

Abstract

In the present report it is shown that a function is automatic if and only if a one-tape Turing machine can compute it in linear time where input and output have to start at the left end of the tape. It is also shown that the same equivalence holds when non-deterministic one-tape Turing machines are considered. This result is extended to the study of the complexity class AF[log n] which is roughly the class of functions which can be computed by a machine with automatic functions as primitive operations in logarithmic time. It is shown that AF[log n] is a proper subclass of DTIME[n log n] but still significantly larger than the class AF[1] of automatic functions.