Probabalistic Turing Machines

Another model of computation worth mentioning due to its relevance to the quantum computation model involves the notion of  probability and randomization. Suppose at some step of an algorithm there exists more than one possible future action. In the case of the nondeterministic Turing machine, the computation was allowed to take all possible actions.  Now, assuming that only one of these possible actions could be carried out by the algorithm, which one does the algorithm execute? Perhaps the algorithm will just choose one at random and proceed with the computation. More specifically, there could be a predefined probability distribution that determines which action to take. For a probabilistic Turing machine such a randomization procedure is used to determine which possible action the computation will carry out.

One way to implement  randomization in a probabilistic TM is by supplying an additional random bitstring of sufficient length along with the usual input bits. The bits forming this random bitstring serve the purpose of determining at random (or with a certain probability) exactly how the TM will proceed given multiple choices. This random bitstring can be thought of simply as a supply of "coin flips" where the existence of a \(1\) or \(0\) in a particular location of the random bitstring would inform the TM to take one of the actions over an alternate.

A consequence of the probabilistic TM is that the overall action and output could be different for a certain input due merely to pure chance. It could very well be the case for a single input string, depending on the series of probabilistically determined actions,  that this input would result in the TM reaching an accepting state in one instance and a rejecting state in another. This is a complication that will become relevant in later discussions in complexity theory when the success rate of a computation will be given probabilistically. However, it is  important to note that although randomized Turing machines may help in performing certain computations more efficiently, there is nothing that can be computed on these randomized computers that could not be computed in principle using the standard Turing machine models.

Nondeterministic Turing Machines

One kind of variant of the deterministic Turing machine is the nondeterministic Turing machine. A deterministic TM has only one unique action at any step of the computation, and therefore the entire computation is completely determined by the input and program. The nondeterministic TM differs from its deterministic counterpart in that there may exist more than one way the machine can behave at any step of the computation. One can think of a nondeterministic TM as having the ability of performing different actions in parallel or simultaneously. Although the deterministic TM can compute anything a nondeterministic TM can compute, the latter may have the ability to perform certain computations more efficiently than the former.

For a deterministic Turing machine the transition function was of the form
 \[\delta : Q\times\Gamma \longrightarrow Q\times\Gamma\times\{L, R\},\]
 which yielded one triple \((q',s',d')\in Q\times\Gamma\times \{L, R\}\) for each defined pair \((q,s) \in Q\times \Gamma\). A nondeterminsitic Turing machine (abbreviated NTM) allows for the possibility of multiple actions for a single pair \((q,s)\) that the NTM may encounter. More formally, the transition function for a NTM takes the form
 \[\delta : Q\times\Gamma \longrightarrow \mathcal{P}(Q\times\Gamma\times\{L, R\}).\]
 Here, the notation \(\mathcal{P}(S)\) of some set \(S\) is defined to be the power set of \(S\), which is the set of all subsets of \(S\). Thus, \(\mathcal{P}(Q\times\Gamma\times\{L, R\})\) represents the set of all possible sets of triples \((q',s',d') \in Q\times\Gamma\times\{L, R\}\). The transition function of a NTM will then assign a state and symbol \((q,s)\) to a collection of triples \(\delta(q,s) \in \mathcal{P}(Q\times\Gamma\times\{L, R\})\), which represent all possible actions the NTM will carry out when encountering \((q,s)\). Of course, the image for a particular configuration \(\delta(q,s)\) may just be a set which contains one element, say \((q',s',d')\), and so that step alone will be uniquely determined by \((q,s)\). Consider the possibility that every possible action of \(\delta\) for any configuration of a \emph{nondeterministic} TM is simply a single element set of the form \({(q',s',d')}\in\mathcal{P}(Q\times\Gamma\times\{L, R\})\). In this case, the NTM corresponds to an equivalent deterministic TM. Therefore, deterministic TMs are just special cases of the more general nondeterministic TMs.

As a consequence of having multiple transitions, each of the different possible sequence of configurations that a NTM can take can each be thought of as a computational branch. All of these branches considered together define the NTM's computational tree for a given input. The NTM is considered to have reached an accepting state if at least one branch of the tree reaches a configuration that ends in the accept state regardless of any other branches  having reached the reject state. The essence of the NTM lies in its ability to execute these multiple branches simultaneously as if there were multiple deterministic TMs performing these different actions in parallel. 

As mentioned, a deterministic TMs can simulate the action of a NTM by computing the action defined by all the different branches individually either consecutively or in parallel  provided there are multiple deterministic TMs each performing the computation specified by a single branch. Similarly, this simulation with deterministic TMs would accept a particular input if at least one of the TMs reached an accepting state, and reject otherwise.

There is one important issue that ought to be treated more carefully in this simulation. This is the possibility of  their existing computational branches that may not halt on certain inputs--that is,  they  may not eventually end in an accepting or rejecting state. Non-halting computations of this sort may be troublesome when attempting to simulate the action of a NTM using a  single deterministic TM that computes each branch individually. For instance,  the TM may get stuck indefinitely on a branch that may never reach an accepting state and then be unable to move on to another branch that may end in an accepting state. A priori, there is no way of necessarily knowing which branches to simulate first or which ones to avoid.

 In order to successfully simulate a computation on a deterministic TM, and avoid complications like the ones described above, the TM can proceed using the method of breadth-first search. Previously, the method described above to simulate the action of a NTM was to simulate each entire branch before simulating another. This method could be referred to as depth-first search. On the contrary, in breadth-first search, all possible branches of the tree are progressively simulated together by simulating a single step in each branch first, then simulating the next step for each branch, and then consecutive steps as they exist for each branch. Proceeding in this way ensures that an accepting state will eventually be reached if one does indeed exist.

It can be shown that for any finite set \(S\) of size \(n\), the size of the power set \(\mathcal{P}(S)\) is \(2^n\). For some NTM, suppose the set \(Q\times\Gamma\times\{L, R\}\) is of size \(n\). Then the maximum number of possible actions that this NTM may take in a particular configuration is given by \(2^n\). The point here is that, though this number is finite, it is exponential in \(n\). Hence, when a deterministic TM attempts to simulate the action of a NTM it may have to simulate exponentially many steps. In general, even though the deterministic TM can accurately simulate the NTM in principle, it may take exponentially more steps to complete the task. Taking into consideration these extra steps as a resource is what could make the NTM a more efficient computational model when compared to deterministic TMs.

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.