Unsolvable Problems are problems for which no algorithm or Turing Machine can always produce a correct answer and halt for every possible input.
This is an important topic under the last unit: Unsolvable Problems and Computational Complexity.
1. Definition
An unsolvable problem is a problem for which no Turing Machine exists that can solve the problem for all possible inputs in finite time.
In simple words:
An unsolvable problem is a problem that cannot be solved by any computer algorithm for every possible input.
Such problems are also called:
- Undecidable problems
- Non-computable problems (in the appropriate context)
2. Solvable vs Unsolvable Problems
| Solvable Problem | Unsolvable Problem |
|---|---|
| An algorithm exists | No general algorithm exists |
| TM can always give an answer | No TM can always give an answer |
| TM always halts | TM cannot be guaranteed to halt |
| Also called decidable | Also called undecidable |
| Example: Checking whether a number is even | Example: Halting Problem |
Easy Example
Problem: Is a number even?
Algorithm:
Input number
↓
Divide by 2
↓
Remainder = 0?
/ \
Yes No
↓ ↓
Even Odd
The algorithm always finishes.
Therefore, it is solvable.
3. Unsolvable Problem Example
The most famous example is the:
Halting Problem
The question is:
Given a program/Turing Machine and its input, can we determine whether it will eventually stop or continue running forever?
For example:
Program P + Input I
↓
Will P stop?
/ \
YES NO
↓ ↓
Halt Run forever
There is no algorithm that can correctly answer this question for every possible program and input.
Therefore, the Halting Problem is undecidable.
4. Why Do Unsolvable Problems Exist?
Computers are extremely powerful, but their computational power has limits.
A Turing Machine can represent the computation performed by a general-purpose computer. However, there are certain problems for which no Turing Machine can always produce the required answer and halt.
Therefore:
Not every well-defined problem can be solved by a computer.
This is a fundamental result of Computability Theory.
5. Main Characteristics of Unsolvable Problems
An unsolvable problem has the following characteristics:
1. No general algorithm exists
There is no single algorithm that solves all possible cases.
2. No TM decider exists
No Turing Machine can always halt and give the correct answer.
3. Some instances may still be solvable
An individual case may be solved, but there is no algorithm that works for all cases.
4. It is different from a difficult problem
An unsolvable problem is not merely very difficult or slow.
Difficult problem
↓
Can theoretically be solved
↓
Algorithm exists
Whereas:
Unsolvable problem
↓
No general algorithm exists
6. Important Unsolvable Problems
Some important undecidable problems studied in TOC are:
1. Halting Problem
Determining whether a TM will halt on a particular input.
2. Post Correspondence Problem (PCP)
Determining whether two sequences of strings have a matching concatenation.
3. Acceptance Problem
Determining whether a given TM accepts a given input.
4. Word Problem for Certain Formal Systems
Determining whether a particular string can be derived in some formal systems.
5. Some Problems for Context-Free Languages
Certain questions about CFGs/CFLs are undecidable, such as whether two CFGs generate exactly the same language.
7. Decidable and Undecidable Languages
This topic can also be understood using languages.
Decidable Language
A language \(L\) is decidable if there is a Turing Machine that:
- accepts every string in \(L\),
- rejects every string not in \(L\),
- and halts in both cases.
Therefore:\[ \boxed{\text{Decidable Language = Recursive Language}} \]
Undecidable Language
A language is undecidable if no such Turing Machine exists.
A recognizer may accept strings belonging to the language but may run forever on strings not belonging to it.
8. Unsolvable vs Intractable Problems
This distinction is very important because both terms can look similar.
| Unsolvable | Intractable |
|---|---|
| No algorithm exists | An algorithm exists |
| Cannot be solved for all inputs | Can be solved |
| No TM decider | TM/algorithm exists |
| Fundamental limitation | Mainly efficiency limitation |
| Example: Halting Problem | Example: many NP-hard problems |
Remember:
Unsolvable = Cannot be solved algorithmically.
Intractable = Can be solved, but may take too much time/resources.
9. How Do We Prove a Problem Is Unsolvable?
A common method is proof by contradiction.
General approach:
Assume an algorithm exists
↓
Use it to construct another algorithm
↓
Show that this creates a contradiction
↓
Therefore, the assumed algorithm cannot exist
↓
Problem is undecidable
The Halting Problem is the classic example of this type of proof.
10. Importance of Unsolvable Problems
Unsolvable problems are important because they tell us about the limits of computation.
They help us understand:
- What computers can solve.
- What computers cannot solve.
- The limitations of algorithms.
- The difference between computability and complexity.
- Why some problems cannot have a general-purpose solution.
- The theoretical limits of programming languages and computer systems.
5–10 Marks Exam Answer
Unsolvable Problems are problems for which no algorithm or Turing Machine can always produce a correct answer and halt for every possible input. They are also called undecidable problems.
An unsolvable problem is not simply a difficult or time-consuming problem. Rather, no general algorithm exists to solve all instances of the problem.
The most famous example is the Halting Problem, which asks whether a given Turing Machine will halt or continue running forever on a given input. It has been proved that no algorithm can correctly answer this question for every possible Turing Machine and input.
Other important undecidable problems include the Post Correspondence Problem, Turing Machine Acceptance Problem, and certain problems involving Context-Free Grammars.
The concept of unsolvable problems is important because it establishes the fundamental limitations of computers and algorithms.
Fast Memory Trick
Unsolvable = No General Algorithm
Remember:
Decidable → Algorithm exists → Always halts
Undecidable → No such algorithm → Cannot always decide
And for the last unit, keep this sequence in mind:
Unsolvable Problem → Halting Problem → PCP → Unsolvable Problems for CFLs → Complexity → Tractable/Intractable Problems
