Turing Machine Formal Definition

1. From Automata to a General-Purpose Computer

Before diving into the formal details, let's build an intuition for what a Turing Machine is and why it's so powerful. Unlike DFAs, which can only move forward on their input, or PDAs, which have a restricted LIFO stack, a Turing Machine has a much more flexible memory model.

A Turing Machine consists of three main parts:

1. An infinite tape: This tape is divided into cells, each capable of storing one symbol. It acts as the machine's memory, holding the input and providing unlimited space for computation.
2. A tape head: The head can move left or right along the tape, one cell at a time. Crucially, it can both read the symbol in the cell it's currently on and write a new symbol to it.
3. A finite state control: This is the "brain" of the machine, similar to the control unit in a CPU. It contains a finite number of states and a program—the transition function—that dictates the machine's actions.

At each step, the machine's action is determined by its current state and the symbol under the tape head. Based on these two pieces of information, the machine will:

1. Change to a new state.
2. Write a symbol on the tape at the current position (possibly the same one).
3. Move the tape head one cell to the left or right.

This ability to move bidirectionally and write to the tape gives it the power to simulate any computer algorithm.

To get a dynamic feel for this, the following video provides an excellent introduction.

2. The Formal Definition of a Turing Machine

Now that we have the intuition, let's formalize it. Just as with DFAs and PDAs, we define a Turing Machine as a tuple of its components. A standard (deterministic) Turing Machine is a 7-tuple.

A Turing Machine (TM) is a 7-tuple $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,q_{accept},q_{reject})$, where:

1. $Q$ is a finite set of states. This is the machine's internal memory of its current condition, just like in a DFA or PDA.

2. $\Sigma$ is the input alphabet, a finite set of symbols. This alphabet cannot contain the special blank symbol ($\bigsqcup$). The initial input string is composed of symbols from $\Sigma$.

3. $\Gamma$ is the tape alphabet, a finite set of symbols that the machine is allowed to write on its tape. It has two important properties:

   • The input alphabet is a subset of the tape alphabet: $\Sigma \subseteq \Gamma$.
   • The blank symbol is in the tape alphabet, but not the input alphabet: $\bigsqcup \in \Gamma$ and $\bigsqcup \notin \Sigma$.
     Your experience with systems that process data might offer an analogy here. $\Sigma$ is the raw input data, while $\Gamma$ includes any intermediate markers, tags, or processed values your algorithm might generate and use during its execution.

4. $\delta$ is the transition function. This is the "program" of the TM. It takes the current state and the symbol under the tape head as input and outputs the next state, the symbol to write, and the direction to move the head.

   $$\delta :(Q\setminus \{q_{accept},q_{reject}\})\times \Gamma \to Q\times \Gamma \times \{L,R\}$$

   Let's break this down:

   • Domain: $(Q\setminus \{q_{accept},q_{reject}\})\times \Gamma$. The function is defined for any non-halting state and any tape symbol.
   • Codomain: $Q\times \Gamma \times \{L,R\}$. For a given (current_state, symbol_read), the function returns a triplet: (next_state, symbol_to_write, direction_to_move). L means move left, R means move right.

5. $q_0\in Q$ is the start state, where the computation begins.

6. $q_{accept}\in Q$ is the accept state. If the machine enters this state, it immediately halts and accepts the input.

7. $q_{reject}\in Q$ is the reject state. If the machine enters this state, it immediately halts and rejects the input.

Why Explicit Accept/Reject States?

Unlike a DFA, which naturally stops after reading the last input symbol, a TM can move back and forth and might never stop (i.e., it can enter an infinite loop). The two halting states, $q_{accept}$ and $q_{reject}$, provide a clear mechanism for the machine to terminate its computation and give a definitive "yes" or "no" answer. If a TM doesn't enter either of these states, it runs forever.

To solidify these formal definitions, please read the following excerpt from a set of lecture notes.

Conclusion

Today, we've taken the significant step of defining the Turing Machine, the most powerful computational model in our hierarchy. We have established both an intuitive understanding of its mechanics and a precise, formal definition.

Key Takeaways:

• A Turing Machine enhances previous models with an infinite tape and a tape head that can read, write, and move left or right.
• Its formal definition is a 7-tuple: $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,q_{accept},q_{reject})$.
• The input alphabet ($\Sigma$) is a subset of the tape alphabet ($\Gamma$), which also includes the special blank symbol ($\bigsqcup$).
• The transition function ($\delta$) is the core of the TM's logic, mapping a (state, symbol) pair to a (new_state, new_symbol, move_direction) triplet.
• Computation has three possible outcomes: it can accept (by entering $q_{accept}$), reject (by entering $q_{reject}$), or run forever.

Preview of the Next Lesson:
Just defining the machine isn't enough; we need to be able to describe its computation as it evolves over time. In the next lesson, we will learn how to trace the execution of a TM by defining its "configuration" or "instantaneous description," which captures a snapshot of the machine's state, tape contents, and head position at any given moment.