The discussion above has, casually, assumed that there are decision problems for which algorithms do not exist.

(nothing above has given any evidence for the assumption made).

We can prove that there *exist* decision problems for which no
algorithm exists by employing a method of argument called

If there are `more' decision problems than programs then it must be the
case that *some* decision problems cannot be solved by programs since
since a single program can solve only a single decision problem.

Suppose we are given two sets of items, *A* and *B*, say, e.g.

*A =* Set of all students registered for the course 2CS46

*B =* Set of all students registered for the course 2CS42

How can we tell if there are more items in *A* than there are in *B*?

By `counting' the number of items in each set.

- How many different decision problems are there?

Thus there are an infinite number of distinct decision problems.

How many different ADA programs are there which take a single number, *n*,
as input
and return a *0* or *1* as their result?

Infinitely many. Since there are clearly infinitely many such programs which contain a loop of the form

foriin1..mloops := 0;end loop;

*`Counting'* is all right when the sets being compared are *finite*.

*`Counting'* does not appear to tell us anything
when both sets are *infinite*.

Q: What do we *actually do* when we `count' the number of items in a set?

A: To each item we attach a unique `label': 1,2,3,4,...

Thus, in comparing the *sizes* of two finite
sets, *A* and *B*, we attach `labels'
to the items in *A*, and `labels' to the items in *B* and we say that

But why use `numbers' as the `labels' to count with?

We could use items in *A* to *label items in B* (i.e. count) and, if
*A* is larger than *B*, then at least one item in *A* will *not
have been used* to label any item in *B*.

And we can `count' *B* by using the `labels'

and now GARY has *not been used* to label any element of *B* and so we
can say that

If it can be shown that for *every way* of labelling items in *B* with
items in *A*
there is *at least one* item of *A*
which is *not* used as a label then, again,
we can state that:

Let:

*A = * The set of *all* decision problems,
*f : N -> {0,1}*.

*B = * The set of all *ADA* programs.

We can *enumerate* (i.e. list) every single ADA
program. That is there is an algorithm
which will output every single different ADA program in turn, e.g.

(Recall thati := 1;loopifADA_PROGRAM ( i ) = 1thenput ( Binary representation of i );end if;i :=i + 1;end loop;

Thus we can talk about a

i.e. the 1st, 2nd, 3rd, *...*, *nth*, *...*, program that is output by
the procedure above.

And so we can form an infinite table, *T*:

1 | 2 | 3 | ........ | n | ........ | |
---|---|---|---|---|---|---|

P_{1} | *P_{1} (1) | P_{1} (2) | P_{1}(3) | ........ | P_{1}(n) | ........ |

P_{2} | P_{2} (1) | *P_{2} (2) | P_{2} (3) | ........ | P_{2} (n) | ........ |

P_{3} | P_{3} (1) | P_{3} (2) | *P_{3} (3) | ........ | P_{3} (n) | ........ |

.. | .. | .. | .. | ........ | ||

.. | .. | .. | .. | ........ | ||

P_{n} | P_{n} (1) | P_{n} (2) | P_{n} (3) | ........ | *P_{n} (n) | ........ |

.. | .. | .. | .. | ........ | ||

.. | .. | .. | .. | ........ |

If it *is* the case that *every* decision problem, *f*, is computed
by *at least one* ADA program, then in the table above which `labels'
each ADA program with a decision problem:

i.e. There is a row, *Pf*, of the table such
that *Pf( n ) = f( n )* for all *n*.

What about the following decision problem?

*DIAG* is well-defined, since our table, *T*, above exists.

*P1* (*DIAG(1) /= P1(1)*)

OR that labelling *P2* (*DIAG(2) /= P2(2)*)

OR that labelling *P3* (*DIAG(3) /= P3(3)*)

*...*

OR that labelling *Pn* (*DIAG(n) /= Pn(n)*).

And so, the decision problem, *DIAG*, does not
label any *Pn*, in the table *T*.

Now matter how the ADA programs are ordered, we can always define a decision problem,
*DIAG*, as above, which does not label any program in the ordering.

In consequence:

Decision problems for which no algorithm exists are called: