Concept of Algorithm

Solvable Problems: A problem is considered solvable if an algorithm exists that can solve all instances of that problem correctly in a finite amount of time. Examples are:

        i.            Sorting a list of numbers

      ii.            Finding the shortest path between two points on a map.

    iii.            Determining if a number is prime etc.

A problem can be solvable even if we haven't found the most efficient algorithm for it yet. The key is that some algorithm is proven to exist.

Unsolvable Problems: A problem is considered unsolvable (or undecidable) if it is logically impossible to create an algorithm that can solve all instances of that problem. These limitations are not due to a lack of human ingenuity or computing power but are fundamental consequences of mathematical logic and the theory of computation, as proven by Alan Turing and others.

The Halting Problem: A Famous Unsolvable Problem

Problem Statement: Can we write a program H that takes another program P and its input I as input, and correctly determines whether P will eventually halt (finish running) or run forever when given input I?

Alan Turing's Proof (1936): Turing proved, through a brilliant logical contradiction, that no such general-purpose program H can ever exist.

Simplified Idea: Assume H exists. Then, we could create a program C that uses H on itself. If H says C halts, then C is designed to run forever, and vice versa. This contradiction means our initial assumption (that H exists) must be false.

Significance: The Halting Problem was one of the first problems proven to be undecidable. It shows there are inherent limits to what computers can do, no matter how powerful they become.

Other Examples of Unsolvable Problems:

Equivalence Problem: Determining if two arbitrary programs produce the same output for all inputs.

Entscheidungsproblem ("Decision Problem"): Determining whether a given statement of first-order logic is universally valid.