# Computational Model: Turing Machine

The turing machine is a computational model that was invented in 1936 by Alan Turing to solve the problem of undecidability.

In theory, the turing machine can be used to represent any algorithm computable by a machine. Thus it would follow that a turing complete ( following paragraph ) language can perform any possible computation.

Turing completeness is determined by a computational representation’s or programming language’s ability to simulate a turing machine. Commonly, when determining turing completeness memory limitations are ignored.

The turing machine is constructed of three parts: a tape, a read/write head, and a controller.

The tape is of infinite length, and is divided in compartments. Each compartment can hold a single symbol from the alphabet being used. In modern ( 2018 ) computers, the alphabet would be a one or a zero.

The read/write head is located above a single compartment on the tape. The head contains no memory, but can move up and down the tape. The job of the head is to read and write to the compartment it is located above.

The controller contains a number of states, and provides instructions given a state and an input from what the head reads.

When the turing machine starts computing: the tape starts in some initial condition with some input; the read/write head starts at some initial position; and the controller begins in some state.

From which the machine’s read/write head will read the tape at its own position.

The controller uses its state and the information read from the read/write head to determine lookup a set of instructions to follow. These instructions contain a symbol to write to the tape, a state to change the controller to, and a left or right move for the tape.

First, the read/write head writes the symbol provided from the controller to the tape.

Second, depending on how one conceptualizes the machine, it either: has the tape move one compartment left or right, or the read/write head moves one compartment left or right. Regardless of the conceptualization, the effect is the same; the read/write head is over a different compartment.

Finally, the controller changes to a new state. If the controller’s new state is a halting state, which are predetermined, then the machine halts, and the current tape is the output.

Josiah has a modest knowledge of economics, formal logic, and TRPGs.

If you want a picture to show with your comment, go get a gravatar.