\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \newcommand{\E} {\mathrm{E}} \)
deepdream of a sidewalk
Show Question
\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \newcommand{\groupMul}[1] { \cdot_{\small{#1}}} \newcommand{\groupAdd}[1] { +_{\small{#1}}} \newcommand{\inv}[1] {#1^{-1} } \newcommand{\bm}[1] { \boldsymbol{#1} } \require{physics} \require{ams} \require{mathtools} \)
Math and science::Theory of Computation

Turing machine

Conceptual description: finite state machine + tape

A Turing machine can be thought of as a finite state machine that controls a reading/writing head that moves along a tape.

The tape, head and state machine

The tape is a long physical 1-dimensional storage device. It has a head which is an object positioned at one of the storage cells; the head is capable of reading and writing to a cell and capable of moving 1 position forward or back inbetween read/write operations. The tape is infinite in one direction. Typically, the tape is considered to start at a zero position and extend to the right indefinitely. The head moves along the tape reading charcaters from it and writing characters to it. The head's movement (including whether to stop moving) is determined by a state machine.

Reading and writing

Reading produces a character from the tape at the head position. This character becomes the next input to the finite state machine. Writing places a character on the tape at the position of the head. The character written is chosen by the finite state machine. The character replaces the existing sequence element. Note that the finite machine is provided the character on the tape as input but it doesn't get the tape head's location as input.

In addition to writing a character to the tape, the finite state machine's also outputs an element from a binary set which encodes whether the head should move left or right once it has finished writing at the current tape location. Usually this the set is described as containing the two characters 'L' and 'R'; L decrements the tape head position, R increments it. When the head is at the beginning of the tape, L has no effect.

Formal definition

The formal definition of a Turing machine builds off of the definition of a finite automata. The definition of finite automata is recalled here.

Finite automata

A finite automaton is a 5-tuple (\( Q, \Sigma, q_0, F, \delta \)), where:

  1. \( Q \) is a finite set called the states,
  2. \( \Sigma \) is a finite set called the alphabet,
  3. \( q_0 \in Q \) is the start sate, and
  4. \( F \subseteq Q \) is the set of accept states.
  5. \( \delta : Q \times \Sigma \to Q \) is the transition function.

The definition of the Turing machine modifies the above definition of a finite automaton in three ways:

Specify a blank symbol
A symbol is introduces that is only present on the tape (it is not a symbol that can be present in the input). A Turing machine uses this symbol to, among other things, detect the end of the input once the input is placed on the tape.
Change to the transition function
Secondly, it modifies the transision function by increasing the dimensionality of its codomain. The codomain becomes \( Q \times \Gamma \times \{L, R\} \), where \( \Gamma \) is the set of symbols allowed on the tape and \( \{L, R\} \) is a set with two elements.
Introduction of a reject state
A reject state is similar to an accept state. The addition of a second type of ending state allows for the machine to end while indicating a sense of failure.

With these changes, the definition of a Turing machine looks like:

Turing machine

A Turing machine is parameterized as a 7-tuple, \( (Q, \Sigma, \Gamma, \delta, q_{accept}, q_{reject}) \), where \( Q, \Sigma \) and \( \Gamma \) are all finite sets, \( \delta \) is a function and \( q_{accept} \) and \( q_{reject} \) are elements of \( \Sigma \).

  1. \( Q \) is the set of states of the machine's underlying finite state machine.
  2. \( \Sigma \) is the input alphabet. It doesn't contain the blank symbol, ␣.
  3. \( \Gamma = \Sigma \cup \{␣\} \) is the tape alphabet.
  4. \( \delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\} \) is the transition function.
  5. \( q_0 \in Q \) is the start state.
  6. \( q_{accept} \in Q \) is the accept state.
  7. \( q_{reject} \in Q \) is the reject state, where \( q_{reject} \ne q_{accept} \).

There is a number of ways to denote a Turing machine with a tuple of sets. All are functionally equivalent but differ in how much of the machines specification is included in the tuple. The above formulation closely follows the presentation of Michael Sipser. The reverse side contains a discussion of some of the issues with this and other definitions.


Inconsistency of the standard Turing machine 'definition'

The decision of what lies this Tuple seems a little arbitrary. There are many aspects of a Turing machine, such as the idea that the head of the tape can move either left or right, which don't appear in the definition above, yet are vital for it's behaviour. One could argue that the above definition isn't really a definition. If it is classed as a definition, then, assuming some prior definition, the above tuple should be a minimal set that describes all possible Turing machines parameterizations. However, this statement isn't entirely satisfactory, as the blank symbol could easily be removed from the tuple and placed in the prior definition, as all Turing machines posses it.

I'm also drawn to notice that the blank symbol could be placed in the tuple as a separate element, instead of as an element of \( \Gamma \), then define \( \Gamma \) as \( \Gamma = \Sigma \cup \{ b \} \).

I'm also curious as to why the set \( \{L, R\} \) is not properly defined: what are \( L \) and \( R \)? Are they the characters L and R, or are they variables? If they are variables, do they not belong in the definition like \( b \)? Or maybe \( b \) doesn't belong in the definition.

Yet another arbitrary choice is whether the accept and reject states are single elements of \( Q \) or whether they are subsets of \( Q \). Brilliant.org goes as far as to not define reject states, but to consider a halt and fail occuring if \( \delta \) is 'undefined' for some input. This seems like a terrible definition, as a function, by definition, is defined for all of it's domain.

Stanford's Plato philosophy wiki takes an extremely minimal approach and doesn't include the blank, accept or reject states in it's tuple (which thus becomes a 4-tuple). https://plato.stanford.edu/entries/turing-machine/

The conclusion of all of this is that it doesn't seem that there is a well agreed upon form of the definition (and whether definition is even the right word). Define it however you like in accordance with which objects you wish to manipulate easily.