nLab Turing machine

Contents

Contents

Idea

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.

See also

References

Classical computing

Quantum computing

On Turing machines in the context of quantum computing

Last revised on August 23, 2023 at 18:52:51. See the history of this page for a list of all contributions to it.