Types of Turing Machines

A turing machine is a mathematical model of a computation defining an abstract machine. In this article, we learn about the different variations/types of turing machines.

Table of contents.

1. Introduction.
2. Types of turing machines.
3. Applications of turing machines.
4. Summary.
5. References.

Prerequisite.

1. Turing machines

Introduction.

A turing machine is a mathematical model of a computation that defines an abstract machine. In the prerequisite article, we learned about Turing machines, how they are defined formally and informally, and the Church-Turing thesis. In this article, we learn about the different variations of turing machines and some of their features.

Types of turing machines.

The following are the different types of turing machines:

• Multi-tape turing machine
• Multi-head turing machines
• Multi-track turing machines
• Semi-infinite turing machines
• Universal Turing Machine
• Alternating Turing machine
• Non-Deterministic Turing Machine
• Unambiguous Turing Machine
• Quantum Turing Machine
• Read-Only Turing Machine
• Probabilistic Turing Machine

Multi-tape turing machine

This is just like any other ordinary turing machine except it has multiple tapes where each tape has its head for reading and writing.

In the beginning, the input is only on the first tape while the rest of the tapes remain blank. In the next step, the machine reads consecutive symbols under its head and prints a symbol on each tape then shifts its head.

This may seem better than a single tape but regardless of the number of tapes, it can be simulated by a single tape turing machine.

To conclude, multi-tape TMs have multiple tapes and each tape is accessed by a different head that moves independently of other heads.

Multi-head turing machines

These have a single tape with n number of heads each reading symbols on the same tape. In a single step, all heads determine the scanned symbols and write then shift left, right, or stay. These actions are independent of any other head.

Multi-track turing machines

This turing machine has multiple tracks but a single tape head that reads and writes on all tracks.
These machines accept recursively enumerable languages just like a normal single-track single-tape turing machine.
Also, for every single-track turing machine, there exists an equivalent multi-track turing machine.

Semi-infinite turing machines

Such machines have left ends limited by an end marker and an infinite right end.
They also have two tracks, that is, the upper track that represents cells to the right of the initial head position and a lower track that represents cells to the left of the initial head position in reverse order.

The machine starts from a state q0 and scans from the left end marker. At each step it reads the symbol on the tape under its head then writes a new symbol on that tape and shifts the head to the left or right of one tape cell.
A transition function determines the actions to be taken.

Semi-infinite machines have two special states, the accept and reject states. The former means that the input is accepted and the latter means that input is rejected when the machine enters that state. In other cases, the machine will continue infinitely without any rejections or acceptances for certain inputs.

Universal Turing Machine

This is a type of turing machine that simulates an arbitrary turing machine on an arbitrary input. It does this by having three pieces of information for the machine it is simulating, the first is the basic description of the machine to be simulated, the second is the input to that machine's tape, and finally the internal state of the machine.

It controls the machine by changing its state based on the input.

Alternating Turing machine

This is a Non-Deterministic turing machine that accepts computations that generalize rules used in the definition of complexity classes of NP and Co-NP.
Its states are divided into two sets namely existential and universal states. The former is accepting if a transition leads to an accepting state while the latter is accepting if every transition leads to an accepting state.

These machines are commonly used in complexity theory since they yield elegant characterizations of complexity classes.

Non-Deterministic Turing Machine

In such turing machines, for every state and symbol, there exists a group of actions the machine can have. Computations of such machines form a tree of configurations that are reachable from the start configuration and therefore input is accepted if there is at least one node in the tree that is an accept configuration otherwise the input is not accepted.

Compared to a deterministic model of computing where a command leads to a single action, NDTs given specific commands allow for a range of actions. For example, an input X would lead to a variety of actions Y(array).

Unambiguous Turing Machine

This is a special type of a non-deterministic turing machine where for each input, there is exactly a single possible computation. In many ways, it is similar to a deterministic turing machine.

Quantum Turing Machine

Also referred to as a universal quantum computer. It is an abstract machine that models the effects of a quantum computer by providing a simple model that covers the power of quantum computation.

This means that any quantum algorithm is can be expressed formally as a quantum turing machine.

Read-Only Turing Machine

Also referred to as a two-way deterministic finite-state automaton. It is a class of models of computability that behave like a standard turing machine and move in both directions across a given input except it cannot write to the input tape, only read it.

In its bare form, it is similar to a deterministic finite-state machine in computational power and therefore only parses regular languages.

Probabilistic Turing Machine

This is a turing machine that is modified to execute randomized computations. These machines make decisions based on the outcomes of unbiased coin tosses.
Every non-deterministic turing machine can be simulated by a probabilistic turing machine with a small error of probability.

Also unlike deterministic turing machines, they have stochastic results whereby on a given input and instruction state machine, it can have different run times or may not halt at all, furthermore, it may accept input in one execution and reject the same input in another execution.

Common applications of such machines are modeling a robot that handles accidents in a nuclear plant or modeling space missions that have strong radiations.

Applications of turing machines.

Different types of turing machines find applications in different areas of computer science, these include;

• Complexity studies.
• Software testing.
• Evolutionary computations.
• Software engineering.
• Computer networks.
• Machine learning.
• High-performance computing.

Summary.

A turing machine can compute anything computable. In this article, we learned about the different variations of turing machines and some of the applications of turing machines.

References.

1. Introduction to Theory of Computation - Anil Maheshwari, Michiel Smid