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

Last revised on January 11, 2021 at 21:44:14. See the history of this page for a list of all contributions to it.