Unit 6: TURING MACHINES AND COMPLEXITY

1. The Turing Machine Model

The Turing Machine (TM), proposed by Alan Turing in 1936, is the mathematical model of a general-purpose computer. It serves as the standard definition of "computability." If a problem can be solved by an algorithm, it can be solved by a Turing Machine.

1.1 Components of a Turing Machine

A TM consists of three main components:

1. Infinite Tape: Divided into cells. Each cell holds a single symbol from a finite alphabet. The tape extends infinitely to the right (and optionally to the left).
2. Read/Write Head: Can read the symbol on the current cell, write a new symbol, and move one cell Left () or Right ().
3. Finite Control: The "brain" of the machine. It is in a specific state and changes states based on transition rules.

1.2 Formal Definition (The 7-Tuple)

A Turing Machine is defined as a 7-tuple:

• : Finite set of states.
• : Input alphabet (subset of , cannot contain the blank symbol).
• : Tape alphabet (contains and the blank symbol ).
• : Transition function, defined as , where:
  • is the current state.
  • is the tape symbol being read.
  • is the next state.
  • is the symbol written to the tape (replacing ).
  • is the direction of the head move ( for Left, for Right).
• : Initial state ().
• : Blank symbol (, but ). All tape cells initially contain except for the input.
• : Set of final/accepting states ().

2. Representation of Turing Machines

2.1 Instantaneous Description (ID)

An ID represents the complete snapshot of the TM at a specific moment. It is denoted as a string :

• : The string on the tape to the left of the head.
• : The current state.
• : The string on the tape beginning at the head position.

Example Transition:
If the ID is and , the next ID is .

2.2 Transition Diagrams

Similar to Finite Automata, states are nodes and transitions are directed edges. An edge from to labeled means: "If in state reading , replace it with , move direction , and go to state ."

2.3 Transition Tables

A tabular representation where rows represent states and columns represent tape symbols. Cells contain the tuple .

3. Design of Turing Machines

Designing a TM involves creating a logical algorithm to manipulate the tape head. Common strategies include:

• Marking: Replacing input symbols with auxiliary symbols (e.g., changing '0' to 'X') to track processed data.
• Matching: Moving back and forth to match symbols (e.g., matching 's with 's).
• Shifting: Moving data on the tape to create space.

Example Design:

Logic:

1. Read the leftmost '0', replace it with 'X', move Right.
2. Scan across '0's and 'Y's until a '1' is found.
3. Replace the '1' with 'Y', move Left.
4. Scan left until 'X' is found, then move one step Right.
5. Repeat.
6. If all '0's and '1's are converted to 'X's and 'Y's, accept.

4. Variations of Turing Machines

Despite these modifications, none of these variations have more computational power than the Standard TM. They simply make designing machines easier (efficiency may vary).

4.1 Multi-Tape Turing Machine

• Has independent tapes and independent read/write heads.
• The transition function reads symbols and performs writes and moves.
• Theorem: Every Multi-tape TM has an equivalent Single-tape TM.

4.2 Non-Deterministic Turing Machine (NDTM)

• The transition function results in a subset of possible moves .
• Acceptance: If any sequence of choices leads to a final state, the string is accepted.
• Theorem: For every NDTM, there exists a deterministic TM (DTM) that accepts the same language. (Note: The simulation may take exponential time, but computability remains the same).

4.3 Multi-Dimensional TM

• Tape is a 2D grid (or 3D, etc.). Head can move Up, Down, Left, Right.
• Equivalent to standard 1D TM.

4.4 Two-Way Infinite Tape

• Tape extends infinitely in both left and right directions.
• Equivalent to standard one-way infinite TM.

5. Linear Bounded Automaton (LBA)

An LBA is a restricted Turing Machine.

5.1 The Model

