This paper should be of great assistance and value to people working in theoretical computer science, as well as those interested in mathematics education at the high school level.

A package, “Computational Models” (CM), consisting of 90 hours in the 11th or 12th grade, was introduced in some high schools in Israel. More than half of the package is devoted to finite automata, and deterministic, nondeterministic, and regular languages. About 25 percent of the material is devoted to PDAs and context-free languages, and the rest to Turing machines and the halting problem.

This paper surveys the performance of the 540 students using the package. While it is not possible to present any details of the results here, it should be mentioned that many rather obvious preconceptions were amply confirmed in the study. The material of CM is very suitable for high school study. The teaching can be started from scratch, but familiarity with some abstract thinking on the part of the students will be of great help. Existence and irregularity proofs present greater difficulties than direct constructions. There is no correlation between previous experience with computers and success with CM; on the contrary, there is a negative correlation between performance in existence proofs and previous computer experience.