Wakka Wakka! This Turing Machine Performs Pac-Man

Wakka Wakka! This Turing Machine Performs Pac-Man


As I learn the latest papers about
DNA-based computing, I needed to confront a somewhat disagreeable fact. Regardless of being a geneticist who additionally majored in pc science, I used to be struggling to bridge two ideas—the common Turing machine, the very essence of computing, and the von Neumann structure, the idea of most fashionable CPUs. I had written C++ code to emulate the machine described in Turing’s 1936 paper, and will use it to resolve, say, if a phrase was a palindrome. However I couldn’t see how such a machine—with its one-dimensional tape reminiscence and skill to take a look at just one image on that tape at a time—may behave like a billion-transistor processor with {hardware} options similar to an arithmetic logic unit (ALU), program counter, and instruction register.

I scoured outdated textbooks and watched on-line lectures about theoretical pc science, however my data didn’t advance. I made a decision I might construct a bodily Turing machine that might execute code written for an actual processor.

Fairly than a billion-transistor behemoth, I believed I’d goal the common-or-garden 8-bit
6502 microprocessor. This legendary chip powered the computer systems I utilized in my youth. And as a ultimate proof, my simulated processor must run Pac-Man, particularly the model of the sport written for the Apple II pc.

In Turing’s paper, his eponymous machine is an summary idea with infinite reminiscence. Infinite reminiscence isn’t potential in actuality, however bodily Turing machines will be constructed with sufficient reminiscence for the duty at hand. The {hardware} implementation of a Turing machine will be organized round a rule guide and a notepad. Certainly, once we do fundamental arithmetic, we use a rule guide in our head (similar to realizing when to hold a 1). We manipulate numbers and different symbols utilizing these guidelines, stepping via the method for, say, lengthy division. There are key variations, although. We will transfer throughout a two-dimensional notepad, doing a scratch calculation within the margin earlier than returning to the principle drawback. With a Turing machine we will solely transfer left or proper on a one-dimensional notepad, studying or writing one image at a time.

A key revelation for me was that the interior registers of the 6502 may very well be duplicated sequentially on the one-dimensional notepad utilizing 4 symbols—0, 1, _ (or area), and $. The symbols 0 and 1 are used to retailer the precise binary knowledge that might sit in a 6502’s register. The $ image is used to delineate totally different registers, and the _ image acts as a marker, making it straightforward to return to a spot in reminiscence we’re working with. The principle reminiscence of the Apple II is emulated in a similar way.

: A printed circuit board and the chips and capacitors used to populate the board.Other than some flip-flops, a few NOT gates, and an up-down counter, the PureTuring machine makes use of solely RAM and ROM chips—there aren’t any logic chips. An Arduino board [bottom] displays the RAM to extract show knowledge. James Provost

Programming a CPU is all about manipulating the registers and transferring their contents to and from important reminiscence utilizing an instruction set. I may emulate the 6502’s directions as chains of guidelines that acted on the registers, image by image. The foundations are saved in a programmable ROM, with the output of 1 rule dictating the following rule for use, what must be written on the notepad (applied as a RAM chip), and whether or not we should always learn the following image or the earlier one.

I dubbed my machine PureTuring. The ROM’s knowledge outputs are linked to set of flip-flops. Among the flip-flops are linked to the RAM, to permit the following or earlier image to be fetched. Others are linked to the ROM’s personal handle traces in a suggestions loop that selects the following rule.

It turned out to be extra environment friendly to interleave the bits of some registers somewhat than leaving them as separate 8-bit chunks. Creating the rule guide to implement the 6502’s instruction set required 9,000 guidelines. Of those, 2,500 have been created utilizing an old-school technique of writing them on index playing cards, and the remaining have been generated by a script. Placing this collectively took about six months.

A diagram showing processor registers interleaved along a 1-D u201ctapeu201dSolely a number of the 6502 registers are uncovered to programmers [green]; its inside, hidden registers [purple] are used to execute directions. Beneath every register a how the registers are organized, and someday interleaved, on the PureTuring’s “tape.”James Provost

To fetch a software program instruction, PureTuring steps via the notepad utilizing $ symbols as landmarks till it will get to the reminiscence location pointed to by this system counter. The 6502 opcodes are one byte lengthy, so by the point the eighth bit is learn, PureTuring is in one among 256 states. Then PureTuring returns to the instruction register and writes the opcode there, earlier than transferring on to carry out the instruction. A single instruction can take as much as 3 million PureTuring clock cycles to fetch, versus one to 6 cycles for the precise 6502!

The 6502 makes use of a memory-mapped enter/output system. Because of this units similar to shows are represented as places someplace inside important reminiscence. Through the use of an Arduino to observe the a part of the notepad that corresponds to the Apple II’s graphics reminiscence, I may extract pixels and present them on an hooked up terminal or display screen. This required writing a “dewozzing” operate for the Arduino because the Apple II’s pixel knowledge is specified by a posh scheme. (
Steve Wozniak created this scheme to allow the Apple II to pretend an analog colour TV sign with digital chips and hold the dynamic RAM refreshed.)

I may have inserted enter from a keyboard into the notepad in a similar way, however I didn’t trouble as a result of really taking part in
Pac-Man on the PureTuring would require extraordinary endurance: It took about 60 hours simply to attract one body’s value of motion for the Pac-Man character and the pursuing enemy ghosts. A modification that moved the machine alongside the continuum towards a von Neumann structure added circuitry to allow random entry to a notepad image, making it pointless to step via all prior symbols. This adjustment minimize the time to attract the sport characters to a mere 20 seconds per body!

PureTuring Half 1. Turing Machine Microprocessor.www.youtube.com

Wanting ahead, options will be added one after the other, transferring piecemeal from a Turing machine to a von Neumann structure: Widen the bus to learn eight symbols at a time as a substitute of 1, change the registers within the notepad with {hardware} registers, add an ALU, and so forth.

Now once I learn papers and articles on DNA-based computing, I can hint every component again to one thing in a Turing machine or ahead to a standard structure, working my very own little psychological machine alongside a conceptual tape!


Leave a Reply

Back To Top
Theme Mode