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.