Understanding Turing Machines and Their Complexities
Turing Machine
The Turing machine is a collection of the following components: M = (Q, E, Γ, δ, q0, B, F). 1) Q is a finite set of states. 2) T is a finite set of external symbols. 3) E is a finite set of input symbols. 4) A or B or B in T is a blank symbol, majorly used as an end marker for input. 5) δ is a transition or mapping function.
Design of TM
The Turing machine can be modeled with the help of the following representation: 1) The input tape has an infinite number of cells, each cell containing one input symbol, and thus the input string can be placed on a tape. The empty tape is filled with blank characters. 2) The finite control and the tape head are responsible for reading the current input symbol. The tape head can move left or right. 3) A finite set of states through which the machine has to undergo.
Universal Turing Machine
1. The universal language Lu is a set of binary strings that can be modeled by a Turing machine. 2. The universal language can be represented by a pair (M, w) where M is a TM that accepts this language and w is a binary string in (0 + 1)* such that w belongs to L(M). Thus, we can say that any binary string belongs to a universal language. 3. The universal language can be represented by Lu = L(U) where U is a universal Turing machine. 4. In fact, U is a binary string. This binary string represents various codes of many Turing machines. 5. Thus, the universal Turing machine is a Turing machine that accepts many Turing machines.
Multi-tape Turing Machine
The multitape Turing machine is a type of Turing machine in which there are more than one input tape. Each tape is divided into cells, and each cell can hold any symbol of a finite tape alphabet. Each tape is infinite in both directions and can hold symbols from a given alphabet. Each tape has its own read/write head that moves independently of the others. The machine’s transition function depends on the current state and the symbols being read by all tape heads.
Halting Problem of Turing Machine (TM)
Statement: The Halting Problem asks whether a given TM TT, with an input tape tt, will eventually halt or run forever. The halting problem is unsolvable.
Proof: Assume there exists a TM M1 that decides if any TM TT halts on input tt.
- M1 halts (accepts) if T halts for t.
- M1 halts (rejects) if T does not halt for t.
Construct another TM M2 that:
- Takes an input description dT of Turing machine T.
- Duplicates dT and gives it to M1 as input.
- Modifies M1 such that:
- If M1 accepts (i.e., T halts), M2 loops forever.
- If M1 rejects (i.e., T does not halt), M2 halts.
Set M2 = T:
- M2 loops if M2 halts (contradiction).
- M2 halts if M2 loops (contradiction).
Conclusion: The contradiction proves that M1 cannot exist. Hence, the halting problem is unsolvable.
Reducibility is a problem-solving technique in mathematics. Let A and B be two problems, and A is reduced to B. If we solve B, we solve A as well. If we can’t solve A, we can’t solve B. For example, if we solve the Eulerian cycle problem, we solve the Eulerian path problem. To decide if a problem is solvable or not, we use the mapping reducibility technique. If there is a mapping reduction from language A to language B, we say that language A is mapping reducible to language B. Notation used for mapping reducibility is A ≤MB iff language A is mapping reducible to language B. If A is reduced to B and B is decidable, then A is decidable. If A is undecidable and reducible to B, then B is also undecidable.
| Solvable Problems | Unsolvable Problems |
|---|---|
| Problems for which an algorithm (or Turing machine) exists that can provide a solution for every valid input in a finite amount of time. | Problems for which no algorithm (or Turing machine) can provide a solution for every valid input. |
| A Turing machine will always halt with the correct answer. | A Turing machine may not halt or cannot provide a definitive answer. |
| These problems are decidable. | These problems are undecidable. |
| An algorithm can be designed to compute the solution. | No algorithm exists to compute the solution. |
| Sorting numbers, finding the shortest path, arithmetic operations, string matching. | Halting Problem, Entscheidungsproblem (Decision Problem), Post Correspondence Problem. |
| P Class Problems | NP Class Problems |
|---|---|
| Problems that can be solved in polynomial time by a deterministic Turing machine. | Problems whose solutions can be verified in polynomial time by a deterministic Turing machine. |
| Polynomial Time | Nondeterministic Polynomial Time |
| P ⊆ NP (Every problem in P is also in NP because computation can be verified by re-performing it). | It is unknown whether P = NP or P ≠ NP. |
| Solvable by a deterministic algorithm in polynomial time. | Verification assumes nondeterministic guessing of the solution. |
| Problems in P are computationally feasible. | Many NP problems are hard to solve but easy to verify once a solution is given. |
| Sorting (e.g., merge sort), matrix multiplication, shortest path. | Sudoku, Boolean satisfiability problem (SAT), Hamiltonian path problem. |
| Decidable Problems | Undecidable Problems |
|---|---|
| Problems for which a Turing machine can always produce a correct yes or no answer for every input in a finite amount of time. | Problems for which no Turing machine can decide a correct answer for all possible inputs. |
| An algorithm (Turing machine) exists that halts on all inputs and gives the correct decision. | No algorithm can decide the problem for all inputs; the Turing machine may not halt or give the correct answer. |
| These problems can always be solved. | These problems cannot always be solved. |
| Always halts with a correct yes/no decision. | May loop forever or fail to give a definitive answer for some inputs. |
| Solutions can be implemented and verified using algorithms. | Highlights the limitations of computation and defines theoretical boundaries. |
Polynomial Time Reduction
To prove whether a particular problem is NP-complete or not, we use polynomial time reducibility. The reduction is an important task in NP completeness proofs. Various types of reductions are: Local replacement – In this reduction A -> B by dividing input to A in the form of components, and then these components can be converted to components of B. Component design – In this reduction A -> B by building a special component for input B that enforces properties required by A.
P (Polynomial Time) class refers to the set of decision problems that can be solved by a deterministic Turing machine in polynomial time. These problems are considered computationally “easy” or “efficiently solvable.”
Explanation: 1. Deterministic Turing Machine (DTM): A DTM follows a well-defined sequence of steps to solve a problem, ensuring a solution in finite time. 2. Polynomial Time: The time taken to solve a problem is bounded by a polynomial function of the input size n. 3. Nature of Problems in P: 1) Problems in P have efficient algorithms for finding solutions. 2) As the input size increases, the computation time grows at a manageable rate. 4) Significance: 1) Provides a baseline for “efficiently solvable” problems. 2) Acts as a benchmark for comparing other complexity classes like NP. Examples: Arithmetic Problems: Multiplying two numbers, matrix multiplication. P ⊆ NP, but whether P = NP remains an open question.
NP (Nondeterministic Polynomial Time) class refers to the set of decision problems for which a solution, if one exists, can be verified in polynomial time by a deterministic Turing machine. Alternatively, NP can be defined as the set of problems solvable in polynomial time by a nondeterministic Turing machine, which can “guess” a solution and verify it efficiently. It is unknown whether P = NP, i.e., whether every problem whose solution can be verified in polynomial time can also be solved in polynomial time. Boolean Satisfiability Problem (SAT): Determining if there exists an assignment of truth values to variables that satisfies a Boolean formula.
Traveling Salesman Problem (TSP) (Decision version):
Checking if there exists a route with a cost less than a given value.Subset Sum Problem:
Verifying if a subset of numbers from a given set adds up to a specific target.Graph Problems:
- Determining if a graph has a Hamiltonian cycle.
- Verifying if a given graph is 3-colorable.
The Boolean Satisfiability Problem (SAT) asks whether there exists a truth assignment to the variables of a given Boolean formula such that the formula evaluates to true. The formula is expressed in conjunctive normal form (CNF), which is a conjunction of clauses, where each clause is a disjunction of literals.
NP-Completeness of SAT: The SAT problem is NP-complete, meaning 1. Given a specific truth assignment to the variables, it is easy (polynomial time) to verify whether the formula evaluates to true. This satisfies the definition of problems in NP. 2. SAT is as hard as any problem in NP. This means that any problem in NP can be reduced to SAT in polynomial time. In other words, if we can solve SAT efficiently (in polynomial time), we can solve any NP problem efficiently. 3. SAT is the first problem proven to be NP-complete. The concept of NP-completeness was introduced by Stephen Cook in 1971, and he proved that SAT is NP-complete through what is now known as Cook’s Theorem.
The NP-completeness of the SAT problem highlights the difficulty of solving it efficiently. It also plays a crucial role in the study of computational complexity, as it serves as the foundation for proving other problems NP-complete by polynomial-time reductions.
The Satisfiability (SAT) problem asks whether there exists a truth assignment to the variables of a given Boolean formula such that the formula evaluates to true.
The formula is usually expressed in conjunctive normal form (CNF), where it is a conjunction of clauses, and each clause is a disjunction of literals. A literal is either a variable or its negation.
For example, consider the Boolean formula: (A∨¬B∨C)∧(B∨¬C). The SAT problem asks: “Is there an assignment of truth values to A, B, and C such that the entire formula evaluates to true?”
The Satisfiability problem (SAT) is central to computational complexity theory. Its NP-completeness makes it an important problem in understanding the limits of efficient computation. Many real-world problems, such as hardware verification and AI reasoning, can be reduced to SAT, demonstrating its practical significance.
A Recursively Enumerable (RE) Language is a class of languages that can be recognized by a Turing Machine. These languages are also known as Turing-recognizable or partial recursive languages. A language L is recursively enumerable if there exists a Turing machine (TM) that will accept all strings in L and either halt on all strings in L or loop indefinitely on strings not in L. In other words, a Turing machine can recognize (or enumerate) the strings of L, but if a string is not in L, the machine may not halt. A recursively enumerable language can be recognized by a non-deterministic or deterministic Turing machine. Recursively Enumerable (RE) languages include all decidable languages (which can be accepted by a Turing machine that halts on all inputs), but also includes languages for which a Turing machine might not halt on all inputs. The set of prime numbers: We can write a Turing machine that, given a number n, will eventually halt if n is prime by checking all possible divisors. If n is divisible by any number other than 1 and itself, the machine rejects it; otherwise, it accepts it. The Turing machine may loop indefinitely on composite numbers, as it would never reach the conclusion that the number is non-prime.
A Context-Free Grammar (CFG) is a formal grammar used to describe context-free languages (CFLs), which are a class of languages that can be generated by a set of production rules. CFGs are widely used to describe the syntax of programming languages and formal languages. Context-Free Grammar is a 4-tuple G = (V, Σ, R, S) where: V is a set of variables (non-terminal symbols), also called non-terminal symbols; Σ is a set of terminal symbols; R is a set of production rules; S is the start symbol.
| FA | PDA |
|---|---|
| A Finite Automaton is a theoretical model of computation that accepts or rejects strings based on a finite number of states and transitions between them. | A Pushdown Automaton is a theoretical model of computation that extends finite automata by adding a stack to the system, which allows it to store and retrieve symbols. |
| FA has a finite number of states. | PDA also has a finite number of states, but it can use a stack to store additional information. |
| FA has no memory other than the current state. | PDA has a stack, providing memory to store symbols that can be used to remember previous inputs. |
| FA can recognize only regular languages. | PDA can recognize context-free languages, which is a broader class than regular languages. |
| Transitions depend on the current state and the input symbol. | Transitions depend on the current state, input symbol, and the top symbol of the stack. |
An NPDA (Nondeterministic Pushdown Automaton) is a type of Pushdown Automaton (PDA) that allows for nondeterministic transitions. This means that, unlike deterministic automata, an NPDA can have multiple possible transitions for the same input symbol and current state. It can choose between multiple options or “branches” of computation, which allows it to explore different possibilities simultaneously. In a nondeterministic PDA, for a given state and input symbol, there can be multiple possible transitions. This is different from a Deterministic PDA (DPDA), where for each state and input, there is exactly one possible transition. The stack is used to store and retrieve symbols, which is crucial for recognizing context-free languages.