Wakka Wakka! This Turing Machine Plays Pac-Man

As I read the newest papers about
DNA-based computing, I had to confront a rather unpleasant truth. Despite being a geneticist who also majored in computer science, I was struggling to bridge two concepts—the universal Turing machine, the very essence of computing, and the von Neumann architecture, the basis of most modern CPUs. I had written C++ code to emulate the machine described in Turing’s 1936 paper, and could use it to decide, say, if a word was a palindrome. But I couldn’t see how such a machine—with its one-dimensional tape memory and ability to look at only one symbol on that tape at a time—could behave like a billion-transistor processor with hardware features such as an arithmetic logic unit (ALU), program counter, and instruction register.

I scoured old textbooks and watched online lectures about theoretical computer science, but my knowledge didn’t advance. I decided I would build a physical Turing machine that could execute code written for a real processor.

Rather than a billion-transistor behemoth, I thought I’d target the humble 8-bit
6502 microprocessor. This legendary chip powered the computers I used in my youth. And as a final proof, my simulated processor would have to run Pac-Man, specifically the version of the game written for the Apple II computer.

In Turing’s paper, his eponymous machine is an abstract concept with infinite memory. Infinite memory isn’t possible in reality, but physical Turing machines can be built with enough memory for the task at hand. The hardware implementation of a Turing machine can be organized around a rule book and a notepad. Indeed, when we do basic arithmetic, we use a rule book in our head (such as knowing when to carry a 1). We manipulate numbers and other symbols using these rules, stepping through the process for, say, long division. There are key differences, though. We can move all over a two-dimensional notepad, doing a scratch calculation in the margin before returning to the main problem. With a Turing machine we can only move left or right on a one-dimensional notepad, reading or writing one symbol at a time.

A key revelation for me was that the internal registers of the 6502 could be duplicated sequentially on the one-dimensional notepad using four symbols—0, 1, _ (or space), and $. The symbols 0 and 1 are used to store the actual binary data that would sit in a 6502’s register. The $ symbol is used to delineate different registers, and the _ symbol acts as a marker, making it easy to return to a spot in memory we’re working with. The main memory of the Apple II is emulated in a similar fashion.

Apart from some flip-flops, a couple of NOT gates, and an up-down counter, the PureTuring machine uses only RAM and ROM chips—there are no logic chips. An Arduino board [bottom] monitors the RAM to extract display data. James Provost

Programming a CPU is all about manipulating the registers and transferring their contents to and from main memory using an instruction set. I could emulate the 6502’s instructions as chains of rules that acted on the registers, symbol by symbol. The rules are stored in a programmable ROM, with the output of one rule dictating the next rule to be used, what should be written on the notepad (implemented as a RAM chip), and whether we should read the next symbol or the previous one.

I dubbed my machine PureTuring. The ROM’s data outputs are connected to set of flip-flops. Some of the flip-flops are connected to the RAM, to allow the next or previous symbol to be fetched. Others are connected to the ROM’s own address lines in a feedback loop that selects the next rule.

It turned out to be more efficient to interleave the bits of some registers rather than leaving them as separate 8-bit chunks. Creating the rule book to implement the 6502’s instruction set required 9,000 rules. Of these, 2,500 were created using an old-school method of writing them on index cards, and the rest were generated by a script. Putting this together took about six months.

Only some of the 6502 registers are exposed to programmers [green]; its internal, hidden registers [purple] are used to execute instructions. Below each register a how the registers are arranged, and sometime interleaved, on the PureTuring’s “tape.”James Provost

To fetch a software instruction, PureTuring steps through the notepad using $ symbols as landmarks until it gets to the memory location pointed to by the program counter. The 6502 opcodes are one byte long, so by the time the eighth bit is read, PureTuring is in one of 256 states. Then PureTuring returns to the instruction register and writes the opcode there, before moving on to perform the instruction. A single instruction can take up to 3 million PureTuring clock cycles to fetch, versus one to six cycles for the actual 6502!

The 6502 uses a memory-mapped input/output system. This means that devices such as displays are represented as locations somewhere within main memory. By using an Arduino to monitor the part of the notepad that corresponds to the Apple II’s graphics memory, I could extract pixels and show them on an attached terminal or screen. This required writing a “dewozzing” function for the Arduino as the Apple II’s pixel data is laid out in a complex scheme. (
Steve Wozniak created this scheme to enable the Apple II to fake an analog color TV signal with digital chips and keep the dynamic RAM refreshed.)

I could have inserted input from a keyboard into the notepad in a similar fashion, but I didn’t bother because actually playing
Pac-Man on the PureTuring would require extraordinary patience: It took about 60 hours just to draw one frame’s worth of movement for the Pac-Man character and the pursuing enemy ghosts. A modification that moved the machine along the continuum toward a von Neumann architecture added circuitry to permit random access to a notepad symbol, making it unnecessary to step through all prior symbols. This adjustment cut the time to draw the game characters to a mere 20 seconds per frame!

Looking forward, features can be added one by one, moving piecemeal from a Turing machine to a von Neumann architecture: Widen the bus to read eight symbols at a time instead of one, replace the registers in the notepad with hardware registers, add an ALU, and so on.

Now when I read papers and articles on DNA-based computing, I can trace each element back to something in a Turing machine or forward to a conventional architecture, running my own little mental machine along a conceptual tape!

​IEEE Spectrum