Random-access Turing machine
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.
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.
gollark: Like literally all academic papers, this feels written by palaiologos.
gollark: ↑ LyriCLy
gollark: A regular tree structure lets us generate the tessellation C combinatorially.The tessellation will be generated lazily, let G be the set of tiles generated sofar. For every g ∈ G, we keep the following information: its state q(c), and forevery i = 0 . . . Nt − 1, its connection e(g, i), which is either a pointer to anothertile g′ ∈ G and an index i′ (meaning that edge i of g connects to edge i′ of g′)or NULL (meaning that we do not know this connection yet).
gollark: It would be difficult for a server-side thing.
gollark: You can easily embed a "zipped folder" into a document of some kind.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.