# The Turing Machine(s)

What is a Turing Machine?

A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules. Despite the model’s simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm’s logic can be constructed.

https://en.wikipedia.org/wiki/Turing_machine

We then proceeded to create different kinds of turing machines for different kinds of computing machines.

Deterministic Turing Machine (DTM)

A Deterministic Turing Machine is a mathematical model which consists of an infinite length tape divided into cells on which input is given. It consists of a head which reads the input tape. A state register stores the state of the Turing machine. After reading an input symbol, it is replaced with another symbol, its internal state is changed, and it moves from one cell to the right or left. If the TM reaches the final state, the input string is accepted, otherwise rejected.

A DTM can be formally described as a 7-tuple (Q, X, ∑, δ, q0, B, F) where −

• Q is a finite set of states
• X is the tape alphabet
•  is the input alphabet
• δ is a transition function; δ : Q × X → Q × X × {Left_shift, Right_shift}.
• q0 is the initial state
• B is the blank symbol
• F is the set of final states

https://www.tutorialspoint.com/automata_theory/turing_machine_introduction.htm

Non-Deterministic Turing Machine (NTM)

In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM’s next state is not completely determined by its action and the current symbol it sees (unlike a deterministic Turing machine).

NTMs are sometimes used in thought experiments to examine the abilities and limitations of computers. One of the most important open problems in theoretical computer science is the P vs. NP problem, which (among other equivalent formulations) concerns the question of how difficult it is to simulate nondeterministic computation with a deterministic computer.

https://en.wikipedia.org/wiki/Nondeterministic_Turing_machine

Please see the following videos to learn more about NTM’s.

Probabilistic Turing Machine

In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution. As a consequence, a probabilistic Turing machine can—unlike a deterministic Turing Machine—have stochastic results; that is, on a given input and instruction state machine, it may have different run times, or it may not halt at all; furthermore, it may accept an input in one execution and reject the same input in another execution.

https://cs.stackexchange.com/questions/110497/non-deterministic-turing-machine-vs-probabilistic-turing-machine-vs-deterministi

Quantum Turing Machine (QTM)

A quantum Turing machine or universal quantum computer is an abstract machine used to model the effects of a quantum computer. It provides a simple model that captures all of the power of quantum computation—that is, any quantum algorithm can be expressed formally as a particular quantum Turing machine. However, the computationally equivalent quantum circuit is a more common model.

Quantum Turing machines can be related to classical and probabilistic Turing machines in a framework based on transition matrices. That is, a matrix can be specified whose product with the matrix representing a classical or probabilistic machine provides the quantum probability matrix representing the quantum machine. This was shown by Lance Fortnow.

https://en.wikipedia.org/wiki/Quantum_Turing_machine

Universal Turing Machine (UTM)

In computer science, a universal Turing machine (UTM) is a Turing machine that simulates an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simulated as well as the input to that machine from its own tape. Alan Turing introduced the idea of such a machine in 1936–1937. This principle is considered to be the origin of the idea of a stored-program computer used by John von Neumann in 1946 for the “Electronic Computing Instrument” that now bears von Neumann’s name: the von Neumann architecture.

In terms of computational complexity, a multi-tape Universal Turing machine need only be slower by logarithmic factor compared to the machines it simulates.

In general a K-Tape Turing Machine can be simulated by a

https://en.wikipedia.org/wiki/Universal_Turing_machine

Simulating Multitape Turing Machines using Single Tape Turing Machines

A multi-tape Turing machine is a variant of the Turing machine that utilizes several tapes. Each tape has its own head for reading and writing. Initially, the input appears on tape 1, and the others start out blank.

This model intuitively seems much more powerful than the single-tape model, but any multi-tape machine—no matter how many tapes—can be simulated by a single-tape machine using only quadratically more computation time. Thus, multi-tape machines cannot calculate any more functions than single-tape machines, and none of the robust complexity classes (such as polynomial time) are affected by a change between single-tape and multi-tape machines.

https://en.wikipedia.org/wiki/Multitape_Turing_machine

NTM’s don’t exist

A Non-Deterministic TM exists to the same extent as a Deterministic TM. Neither really exists, because all real computers have bounded storage, but we can simulate them. The big difference is that the time to simulate an NTM tends to increase exponentially, rather than linearly, in the number of steps simulated. A simulator has to track all the configurations the machine might be in at the end of a given step. A simulator for a DTM only has to track one configuration at a time.

We think of our problem solving algorithms as a tree of back tracking computations.

DTM simulation of NTM

It might seem that NTMs are more powerful than DTMs, since they can allow trees of possible computations arising from the same initial configuration, accepting a string if any one branch in the tree accepts it. However, it is possible to simulate NTMs with DTMs, and in fact this can be done in more than one way.

Question: Then why don’t we have a NTM simulation or an implementation?

NTM versus QTM

Because quantum computers use quantum bits, which can be in superpositions of states, rather than conventional bits, there is sometimes a misconception that quantum computers are NTMs. However, it is believed by experts (but has not been proven) that the power of quantum computers is, in fact, incomparable to that of NTMs; that is, problems likely exist that an NTM could efficiently solve that a quantum computer cannot and vice versa. In particular, it is likely that NP-complete problems are solvable by NTMs but not by quantum computers in polynomial time.

Intuitively speaking, while a quantum computer can indeed be in a superposition state corresponding to all possible computational branches having been executed at the same time (similar to an NTM), the final measurement will collapse the quantum computer into a randomly selected branch. This branch then does not, in general, represent the sought-for solution, unlike the NTM, which is allowed to pick the right solution among the exponentially many branches.

PTM versus NTM

So a PTM and NTM are both non-deterministic. While a PTM is a realisable model of computing in reality, an NTM is not. Is it because this “guessing” in the NTM is kind of esoteric? It’s still quite weird that the NTM just guesses the correct answer and makes the right choices at each step to arrive at the final answer in the end.

Implementing nondeterministic algorithms with deterministic ones
One way to simulate a nondeterministic algorithm N using a deterministic algorithm D is to treat sets of states of N as states of D. This means that D simultaneously traces all the possible execution paths of N (see powerset construction for this technique in use for finite automata).

Another is randomization, which consists of letting all choices be determined by a random number generator. The result is called a probabilistic deterministic algorithm.

https://en.wikipedia.org/wiki/Nondeterministic_algorithm

Conclusion

NTM’s don’t exist. Atleast not outside Automatski. These are the things we know about NTM’s

• DTM’s can simulate NTM’s but will incur an Exponential Slowdown
• NTM’s can solve NP Problems in Polynomial Time
• NTM’s ‘magically’ guess the correct choice/answer at each step. [Which is why we don’t have NTM’s outside Theory because we cannot ‘implement’ this magic]
• Non-deterministic algorithm is an algorithm that can exhibit different behaviors on different runs, as opposed to a deterministic algorithm
• DTM’s and NTM’s solve problems using a Backtracking Tree based approach. We need to get rid of it to solve Exponential Time & Space Problems

The concept of Non Deterministic Turing Machine is purely theoretical – there is no non-deterministic turing machine available. (Atleast not outside Automatski)

The Pinnacles of Human Achievement 1992-1994 CE

The Non-Deterministic Turing Machine was mankinds pinnacle breakthrough in 1992-1994 @ Automatski. As expected it can solve Exponential Time & Space problems in Polynomial Time & Space.