Deterministic Turing Machines

As a model of computation, Turing machines can be considered as an idealized abstract representation of a computer. Although different models of computation exist and are often utilized instead in practice, the purpose of a Turing machine is to offer a unifying means of thinking about computation abstractly. It is a matter of principle that whatever can be done by the means of any computer can just as well be accomplished by a Turing machine. In this regard, the conventional computers one may be more familiar with in modern society are not technically Turing machines, but are equivalent in a certain abstract sense.

Turing machines are designed to explicitly calculate Boolean functions of the form \(f: \{0,1\}^n\rightarrow\{0,1\}^m\). The purpose of a Turing machine (hereby abbreviated as TM) is not only to take some input bitstring \(\omega\in\{0,1\}^n\) and output the corresponding bitstring \(f(\omega)\in\{0,1\}^m\), but to do so in a step-by-step algorithmic fashion by accordingly transforming the input into the corresponding output using a predefined set of rules for that particular TM. Instead of omnisciently providing the value \(f(\omega)\) for some function \(f\) given only the input \(\omega\), a TM can be thought of as an automated device which goes through all the necessary analysis and "motions" to determine what the output \(f(\omega)\) really is. This is done by specifying a program for the TM, which contains instructions for the machine's behavior for yielding information about the output on any suitable input. Typically, a TM is a special-purpose computer whose program contains instructions for computing one particular Boolean function \(f\) which would correspond to a single algorithmic task.  However, a single TM is not limited to doing just a single algorithmic task and can be generalized to handle more than one computational task.

It is worthwhile to anthropomorphize a Turing Machine to better understand its operation. One could imagine the TM as having a pen and paper on which to work. This paper would initially have only the input written on it with blank space for extra working room. By following a strict set of rules defined by the specific program for this TM, the TM would then proceed to read the input and accordingly write, erase, or rewrite additional information on the paper until it ends its task with information left on the paper corresponding to the output associated with the initial input. The rigor provided by the TM ensures that during this whole working process each step is carried out in a meticulous manner so that each step of the computation is finitely realizable. This allows the TM to faithfully capture the essence expected of a reasonable algorithmic task.

A more formal and precise mathematical definition of a Turing machine is now given followed by a description of its parts. A Turing machine, \(M\), is a 7-tuple of the form:
\[M = (Q, \Sigma, \Gamma, \delta, q_ 0, q_ {accept}, q_ {reject}), \]
where

1.  \(Q\) is a set of internal states
2.  \(\Sigma$\)is the input alphabet which does not contain the blank symbol \(\sqcup\)
3.  \(\Gamma\) is the tape alphabet, where \(\sqcup\in\Gamma\) and \(\Sigma\subseteq\Gamma\)
4.  \(\delta : Q\times\Gamma\longrightarrow 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

Here, the input alphabet is the set of symbols that the input will be written in. In most cases this will be provided in terms of bits so that \(\Sigma= \{0,1\}\). Since the input could be a bitstring \(\omega\in\{0,1\}^n\) of any finite length \(n\), define \(\Sigma^* := \bigcup_{k=1}^\infty\{0,1\}^k\) to be the set of all bitstring of any finite length. The blank symbol \(\sqcup\) is literally used to specify an empty space on the TM's working paper. It is not included in the input alphabet \(\Sigma\) and is instead contained in the larger tape alphabet \(\Gamma\) to avoid ambiguity with what is interpreted as input by the TM. The tape alphabet \(\Gamma\) can contain more symbols than the input alphabet \(\Sigma\) for the purpose of allowing the TM more freedom to read and write different symbols onto the paper while working. Without loss of generality, the TM's working paper is simply interpreted as a one-dimensional array of symbols (hence the term "tape"), which can be considered to be of infinite length in both directions in order to provide the TM with infinite workspace and memory. This latter property of an unlimited memory is an essential defining characteristic of a Turing Machine. Furthermore, for the purpose of indexing positions along this tape suppose this tape is partitioned into distinct cells along the tape which can each contain only one symbol.

The set of internal states \(Q\) describe the state of the TM at any given moment of the computation and serve to inform the machine which part of the program or computation the TM is on. The TM will always start on the start state \(q_0\) and change its state accordingly throughout the computation into some other states \(q \in Q\) until the computation ends on either the accept state \(q_{accept}\) or reject state \(q_{reject}\). These two terminating states correspond to final states when the TM either "accepts" or "rejects" the output bitstring, respectively.

The heart of the TM and the essence of its program are contained within the transition function \(\delta: Q\times\Gamma \longrightarrow Q\times\Gamma\times\{L, R\}\), which describes how the TM behaves when its configuration is in a particular state \(q \in Q\) and is reading a certain  symbol in \(\Gamma\) written on the tape. For each possible state and symbol \((q, s) \in Q\times\Gamma\) that the TM may encounter, the transition function \(\delta\) specifies a state, symbol, and direction \((q', s' ,d') \in Q\times\Gamma\times\{L, R\}\) which tells the TM which state to enter next, which symbol to write over in the existing position of the tape, and what direction along the tape the TM should move next.

To better understand the dynamics of a TM, imagine the TM equipped with a read-write head that has the ability to move around to different positions along the tape and read or write symbols onto the tape. This read-write head is only able to read one symbol at a time written in a single cell, erase and write another single symbol in that cell, and move to an adjacent cell on the tape in either the left \(L\) or right \(R\) directions. In this way, if the TM is in some state \(q\) reading some symbols \(s\) in a certain cell on the tape the transition function of the TM will give something of the form \(\delta(q, s) = (q', s', d')\), which tells the TM to change the symbol in that cell from \(s\) to \(s'\), enter into another state \(q'\), and move one cell to the left or right according to what is specified by the direction \(d'\). Next, the TM will act similarly according to what is now specified by the transition function: \(\delta(q', s') = (q'', s'', d'')\) for another state \(q''\), symbol \(s''\), and direction \(d''\). Note that the change in state or symbol specified by the transition function does not actually have to be different from the current state or symbol, and the TM may remain in the same state or leave the preexisting symbol on the tape as it is.

Initially, what is present on the TM's tape at the start of a computation will be just the input bitstring  \(\omega=\omega_1\omega_2...\omega_n\)  with blank symbols to either side of the input. The TM will start in the start state \(q_0\) reading the first bit \(\omega_1\) and compute according to the transition function \(\delta\) until the TM reaches either of the terminating states \(q_{accept}\) or \(q_{reject}\). At this point, what is left on the tape will be a bitstring corresponding to the output.

This computational model of a Turing machine just described here is more specifically called a   deterministic Turing Machine. This name is justified because the entire computation is completely determined by the initial input and program through the actions defined by the TM's transition function since the transition function assigns a single action \(\delta(q,s)\) for each state and symbol. Thus, for a given input on a deterministic TM there is only one possible output. This model is contrasted by some other models of computation and possible variants of Turing machines. Only some of these Turing machine variants will be briefly discussed in the following section. However, it is important to mention that it still suffices to regard the deterministic Turing machine model as the idealized representation of a computer despite the advantages that may be offered by these other variants, because this standard deterministic Turing Machine is capable of simulating any of its variants. Reasons for this will be justified later, and will therefore give reason for believing in this claimed robustness of the deterministic Turing machine model.