While finite automata could model simple pattern recognition and pushdown automata could handle hierarchical, nested structures, both possessed inherent limitations related to memory. Finite automata had no auxiliary memory, and pushdown automata were restricted to a single, last-in-first-out (LIFO) stack. These limitations mean they cannot solve problems that require arbitrary amounts of sequential memory or the ability to read and rewrite anywhere in that memory.

The Turing Machine (TM), conceived by Alan Turing in 1936, overcomes these limitations by introducing an infinitely long tape that serves as its memory. This simple yet powerful addition allows the TM to simulate any algorithmic process. It is not intended as a practical model for building computers, but rather as a theoretical abstraction to understand the fundamental capabilities and limitations of computation itself.

A Turing Machine (TM) is formally defined as a 7-tuple (Q,Σ,Γ,δ,q0 ,qaccept ,qreject ), where:
● Q (States): A finite, non-empty set of internal states. These states represent the TM's current configuration or phase of computation, similar to states in automata.
○ Example: q_start, q_read, q_write, q_found_match.
● Σ (Input Alphabet): A finite, non-empty set of input symbols. These are the symbols that can appear in the initial input string placed on the tape.
○ Example: {0,1}, {a,b,c}. Crucially, the blank symbol _ is never part of the input alphabet.
● Γ (Tape Alphabet): A finite, non-empty set of symbols that can be written onto the tape. This set includes all input symbols and a special blank symbol.
○ Requirement: Σ⊆Γ.
○ Special Symbol: _ (blank symbol). This symbol is a member of Γ but not Σ. It represents an empty cell on the tape. The tape is initially filled with blanks everywhere except where the input string is written.
● δ (Transition Function): This is the core of the TM's operation. It dictates the TM's behavior at each step. Unlike DFAs or NFAs, the TM's transition depends on the current state and the symbol under the tape head. For a given (current state, tape symbol under head) pair, it specifies:
○ A new state to transition to.
○ A symbol to write onto the current tape cell (replacing the symbol just read).
○ A direction to move the tape head (Left or Right).
○ Formally, δ:Q×Γ→Q×Γ×{L,R}
■ L means move the tape head one cell to the left.
■ R means move the tape head one cell to the right.
○ Deterministic: This definition describes a deterministic Turing Machine. For any given (state, symbol) pair, there is exactly one possible action.
● q0 (Start State): The unique initial state from Q where the TM begins its computation.
● qaccept (Accept State): A designated state from Q. If the TM enters this state, it immediately halts and accepts the input string.
● qreject (Reject State): A designated state from Q. If the TM enters this state, it immediately halts and rejects the input string.
○ Important: qaccept and qreject must be distinct states (qaccept =qreject ). If a TM reaches either of these states, it halts. If it never reaches either, it runs forever (loops).

1. Tape: An infinitely long strip, divided into cells. Each cell can hold exactly one symbol from the tape alphabet Γ. The tape extends infinitely to the right (and often conceptualized as infinite to the left as well, or at least arbitrarily extendable). Initially, the input string occupies the leftmost portion of the tape, and all other cells are filled with the blank symbol _.
2. Tape Head: A mechanism that can read a symbol from a cell, write a symbol to a cell, and move left or right one cell at a time. It always points to a single cell on the tape.
3. Control Unit: The "brain" of the TM. It is in one of a finite number of states. Based on its current state and the symbol read by the tape head, it consults the transition function δ to decide:
   ○ What symbol to write onto the tape.
   ○ What direction to move the tape head.
   ○ What its next internal state will be.

1. Initialization: The input string is placed on the leftmost portion of the infinite tape. All other tape cells are filled with the blank symbol _. The tape head is positioned at the leftmost symbol of the input string. The control unit is in the start state q0 .
2. Execution Cycle (Loop): The TM repeatedly performs the following actions:
   ○ Read: The tape head reads the symbol currently in the cell it is pointing to.
   ○ Consult Transition Function: The control unit takes its current state and the symbol just read as input to the transition function δ.
   ○ Write, Move, Change State: Based on the output of δ(current_state,symbol_read)=(new_state,symbol_to_write,direction_to_move):
   ■ The symbol_to_write is written onto the current tape cell.
   ■ The tape head moves one cell in the specified direction_to_move (L or R).
   ■ The control unit transitions to the new_state.
   ○ Check for Halting: If the new_state is qaccept or qreject, the TM halts.
3. Halting Conditions:
   ○ Acceptance: If the TM enters state qaccept, it halts and the input string is considered accepted.
   ○ Rejection: If the TM enters state qreject, it halts and rejects the input string.
   ○ Looping: If the TM never enters qaccept or qreject, it continues to run indefinitely (loops).