• Restriction: The potentially usable tape is limited to the portion containing the input (plus two end markers).
• The tape is not infinite. The length of the tape is a linear function of the input length (usually exactly or ).
• Transitions cannot move left of the left marker or right of the right marker.

5.2 Power of LBA

• Accepts: Context-Sensitive Languages (CSL).
• Hierarchy: Finite Automata Pushdown Automata LBA Turing Machines.
• Non-Determinism: It is an open question (The LBA Problem) whether Deterministic LBA = Non-Deterministic LBA.

6. Basic Concepts of Computability

6.1 Recursive Language (Decidable)

A language is Recursive if there exists a Turing Machine such that:

1. If , accepts (halts in a final state).
2. If , rejects (halts in a non-final state).
   • Key: The machine always halts.

6.2 Recursively Enumerable Language (RE)

A language is Recursively Enumerable if there exists a Turing Machine such that:

1. If , accepts and halts.
2. If , may halt and reject OR it may loop forever.
   • Key: We are only guaranteed an answer for valid strings.

6.3 Relationship

• If a language and its complement are both RE, then is Recursive.

7. Decidability and Undecidability

7.1 Decidable Problems

A problem is decidable if there is an algorithm (a TM that always halts) that solves it.

• Example: Is a regular language empty? (Decidable).

7.2 Undecidable Problems

A problem is undecidable if it is proven that no algorithm can exist to solve it for all inputs.

7.3 The Halting Problem

Statement: Given a Turing Machine and an input string , is there an algorithm to determine if will eventually halt on ?
Result: The Halting Problem is Undecidable.
Proof Logic (Diagonalization):

1. Assume a machine exists that decides halting.
2. Construct a new machine that takes input (description of a machine).
3. asks : "Does halt on input ?"
4. If says YES, enters an infinite loop.
5. If says NO, halts.
6. Run on itself ().
   • If halts, it implies it loops.
   • If loops, it implies it halts.
7. Contradiction. Therefore, cannot exist.

7.4 Post Correspondence Problem (PCP)

An undecidable combinatorial problem.

• Input: Two lists of strings and .
• Question: Is there a sequence of indices such that the concatenation of strings from list A equals the concatenation from list B?
  
• Status: Undecidable for general alphabets.

8. Computational Complexity

Complexity theory classifies decidable problems based on the resources required to solve them.

8.1 Measuring Complexity

1. Time Complexity (): The number of steps (transitions) the TM makes before halting, as a function of input length .
2. Space Complexity (): The number of distinct tape cells visited by the TM during computation.

8.2 Complexity Classes

• P (Polynomial Time): Problems solvable by a Deterministic TM in polynomial time (). Considered "efficiently solvable."
• NP (Nondeterministic Polynomial Time): Problems solvable by a Non-Deterministic TM in polynomial time. Equivalently, solutions can be verified by a DTM in polynomial time.
• PSPACE: Problems solvable using polynomial space.

8.3 P vs NP

• .
• The biggest open problem in computer science is whether .

9. Cellular Automaton

While TMs operate sequentially (one head, one cell), Cellular Automata (CA) operate in parallel.

9.1 Definition

• A grid of cells (1D, 2D, or higher).
• Each cell is in one of a finite number of states.
• Time advances in discrete steps.
• Local Rule: The new state of a cell depends on its current state and the states of its neighbors. All cells update simultaneously.

9.2 Example: Conway's Game of Life

• 2D grid. States: Alive (1) or Dead (0).
• Rules:
  1. Underpopulation: Live cell with < 2 neighbors dies.
  2. Survival: Live cell with 2 or 3 neighbors lives.
  3. Overpopulation: Live cell with > 3 neighbors dies.
  4. Reproduction: Dead cell with exactly 3 neighbors becomes alive.

9.3 Relation to Turing Machines

• Certain Cellular Automata (like the Game of Life or Wolfram's Rule 110) are Turing Complete.
• This means a Cellular Automaton can simulate any Turing Machine, and thus can compute anything computable.