Algorithmically Unsolvable Problems

Unsolvable problems ???

$64,000 question:

Are there problems that you cannot design an algorithm to find the solution ????
I.e.:

Answer: yes

A famous algorithmically unsolvable problem is the Halting problem

The Halting Problem

Alan Turing (father of the Turing Machine) proved in 1936 that a general algorithm to solve the Halting Problem cannot exist

The Halting Problem:

Given:

Problem:

Write an algorithm H(P, I) that determines if the program P will stop when it is given the input I.
H(P, I) will return:
Schematiclly:

Claim:

There is no algorithm that can find the (correct) solution to the Halting problem

Preparation for the proof:

In the proof, we will be using:
It may sound weird as first to have a program as input
But it is not strange at all because you have seen this before !!!

Example: a compiler

A Java compiler takes as input a Java program
It outputs the same program in Java Byte code (i.e., translates "English commands" into binary encoded instructions)

Proof:

Suppose you have found a solution to the Halting Problem
The proof consists of constructing a program where H() will fail to return the correct answer

Proof continued...

We construct the following (obnoxious) program K(x) using H(P,I):

K( x ) { if ( H(x, x) ) { while (true); } else { exit; } }

We will make H(P, I) solve:

Program P = K
With Input I = K

I.e.:, we run:

H( K, K )

Now, we know H(K,K) will return one of the following 2 answers:

H( K, K ) = true (meaning: Program K will stop when input = K) H( K, K ) = false (meaning: Program K will not stop when input = K)

Suppose that H(K, K) = true (i.e., K will stop when I = K).

Let's look at the actual execution of K(K):

K( K ) { if ( H(K, K) /* returns true */ ) { while (true); /* Hey: Program K does NOT stop !!! */ } else { exit; } }

So the answer H(K,K) = true was incorrect !!!!

Now, suppose that H(K,K) = false (i.e., K will not stop when I = K).

Let's look at the actual execution of K(K):

K( K ) { if ( H(K, K) /* returns false */ ) { while (true); } else { exit; /* Hey, Program K STOPS !!! */ } }

So the answer H(K,K) = false is also incorrect

What have we achieved:

If someone will ever create an algorithm that can solve the halting problem, we have:

Therefore:

an algorithm that can the Halting Problem can never be written !!!

Postscript....

The construction is similar to the Russel Paradox

Russel Paradox:

Define R = the set of all sets that are not members of themselves .
I.e.: R = { x | x ∉ x }

$64,000 question:

Is R ∈ R or
Is R ∉ R
(One of the above statement must be true :-))

Assume that R ∈ R, then:

Since: R = { x | x ∉ x } and: R ∈ R Therefore: R ∉ R !!! Contradicts the assumption that R ∈ R

Assume that R ∉ R, then:

Since: R = { x | x ∉ x } and: R ∉ R Therefore: R ∈ R !!! Contradicts the assumption that R ∉ R

We conclude that R ∈ R and R ∉ R are both incorrect...

A popular version of the Russel paradox is:

A barber X shaves all barbers who do not shave themselves

Question: Does barber X shaves himself ?

Yes, he does leads to:
No, he does not leads to: