Curriculum Design for a Unit on Alan Turing and His Impact on CS At the end of the year, there is a gap between the AP Exam for AP Computer Science A and the last class meeting. Since students don't have to take a final after the AP Exam, there's not a lot of motivation for additional graded work. Nonetheless, I want to make the time meaningful, so my plan is to put together a short unit on Alan Turing, his contributions to CS, Turing Machines, Turing-completeness, the importance of the Halting Problem, the Turing Test, etc. Hopefully, I can integrate clips from The Imitation Game as well to increase engagement.

The unit as a whole would last a little over a week and would be engaging (as something post-AP Exam in May has to be). This would be for a small class of students just having completed two years of AP Computer Science and very likely studying CS in college. 

Are there short lessons/units you have on Alan Turing that students respond well to? If you've taught some of the above concepts before (TMs, Halting Problem, Turing Test, etc.), what classroom resources do you have to explain them in a short, student-friendly manner?
With only a few weeks, it's hard to cover much in depth, but you can skim the surface of a few topics.  I would focus the unit by talking about the problem of computability that Turing and Church (and others) were facing.  It's a nice problem, because it is easy to describe in broad strokes, and the implications border on the mystical.

I would then go on as a class to look at how Turing attempted to explore the problem.  I would start with creating Finite State Machines, and run a few class periods of this to help them get the hang of it.  I might mention, but not really explore, the idea of a grammar, and talk about the equivalence of FSMs with regular expressions.

Then I would skip PDAs and move right into Turing Machines.  Have them spend some time building them in class, and finally introduce the Busy Beaver problem with this video.  Be prepared to stop and talk a few times during it to help them keep up to speed. The payoff at the end is totally worth it.

I would finish up by describing the Halting Problem, and talk a bit about what the implications of an Oracle would be if it could somehow exist.

At the very end of the unit, I might mention that Turing created his solution using mutability as a core idea, but that there was another approach created by Church, Turing's mentor from Princeton, that used pure mathematical functions to accomplish the same thing.  The two of them proved that their systems were equally powerful in the Church-Turing Thesis.  And as funny as it sounds to have computation without mutability, there is an entire branch of programming languages devoted to exactly this approach called functional languages.

Obviously just mentioning this won't get them to understand functional languages, but it will set the stage for them later on in their undergrad CS years to appreciate why they are learning functional programming in the first place.