Crawling out of the Turing tarpit

Rolf W. Rasmussen

Half-day workshop - in English

Writing your own CPU emulator to successively run programs of increasing complexity

Alan Perlis warns “Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy”.

During this workshop, we’ll build up a CPU emulator one instruction at a time, designing the Instruction Set Architecture (ISA) as we go along, in order to successively run programs of increasing complexity. We’ll discover how few steps are needed to go from running “Hello World”, to a running an OS image with an embedded development environment.

Our goal is to create a practical Instruction Set Architecture, but we’ll also along the way touch upon some theoretical and historical aspects as well. We’ll see how to use abstraction to build layer upon layer of more complex functionality starting with a few basic building blocks. After measuring the cost of such abstraction, we’ll work on fixing inefficiencies that crop up.

Lastly, we’ll look at the different directions we could evolve the embryonic ISA and emulator we’ve created, how we would go about doing so, and what existing ISAs, software, and projects that occupy these spaces in the real world.

Slide deck:

Code examples:

Example executables:


Primarily for: Developers, Architects, Others

Participant requirements: Familiarity with how to run programs from the command line. A computer with any OS containing development tools for a programming language you master, such that writing command-line programs that read and writes files and interacts with standard input and output poses no problem. Java, C, C++, Python, C#, and Node.js are all examples of suitable languages.