Turing Machine in TOC
The Turing Machine is a mathematical computation model that accepts Recursive Enumerable Languages (ERL) in TOC (Theory of Computation). The mathematician and logician Alan Turing invented the Turing machine in 1936. Turing machine is not a physical device but a theoretical model for some computations.
Purpose of Turing Machine
Turing machines, Pushdown Automata (PDA), and Finite State Machines (FSM) are all models of computation. Turing machine is more powerful than PDA and FSM regarding computational power, memory, language recognition, and applications. Let’s explain all of these
1. Computational Power
Let’s compare the Turing machine concerning computational power with PDA and FSM.
- The Turing Machine is the most powerful and can recognize any algorithmic process.
- Pushdown Automata is less powerful than Turing machines because it recognizes context-free languages, which are a subset of the languages recognized by Turing machines.
- Finite State Machine is the lowest in power. It recognizes regular languages, which are a subset of context-free languages.
2. Memory
Let’s compare the Turing machine concerning memory with PDA and FSM.
- Turing Machine uses infinite input tape for its memory, allowing it to store unlimited information.
- Pushdown Automaton uses a stack for its memory.
- A Finite State Machine has a limited internal state and no explicit external memory like a Stack or input tap, so it is the least powerful in terms of memory.
3. Language Recognition
Let’s compare the Turing machine concerning language recognition with PDA and FSM.
- Turing Machine recognizes recursively enumerable languages (REL), including all regular, context-free, and recursively enumerable languages.
- Pushdown Automaton recognizes context-free languages that include regular languages.
- Finite State Machine recognizes only regular languages.
4. Applications
Let’s compare the Turing machine’s applications with PDA and FSM.
- Turing Machine is mainly used in theoretical computer science to define algorithm processes.
- Pushdown Automaton is used to parse context-free grammars and make them relevant for analyzing programming languages and syntax.
- Designers commonly use finite-state machines to design and model simple systems, such as control circuits.
Elements of Turing Machine
The turning machine has the essential elements given below.
Input Tape: It has an infinite length for performing read and write operations.
Input Symbols: The input tape consists of infinite cells, each containing either an input or a special symbol. A special symbol is also called a blank symbol in an automata, the Turing machine.
- Input Symbols (∑) an be in the form of {0,1, a, b, ε, Z0}
- Special Symbols (B) can be in the form of {&, $,],[, #, etc. }
Head pointer: A read/write head pointer that points to the cell being read/write and can move in both (left and right) directions.
Following is a descriptive diagram of the Turing Machine.
Operation on Input Tape in Turing Machine
Let’s explain the basic operations over Input Tape.
- Read/scan the symbol below the tap Head
- Update / Write a symbol below the Tap Head
- Move the Tap Head one step LEFT or RIGHT
Let’s see the descriptive diagram
Important:
|
Computation Result in Turing Machine
Following are all possible results after performing all operations on input tape.
- HALT and ACCEPT: We reach an accepted state when we have done all operations.
- HALT and REJECT: We get a rejected state after doing all operations.
- LOOP: it means the machine fails to HALT or reject
Note: HALT is also called STOP