Skip to content
Home » Unsolvable Problems

Unsolvable Problems

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 ProblemUnsolvable Problem
An algorithm existsNo general algorithm exists
TM can always give an answerNo TM can always give an answer
TM always haltsTM cannot be guaranteed to halt
Also called decidableAlso called undecidable
Example: Checking whether a number is evenExample: 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.

UnsolvableIntractable
No algorithm existsAn algorithm exists
Cannot be solved for all inputsCan be solved
No TM deciderTM/algorithm exists
Fundamental limitationMainly efficiency limitation
Example: Halting ProblemExample: 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:

  1. What computers can solve.
  2. What computers cannot solve.
  3. The limitations of algorithms.
  4. The difference between computability and complexity.
  5. Why some problems cannot have a general-purpose solution.
  6. 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