1. Definition
A Non-Computational Problem is a problem for which no computer or algorithm can always provide a solution.
In simple words:
A non-computational problem is a problem that cannot be solved by any algorithm, no matter how powerful or fast the computer is.
This is different from a problem that is simply slow to solve.
2. Computational vs Non-Computational
| Computational Problem | Non-Computational Problem |
|---|---|
| Can be solved using an algorithm | Cannot be solved by any algorithm |
| Computer can produce an answer | No general algorithm exists |
| Example: Sorting numbers | Example: General Halting Problem |
| Problem is computable | Problem is uncomputable |
Important Point
Slow problem ≠ Non-computational problem
For example, if a problem takes 100 years to solve, it may still be computational.
But if no algorithm can solve it, it is non-computational.
3. Example: Halting Problem
Suppose we have a program P and an input I.
We want to determine:
Will program P eventually stop, or will it continue running forever?
For some programs, we can determine the answer.
But there is no general algorithm that can correctly determine this for every possible program and input.
This is called the Halting Problem and is a famous example of an undecidable/non-computational problem.
4. Why are Non-Computational Problems Important?
They help us understand the limits of computers.
They tell us that:
- Computers cannot solve every possible problem.
- Some problems have no algorithmic solution.
- Increasing computer speed cannot solve these problems.
- There are fundamental limits to computation.
5. Examples
Important examples include:
- Halting Problem
- Post Correspondence Problem (PCP)
- Some problems related to Turing Machines
- Some decision problems involving formal languages
⭐ Exam Answer — 5 Marks
Non-Computational Problems are problems for which no algorithm exists that can provide a correct solution for all possible inputs. Such problems are also called undecidable or uncomputable problems in many contexts. They represent the fundamental limitations of computers.
A famous example is the Halting Problem, which asks whether a given program will stop or continue running forever for a particular input. It has been proved that no general algorithm can solve this problem for all programs.
Other examples include the Post Correspondence Problem and certain problems related to Turing Machines.
Thus, non-computational problems show that there are limits to what computers can solve.
🧠 Easy line to remember
“If no algorithm can solve a problem for all inputs → it is a non-computational/undecidable problem.”
