Page 69 - 2502_Pakistan-kifayat_C-8

Turing’s Halting Problem

One of the most important discoveries about unsolvable problems came from Alan Turing in the 1930s.
The Halting Problem asks whether there is a general algorithm (a program) that can determine, for any
given program and its input, whether that program will eventually stop running (halt) or will run forever.
This means we cannot build a perfect "stop detector" for every possible program. Some programs
might run forever, and no one method can always tell if or when they will stop.

The Halting Problem shows limitations of computation: some problems are fundamentally unsolvable
by computers. It lays the foundation for the theory of computability and helps understand what
computers can and cannot do.

Real-World Examples of Unsolvable Problems

These abstract ideas have real impacts:

Predicting everything: No computer can perfectly predict the future because so many things
depend on unpredictable events and endless details.

Detecting all computer viruses: Some viruses use tricks to hide themselves so well that no program
can always detect every virus.
Perfectly understanding human language: Human language is full of slang, context, jokes, and
emotions, making it impossible for any algorithm to understand every meaning perfectly.

Predicting the weather perfectly: Even though we have weather apps, they can’t tell exactly what
the weather will be like weeks or months ahead. That’s because the weather is very complicated, and
many tiny changes can make a big difference.

Knowing what everyone will think or do: No computer can read minds or know exactly what
people will decide to do in the future. People can surprise us!

Double Tap Century #Critical Thinking
21 st
Skills
State whether these statements are true or false.

1. Complex problems can always be solved with a formula.

2. Algorithms can solve every problem in the world.

3. The Halting Problem is unsolvable.
4. Efficiency means using minimum resources.

PSEUDOCODE

Pseudocode is a simple way to plan a program or solve a problem using plain, everyday language. It
helps us think step-by-step, just like writing a set of instructions or a recipe. It describes an algorithm in
simple, human-readable language without syntax. Pseudocode is not written in any special computer

#Solving Complex Problems 67