Lesson 1

Now we will use the methods developed above to prove that there exist undecidable problems! In fact, it is not surprising that such problems exist. What is surprising is that there are practically important problems that are undecidable.

Undecidability was first proven by Alan Turing. At the age of twenty-four, he wrote a paper titled “On computable Numbers, with an Application to the Entscheidungsproblem”. In this (one and the same!) paper, three important concepts were introduced: Turing machines — a mathematical framework for analyzing computations (computers did not yet exist at the time!), the concept of decidability, and the Church–Turing thesis.