4
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I like this. :) $\endgroup$
    – TuringTux
    Commented Jun 26, 2017 at 7:56
  • 1
    $\begingroup$ Don't forget about his cryptography work. He played a big role in breaking Enigma. $\endgroup$
    – Ray
    Commented Jun 28, 2017 at 21:52

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

I would, given the time period you have, show the entire film. It's an excellent movie, only strays slightly from the actual story of the Turing machine, and is fairly accurate (the only discrepancy I found was that Turing's boss begged him to work on it instead of Turing going to them about it). After the film I would discuss the discrepancies and how "Christopher" was used as reference and evolved to the first computers.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.