Adding Computing Theory to Computer Design and Architecture

Abstract: According to the most recent Computer Science Curriculum, all computer science students should receive around 6 instructional hours on key concepts from computing theory covering areas such as finite automata, regular expressions, grammars and the halting problem. Computing theory has traditionally been a difficult subject for computer science students and as a result a key question is how and in what type of setting should computing theory be presented. Presented here are materials for one approach which naturally ties the rather abstract computing theory concepts to ideas and tools presented in a computer design and architecture course (based on the book by Nisan and Schocken). Each computing theory concept is presented through lecture slides, an associated video lecture, in-class activity and take home lab.


All of the following instructional materials are available under a Creative Commons license. See Adding Computing Theory to a Course on Computer Design and Architecture for full details.

Finite State Machines

Turing Machines and the Halting Problem

Regular Expressions

Context-Free Grammars

Copyright 2015. Jesse Eickholt