A Turing machine is a model of computation?. It can be thought of as a machine with a set of possible internal states that uses an infinite (in both directions) piece of tape with countably-many positions available for symbols (drawn from a specified set of symbols). There is a pointer that selects the current position on the tape. Every timestep, it can, in this order:
Remove or change the symbol that it is currently pointing to;
Point to the square of tape to the left or to the right of the square that it is currently pointing to;
Change its state.
It then repeats this sequence until its state is a halting state, if ever, where a halting state is one special state specified in advance.
On Turing machines in the context of quantum computing
David Deutsch, Quantum theory, the Churchâ€“Turing principle and the universal quantum computer, Proceedings of the Royal Society of London A 400 1818 (1985) 97-117 [doi:10.1098/rspa.1985.0070, pdf]
Wikipedia, Quantum Turing machine
Last revised on August 23, 2023 at 18:52:51. See the history of this page for a list of all contributions to it.