In computational complexity

Computational Complexity

Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...

, a field of computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, random-access Turing machines are an extension of Turing machine

Turing machine

A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...

s used to speak about small complexity classes, especially for classes using logarithmic time, like DLOGTIME

DLOGTIME

DLOGTIME is the complexity class of all computational problems solvable in a logarithmic amount of computation time on a deterministic Turing machine. It is the smallest nontrivial class using the resource of deterministic time...

 and the Logarithmic Hierarchy

LH (complexity)

Logarithmic Hierarchy is the complexity class of all computational problems solvable in a logarithmic amount of computation time on an alternating Turing machine with a bounded number of alternation. It is a special case of hierarchy of bounded alternating Turing machine...

.

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 write on the working tape the pth symbol of the input.

This 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.