Random-access Turing machine

This article needs additional citations for verification. Please help by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources:  –  ·  ·  · scholar · JSTOR (August 2010) (Learn how and when to remove this template message)

In computational complexity, a field of computer science, random-access Turing machines are an extension of Turing machines used to speak about small complexity classes, especially for classes using logarithmic time, like DLOGTIME and the logarithmic hierarchy.

Definition[]

On a random-access Turing machine, there is a special pointer tape of logarithmic space accepting a binary vocabulary. The Turing machine has a special state such that when the binary number on the pointer tape is 'p', the Turing machine will write on the working tape the pth symbol of the input.

The pointer tape facility lets the Turing machine read any letter of the input without taking time to move over the entire input. This is mandatory for complexity classes using less than linear time.

References[]

• Neil Immerman Descriptive Complexity (1999 Springer), chapter 5