I was thinking of sharing them in a recent thread on AI, but that was not really the place.

I'm thinking of two results that are somewhat related and can be big eye openers:

1. The halting problem.

Turing proved in 1936 that it was not possible to create an algorithm (program) that would determine, given another program as input, whether that program would finish (i.e. not loop infinitely).

The huge take-away:

**some things are fundamentally in-computable.**

Note that this was done before the advent of computers.

### Halting problem - Wikipedia

en.wikipedia.org

2. The Cantor diagonal method.

This is explainable to someone with high-school math.

Cantor proved that the real numbers were not "countable".

A set is defined to be countable if it can be put in "into" correspondence with the natural numbers.

A countable set could be infinite (countably infinite), if it could be placed in "1-to-1" correspondence with the natural numbers.

Examples of countably infinite sets: the even numbers; the odd numbers; fractions i.e. rational numbers.

Cantor used a surprisingly elementary method to prove that there was no possible "1-to-1" mapping between the real numbers and the natural numbers.

### Cantor's diagonal argument - Wikipedia

en.wikipedia.org

The huge take-away:

**There are different sizes of infinity.**

Cantor's method has been used as the basis for things like the halting theorem (above) or Gödel's incompleteness theorem.

What are other examples of cool science or math within unexpectedly easy reach?