Lesson 2

We call a problem decidable (or algorithmically decidable) if there exists a program that, for any input, finds a correct output in finite time. It is easy to see that the set of all programs is countable: indeed, a program is just a finite-length string over a finite alphabet.