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.
Last revised on January 11, 2021 at 21:44:14. See the history of this page for a list of all contributions to it.