Turing Machines

Turing Machines

The Turing Machine

A Turing machine (TM) is a theoretical model of computation that defines an abstract machine capable of performing calculations and processing symbols on an infinite tape. This model is fundamental in computer science and helps us understand the limits of what can be computed.

Components of a Turing Machine

A Turing machine consists of six components:

1. Alphabet (I): A finite set of symbols that the machine can read and write, excluding the blank symbol, denoted by 'd'.
2. Tape: An infinite sequence of cells, each capable of holding a single symbol from the alphabet. The tape is divided into cells, with the leftmost cell (cell i) containing the first symbol of the input.
3. Tape Head: A read/write head that can read the symbol in the current cell, write a new symbol, and move one cell to the left or right. The tape head starts at cell i and cannot move left from this cell.
4. Output Alphabet (r): A set of symbols that can be printed on the tape by the tape head. This set can include the blank symbol, but the blank is not counted as a letter in the output alphabet.
5. States: A finite set of states, including one START state and one or more HALT states. The machine begins execution in the START state and can enter HALT states to terminate processing.
6. Program: A set of rules that dictate how the machine transitions between states based on the current state and the symbol read from the tape. Each rule is represented as a triplet: (current symbol, symbol to write, direction to move).

Example of a Turing Machine

Consider a Turing machine designed to accept the language of strings where the second letter is a 'b' over the alphabet {a, b}. The input tape might look like this for the string 'aba':

The program for this Turing machine is represented as a directed graph with edges labeled with the rules:

(a, a, R)  // From state 1 to state 2 on reading 'a' and moving right
(h, h, R)  // From state 2 to state 3 on reading 'h' and moving right
(a, a, R)  // From state 3 to state 3 on reading 'a' and moving right
(h, h, R)  // From state 3 to state 4 on reading 'h' and moving right
HALT 4

Initially, the tape head reads cell i, which contains 'a'. The machine follows the rules as follows:

1. In state 1, reading 'a', it stays in state 1 and moves to the right (to cell ii).
2. In state 2, reading 'b', it moves to state 3 and continues right.
3. In state 3, it reads 'a', stays in state 3, and continues moving right until it reaches a blank.
4. Once it encounters a blank, it transitions to HALT state, indicating acceptance of the input string.

Execution Process of a Turing Machine

The execution of a Turing machine can be traced through its states and transitions. For example, let us trace the execution of the TM on the input string 'aba'. The process is as follows:

State: 1  Read: a  Tape: aba...  Move: R  Next State: 2
State: 2  Read: b  Tape: aba...  Move: R  Next State: 3
State: 3  Read: a  Tape: aba...  Move: R  Next State: 3
State: 3  Read: d  Tape: aba...  Move: HALT  Next State: HALT

The execution chain can be summarized as:

1 --> 2 --> 3 --> HALT

Common Mistakes

Types of Turing Machines

Turing machines can be classified based on their capabilities:

• Deterministic Turing Machines (DTMs): These machines have a single unique action for each state and symbol combination.
• Nondeterministic Turing Machines (NTMs): These machines can have multiple possible actions for a given state and symbol, allowing for parallel computation paths.

Language Acceptance by Turing Machines

A Turing machine accepts a string if it can reach a HALT state while processing that string. The set of accepted strings forms the language recognized by the Turing machine. For example, the language accepted by the TM in the previous example is all strings where the second letter is 'b'.

Summary

• A Turing machine is an abstract model of computation consisting of an alphabet, tape, tape head, output alphabet, states, and a program.
• Execution can be traced through state transitions based on rules defined in the program.
• Common mistakes include attempting to move the tape head left from the first cell.
• Languages accepted by TMs are defined by the strings that lead to a HALT state.

Check your understanding

• What are the six components of a Turing machine?
• How does a Turing machine determine if it accepts a string?
• What is the difference between deterministic and nondeterministic Turing machines?
• Provide an example of a simple Turing machine and describe its function.